【bzoj3671】[Noi2014]随机数生成器

优先按照它说明的方法处理数组

然后为了让数列中尽可能多的出现小的数字

所以1是必须要出现的，这样才能使整个数列的排序后字典序最小。

我们思考，如果2也能在这个数列中那就最好不过了

但是2有可能不在这个数列里，就是2在走了1就不可能走的地方的话，就不能走2了。

所以从小到大枚举数字，如果当前数字能走，就输出，然后标记所有走了这个节点就不能走的节点。

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstring>

#include<cstdio>

#include<cmath>

using namespace std;

typedef long long LL;

#define N 5010

LL seed,a,b,c,d;

int n,m,ask;

int x,y;

int arr[N*N],g[N][N];

int ans[N<<2];

bool v[N][N];

int work()

{

    return seed=(a*seed*seed%d+b*seed%d+c)%d;

}

int main()

{

    scanf("%lld%lld%lld%lld%lld%d%d%d",&seed,&a,&b,&c,&d,&m,&n,&ask);

    for (int i=1;i<=n*m;i++)

        arr[i]=i,swap(arr[i],arr[work()%i+1]);

    for (int i=1;i<=ask;i++)

    {

        scanf("%d%d",&x,&y);

        swap(arr[x],arr[y]);

    }

    for (int i=1;i<=m;i++)

        for (int j=1;j<=n;j++)

            g[i][j]=arr[(i-1)*n+j];

    for (int i=1;i<=m;i++)

        for (int j=1;j<=n;j++)

            arr[g[i][j]]=(i-1)*n+j;

    for (int i=1;i<=n*m;i++)

    {

        x=arr[i]/n+1-(arr[i]%n==0);

        y=arr[i]-(x-1)*n;

        if (!v[x][y])

        {

            if (i!=1)

                putchar(' ');

            printf("%d",i);

            for (int j=x+1;j<=m;j++)

                for (int k=y-1;k;k--)

                {

                    if (v[j][k])

                        break;

                    v[j][k]=true;

                }

            for (int j=x-1;j;j--)

                for (int k=y+1;k<=n;k++)

                {

                    if (v[j][k])

                        break;

                    v[j][k]=true;

                }

        }

    }

    return 0;

}

巴特西

【bzoj3671】[Noi2014]随机数生成器

最新文章

热门文章