UVA 11754 - Code Feat

题目链接

题意：给定一个c个x, y1,y2,y3..yk形式，前s小的答案满足s % x在集合y1, y2, y3 ... yk中

思路：LRJ大白例题，分两种情况讨论

1、全部x之积较小时候，暴力枚举每一个集合选哪个y。然后中国剩余定理求解

2、全部x之积较大时候，选定一个k/x尽可能小的序列，枚举x * t + y (t = 1, 2, 3...)去暴力求解。

代码：

#include <stdio.h>

#include <string.h>

#include <vector>

#include <set>

#include <algorithm>

using namespace std;

const int N = 15;

const int M = 105;

int c, s, x[N], k[N], y[N][M], now;

set<int> value[N];

vector<long long> ans;

long long a[N];

void solve_enum() {

	for (int i = 0; i < c; i++) {

		if (c == now) continue;

		value[i].clear();

		for (int j = 0; j < k[i]; j++)

			value[i].insert(y[i][j]);

 	}

 	for (int t = 0; ; t++) {

 		for (int i = 0; i < k[now]; i++) {

 			long long n = (long long)x[now] * t + y[now][i];

 			if (n == 0) continue;

 			bool ok = true;

 			for (int i = 0; i < c; i++) {

 				if (i == now) continue;

 				if (!value[i].count(n % x[i])) {ok = false; break;}

    		}

    		if (ok) {printf("%lld\n", n); if (--s == 0) return;}

   		}

  	}

}

long long exgcd(long long a, long long b, long long &x, long long &y) {

	if (!b) {x = 1; y = 0; return a;}

	long long d = exgcd(b, a % b, y, x);

	y -= a / b * x;

 	return d;

}

long long china() {

	long long M = 1, ans = 0;

 	for (int i = 0; i < c; i++)

 		M *= x[i];

	for (int i = 0; i < c; i++) {

		long long w = M / x[i];

		long long xx, yy;

		exgcd(x[i], w, xx, yy);

		ans = (ans + w * yy * a[i]) % M;

 	}

 	return (ans + M) % M;

}

void dfs(int d) {

	if (d == c) {

		ans.push_back(china());

		return;

 	}

 	for (int i = 0; i < k[d]; i++) {

 		a[d] = y[d][i];

 		dfs(d + 1);

	}

}

void solve_china() {

	ans.clear();

	dfs(0);

	sort(ans.begin(), ans.end());

	long long M = 1;

	for (int i = 0; i < c; i++) M *= x[i];

	for (int i = 0; ; i++) {

		for (int j = 0; j < ans.size(); j++) {

			long long n = M * i + ans[j];

			if (n > 0) {printf("%lld\n", n); if (--s == 0) return;}

  		}

 	}

}

int main() {

	while (~scanf("%d%d", &c, &s) && s || c) {

		now = 0;

		long long sum = 1;

  		for (int i = 0; i < c; i++) {

			scanf("%d%d", &x[i], &k[i]);

			sum *= k[i];

			if (k[i] * x[now] < k[now] * x[i])

				now = i;

			for (int j = 0; j < k[i]; j++)

				scanf("%d", &y[i][j]);

			sort(y[i], y[i] + k[i]);

  		}

  		if (sum > 10000) solve_enum();

  		else solve_china();

  		printf("\n");

	}

	return 0;

}