题目链接:uva 11754 - Code Feat
题目大意:求一个数N,给出C和S,表示有C个条件,每个条件有X 和 k,然后是该个条件的k个yi,即NmodX=yj,输出满足的最小的S个N,要求正整数。
解题思路:total为所有的k的乘积,也就是可以作为一组完整限定条件的可能数,当个确定条件可以用中国剩余定理处理。但是如果total太大的话,处理的情况比较多。不过total数大的时候,可以通过枚举N来判断,找到一组k/x最小的最为枚举基准,然后判断即可。
#include <cstdio>
#include <cstring>
#include <set>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long ll;
const int maxc = 15;
const int maxk = 105;
const int limit = 10000;
ll total;
int C, S, X[maxc], k[maxc];
int bestc, Y[maxc][maxk];
set<int> vis[maxc];
void init () {
total = 1;
bestc = 0;
for (int i = 0; i < C; i++) {
scanf("%d%d", &X[i], &k[i]);
total *= k[i];
for (int j = 0; j < k[i]; j++)
scanf("%d", &Y[i][j]);
sort(Y[i], Y[i] + k[i]);
if (k[i] * X[bestc] < k[bestc] * X[i])
bestc = i;
}
}
void solveEnum (int s) {
for (int i = 0; i < C; i++) {
if (i == s)
continue;
vis[i].clear();
for (int j = 0; j < k[i]; j++)
vis[i].insert(Y[i][j]);
}
for (int t = 0; S; t++) {
for (int i = 0; i < k[s]; i++) {
ll n = (ll)X[s] * t + Y[s][i];
if (n == 0)
continue;
bool flag = true;
for (int c = 0; c < C; c++) {
if (c == s)
continue;
if (!vis[c].count(n%X[c])) {
flag = false;
break;
}
}
if (flag) {
printf("%lld\n", n);
if (--S == 0)
break;
}
}
}
}
int a[maxc];
vector<int> sol;
void gcd(ll a, ll b, ll& d, ll& x,ll& y) {
if (!b) {
d = a;
x = 1;
y = 0;
} else {
gcd(b, a%b, d, y, x);
y -= x*(a/b);
}
}
int china (int n, int* s, int* m) {
ll M = 1, d, y, x = 0;
for (int i = 0; i < n; i++)
M *= m[i];
for (int i = 0; i < n; i++) {
ll w = M / m[i];
gcd(m[i], w, d, d, y);
x = (x + y * w * a[i]) % M;
}
return (x+M)%M;
}
void dfs (int dep) {
if (dep == C)
sol.push_back(china(C, a, X));
else {
for (int i = 0; i < k[dep]; i++) {
a[dep] = Y[dep][i];
dfs(dep+1);
}
}
}
void solveChina () {
sol.clear();
dfs(0);
sort(sol.begin(), sol.end());
ll M = 1;
for (int i = 0; i < C; i++)
M *= X[i];
for (int i = 0; S; i++) {
for (int j = 0; j < sol.size(); j++) {
ll n = M * i + sol[j];
if (n > 0){
printf("%lld\n", n);
if (--S == 0)
break;
}
}
}
}
int main () {
while (scanf("%d%d", &C, &S) == 2 && C + S) {
init();
if (total > limit)
solveEnum(bestc);
else
solveChina();
printf("\n");
}
return 0;
}
分享到:
相关推荐
CPP中的Postfix-Tree-Calculator:在C ++中实现后缀树计算器。 包括来自UVA CS部门的测试C ++文件
UVa写入 使用C ++编写UVa OJ: : 等级 基于 ★★ ★★ ★★★ ★★★★ ★★★★★ 未排名
判断输入字符串是否为镜像或回文串。 来源于UVaOJ - 401. 水题。
programming-problems:使用C ++,Rust,C或Python解决方案来解决不同竞争编程平台的问题
开源项目-codingsince1985-UVa#uva-online-judge-solutions-in-golang.zip,两年来每天都在解决一个uva在线裁判问题,算起来…
uva705 Slash Maze 的代码,在UVaOJ上通过
PDF试题
Algorithm-UVA-Solutions-in-Python.zip,python 3中各种uva(acm)问题的解决方案。,算法是为计算机程序高效、彻底地完成任务而创建的一组详细的准则。
uva532 Dungeon Master的源代码,并且AC了