题意 有n个循环 给出x a b c xi+1=(a*x+b)%c 要求是从这些循环中各取一个数 使加和最大并且给出一个m 满足sum%m!=0
n的范围是4次方 c的范围是3次方 训练赛的时候看了一眼就觉得好难 稍微一处理就要超时..
天气好热 又wa了水题两次 十分不想做题QAQ 看着有点难就懒得想 掏出手机开始玩 坑了蕾姐一把 QAQ 以后再也不这样了
然而蕾姐还是机智的想出了几近正解的办法QAQ
在这个循环中 每两个紧挨着的数的间隔必定是一样的 这些数的值在0~C之间 是1000
我们对每个循环的最大值和次大值进行保存
可以看出 一旦出现sum%m 由于每个循环必定需要一个数 如果这个间隔%m==0 那么我们将一个大的数换为一个小的数 仍然会有sum%m==0 是浪费
如果间隔%m!=0 那么换次大值就可以达到使sum%m==0变为！=0
所以 我们把所有循环的最大值加起来作为一个sum 之后 找出最小且%k!=0的间隔
如果sum%m!=0直接输出就可以 如果==0 就减去间隔 由于间隔%k!=0 所以减去间隔的sum%k！=0
#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<map>
#include<math.h>
#include<iostream>
using namespace std;
/// 保存下来 每个循环的循环大小(最大的和第二大的) 以及该循环是否可以%k 记录最大的和第二大的地点
int xh[10050];
int maxw1[10050];
int maxw2[10050];
int vis[1050];
bool ok[10050];
int main()
{
int n,m;
while(scanf("%d%d",&n,&m)!=EOF)
{
memset(ok,false,sizeof(ok));
memset(vis,0,sizeof(vis));
int x,a,b,c;
int sum=0;
for(int i=1; i<=n; i++)
{
scanf("%d%d%d%d",&x,&a,&b,&c);
vis[x]=i;
int maxx=x;
int maxx2=-1;
int maxxid=1;
int maxx2id=-1;
int cnt=1;
while(1)
{
x=(a*x+b)%c;
if(vis[x]==i)
break;
vis[x]=i;
cnt++;
if(x>maxx)
{
maxx2=maxx;
maxx=x;
maxx2id=maxxid;
maxxid=cnt;
}
else if(x>maxx2)
{
maxx2=x;
maxx2id=cnt;
}
}
maxw1[i]=maxxid;
if(maxx2!=-1)
{
maxw2[i]=maxx2id;
int z=maxx-maxx2;
xh[i]=z;
if(z%m!=0)
ok[i]=true;
else ok[i]=false;
}
else
{
ok[i]=false;
}
sum+=maxx;
}
if(sum%m!=0)
{
printf("%d\n",sum);
for(int i=1; i<=n; i++)
{
printf("%d",maxw1[i]-1);
if(i==n)
printf("\n");
else printf(" ");
}
}
else
{
int minn=1005;
int w=-1;
for(int i=1; i<=n; i++)
{
if(ok[i])
{
if(xh[i]<minn)
{
minn=xh[i];
w=i;
}
}
}
if(minn!=1005)
{
maxw1[w]=maxw2[w];
printf("%d\n",sum-xh[w]);
for(int i=1; i<=n; i++)
{
printf("%d",maxw1[i]-1);
if(i==n)
printf("\n");
else printf(" ");
}
}
else
{
printf("-1\n");
}
}
}
}