2017年6月

这道题不要用C++11,否则luogu上T好几个点
题面见题目传送门

首先,因为$N,M \leq 5000$,所以$ O(nm)$ 的求$T_i$ 的纯模拟算法时限完全没有问题。
接着就是求路径序列了:千万注意要好好读题
字典序最小” “从小到大排序”说明什么?要贪心做!
那么我们如何贪心呢?
直观地想到:从小到大考虑能不能走到它。
但是直接判断的话复杂度可是会超时的啊!
假设i在第$X_i$行,$Y_i$列。
那么显然:
当i和j都可以走,当$X_i < X_j$,$Y_i \leq Y_j$,利用这个性质,我们可以简化判断。
假设i选了,则对于所有j,当$X_j < X_i$,则$Y_j \geq Y_i$ ,反之同理。于是写出代码:

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
#define up(a,b,c) for (int a(b),end##a(c);a<=end##a;++a)
#define down(a,c,b) for (int a(b),end##a(c);a>=end##a;--a)
#define uup(a,c,b) for (int a(b),end##a(c);a<=end##a;++a)
#define udown(a,b,c) for (int a(b),end##a(c);a>=end##a;--a)
using namespace std;
int read(){
    char s;
    int k=0,base=1;
    while((s=getchar())!='-'&&s!=EOF&&!(s>='0'&&s<='9'));
    if(s==EOF)exit(0);
    if(s=='-')base=-1,s=getchar();
    while(s>='0'&&s<='9'){
        k=k*10+(s-'0');
        s=getchar();
    }
    return k*base;
}
void write(int x){
    if(x<0){
        putchar('-');
        write(-x);
    }
    else{
        if(x/10)write(x/10);
        putchar(x%10+'0');
    }
}
int t[25050000],ft[25050000],lj[5050],rj[5050],n,m,q;
void myswap(int &a,int &b){
    int t=a;a=b;b=t;
}
int main(){
    long long x=read(),a=read(),b=read(),c=read(),d=read();
    n=read(),m=read(),q=read();
    int nm=n*m;
    up(i,1,nm){
        x=(x*x*a+x*b+c)%d;
        t[i]=i;
        myswap(t[i],t[(int)x%i+1]);
    }
    up(i,1,q){
        myswap(t[read()],t[read()]);
    }
    up(i,1,nm){
        ft[t[i]]=i;
    }
    up(i,1,n)lj[i]=1,rj[i]=m;
    int tt=n+m-1,h,l;
    up(i,1,nm){
        h=(ft[i]-1)/m+1;l=(ft[i]-1)%m+1;
        if(lj[h]<=l&&rj[h]>=l){//可以选
            printf("%d%c",i,--tt?' ':'\n');
            if(!tt)return 0;
            int k=h-1;
            while(k){
                rj[k]=rj[k]>l?l:rj[k];//根据性质
                --k;
            }
            k=h+1;
            while(k<=n){
                lj[k]=lj[k]<l?l:lj[k];//根据性质
                ++k;
            }

        }
    }
    return 0;
}

简述

平时写的快速读入,大多数是指一个一个字符读入,再转成数字。
但是有一种更快的方法:
强行读入整个输入文件,存在一个字符串里。
接着在这个字符串里利用快速读入转成数字。
速度非常快。





- 阅读剩余部分 -

题目简要描述

设num[i]表示既是S[1..i]的前缀又是后缀,并且前缀和后缀不重叠的字符串个数。
求$\prod_{i=1}^n (num[i]+1)=(num[1]+1)\times (num[2]+1)\times \dots \times (num[n]+1)$对$1000000007$取模的结果。
10%:|S|<=50
30%:|S|<=200
50%:|S|<=10000
100%:|S|<=1000000






- 阅读剩余部分 -