codeforces gym100851 Generators 暴力+贪心

http://codeforces.com/gym/100851
题目大意：给$n$个随机数生成器：$x_i=(x_{i-1}\ast a+b)\%c$，($0<=a,b<=1000,0<=x_0<c<1000$)，现在要从它们对应的每一个序列中选取一个数，使得总和最大且这个总和不能被$k$整除。

思路：看数据范围，可以暴力找出循环节，即暴力得到所有序列，从而得到每一个序列的最大的数的总和$sum$，若$sum\%k!=0$，那么答案就是$sum$，否则我们对于每一个序列找到$MA{X}_i-A_{ij}$最小的且不能被$k$整除的数，再从这$n$个数中找到最小的那个数，记为$MIN$，答案就是$sum-MIN$。复杂度$O(c_{max}\ast 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; }

总结

以上是生活随笔为你收集整理的codeforces gym100851 Generators 暴力+贪心的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。