UVALive 7472

题意有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");

            }

        }

    }

}

巴特西

UVALive 7472

最新文章

热门文章