codeforces gym100851 Generators 暴力+贪心

http://codeforces.com/gym/100851

题目大意：给 n n n个随机数生成器： x i = ( x i − 1 ∗ a + b ) % c x_i=(x_{i-1}*a+b)\%c xi​=(xi−1​∗a+b)%c，( 0 < = a , b < = 1000 , 0 < = x 0 < c < 1000 0<=a,b<=1000,0<=x_0<c<1000 0<=a,b<=1000,0<=x0​<c<1000)，现在要从它们对应的每一个序列中选取一个数，使得总和最大且这个总和不能被 k k k整除。

思路：看数据范围，可以暴力找出循环节，即暴力得到所有序列，从而得到每一个序列的最大的数的总和 s u m sum sum，若 s u m % k ! = 0 sum\%k!=0 sum%k!=0，那么答案就是 s u m sum sum，否则我们对于每一个序列找到 M A X i − A i j MAX_i-A_{ij} MAXi​−Aij​最小的且不能被 k k k整除的数，再从这 n n n个数中找到最小的那个数，记为 M I N MIN MIN，答案就是 s u m − M I N sum-MIN sum−MIN。复杂度 O ( c m a x ∗ n ) O(c_{max}*n) O(cmax​∗n)。

#include<bits/stdc++.h>
#define INF 0x3f3f3f3f
using namespace std;
typedef long long ll;

bool vis[1005];
int tmp[10005];
int ans[10005];
int re[10];
int n,k,x,a,b,c;

int main()
{
	freopen("generators.in","r",stdin);
	freopen("generators.out","w",stdout);
	scanf("%d %d",&n,&k);
	int sum=0,len=0,MAX=0,siz=0,MIN=INF;
	for(int i=1;i<=n;i++)
	{
		MAX=-1;
		siz=0;
		scanf("%d %d %d %d",&x,&a,&b,&c);
		while(!vis[x])
		{
			if(x>MAX)
			{
				MAX=x;
				ans[i]=siz;
			}
			vis[x]=1;
			tmp[siz++]=x;
			x=(x*a+b)%c;
		}
		sum+=MAX;
		int u;
		for(int j=0;j<siz;j++)
		{
			vis[tmp[j]]=0;
			u=MAX-tmp[j];
			if(u<MIN&&u%k!=0)
				MIN=u,re[0]=i,re[1]=j;
		}
	}
	if(sum%k==0)
	{
		if(MIN==INF)
			printf("-1\n");
		else
		{
			printf("%d\n",sum-MIN);
			ans[re[0]]=re[1];
			for(int i=1;i<=n;i++)
				printf("%d ",ans[i]);
			printf("\n");
		}
	}
	else
	{
		printf("%d\n",sum);
		for(int i=1;i<=n;i++)
			printf("%d ",ans[i]);
		printf("\n");
	}
	return 0;
}