【NOI2014】随机数生成器

  • 本文为博主原创，未经许可不得转载

NOI居然有这么水的题目

按照题目要求生成地图之后，从小到大枚举数，判断能不能选并更新每行选数的范围

注意此题卡空间，只够开2个5000*5000的数组，所以要循环利用

时间复杂度$O(n^2)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#include<bits/stdc++.h>
#define FILE "read"
#define MAXN 5010
#define cmax(a,b) a=max(a,b)
#define cmin(a,b) a=min(a,b)
using namespace std;
typedef long long ll;
int n,m,Q,Up[MAXN],Dn[MAXN],ans[MAXN*2],x[MAXN*MAXN],T[MAXN*MAXN];
inline int read(){
    int x=0,f=1;  char ch=getchar();
    while(!isdigit(ch))  {if(ch=='-')  f=-1;  ch=getchar();}
    while(isdigit(ch))  {x=x*10+ch-'0';  ch=getchar();}
    return x*f;
}
void updata(int a,int b){
    for(int i=1;i<=n;++i){
        if(i<a) cmin(Up[i],b);
        if(i>a) cmax(Dn[i],b);
    }
}
int main(){
    //freopen(FILE".in","r",stdin);
    //freopen(FILE".out","w",stdout);
    x[0]=read(); ll a=read(),b=read(),c=read(),d=read();
    n=read();  m=read();  Q=read();
    for(int i=1;i<=n;++i) Up[i]=m;
    for(int i=1;i<=n*m;++i){
        x[i]=x[i-1]*(a*x[i-1]+b)%d+c;
        x[i]%=d;
        T[i]=i;
    }
    for(int i=1;i<=n*m;++i) swap(T[i],T[(x[i]%i)+1]);
    for(int i=1;i<=Q;++i){
        int u=read(),v=read();
        swap(T[u],T[v]);
    }
    for(int i=1;i<=n*m;++i) x[T[i]]=i;
    for(int i=1;i<=n*m;++i){
        int a=x[i]/m,b=x[i]%m;
        if(x[i]%m) a++;
        if(!b) b+=m;
        if(b<=Up[a]&&b>=Dn[a]){
            updata(a,b);
            ans[++ans[0]]=i;
            if(ans[0]==n+m-1) break;
        }
    }
    for(int i=1;i<=ans[0];++i){
        printf("%d",ans[i]);
        if(i!=ans[0]) printf(" ");
    }
    return 0;
}

本文标题:【NOI2014】随机数生成器

文章作者:chty

发布时间:2017年05月28日 - 21时01分

最后更新:2018年06月08日 - 18时50分

许可协议:本文为博主原创，未经许可不得转载。

文章目录
,