正文
[bzoj3671][Noi2014][随机数生成器] (贪心+位运算+卡空间)
提示：扫一扫查出行【扫一扫了解最新限行尾号】
复制提示
Description
Input第1行包含5个整数，依次为 x_0,a,b,c,d ，描述小H采用的随机数生成算法所需的随机种子。第2行包含三个整数 N,M,Q ，表示小H希望生成一个1到 N×M 的排列来填入她 N 行 M 列的棋盘，并且小H在初始的 N×M 次交换操作后，又进行了 Q 次额外的交换操作。接下来 Q 行，第 i 行包含两个整数 u_i,v_i，表示第 i 次额外交换操作将交换 T_(u_i )和 T_(v_i ) 的值。
Output输出一行，包含 N+M-1 个由空格隔开的正整数，表示可以得到的字典序最小的路径序列。
Sample Input1 3 5 1 71
3 4 3
1 7
9 9
4 9
Sample Output1 2 6 8 9 12
HINT
本题的空间限制是 256 MB，请务必保证提交的代码运行时所使用的总内存空间不超过此限制。
一个32位整数（例如C/C++中的int和Pascal中的Longint）为4字节，因而如果在程序中声明一个长度为 1024×1024 的32位整型变量的数组，将会占用 4 MB 的内存空间。
2≤N,M≤5000
0≤Q≤50000
0≤a≤300
0≤b,c≤108
0≤x0<d≤1081≤ui,vi≤N×M
Solution
字典序最小。。。考虑贪心咯
从小到大选数，可以就选
因为方阵中的路径是一段连续区间，我们对每次选完后剩余的数做限制，标记一下就行
#include <stdio.h>
#include <memory.h>
#define MaxN 5003
#define MaxBuf 1<<20
#define L long long
#define RG register
#define dmin(a,b) ((a)<(b)?(a):(b))
#define dmax(a,b) ((a)>(b)?(a):(b))
char B[MaxBuf],*p=B;
template<class Type>inline void Rin(RG Type &x){
x=;
while(*p<''||*p>'')p++;
while(*p>=''&&*p<='')
x=x*+*p++-'';
}
template<class Type>inline void exc(RG Type &x,RG Type &y){
RG Type z=x; x=y; y=z;
}
L x_0,a,b,c,d;
int n,m,_q,lef[MaxN],rig[MaxN],g[MaxN][MaxN],t[MaxN*MaxN];
inline int ram(){
return x_0=(a*x_0*x_0%d+b*x_0%d+c)%d;
}
inline void limina(RG int x,RG int y){
for(RG int i=;i<x;i++)
rig[i]=dmin(rig[i],y);
for(RG int i=x+;i<=n;i++)
lef[i]=dmax(lef[i],y);
}
int main(){
memset(rig,0x3f,sizeof rig);
fread(p,,MaxBuf,stdin);
Rin(x_0),Rin(a),Rin(b),Rin(c),Rin(d),Rin(n),Rin(m),Rin(_q);
for(RG int i=;i<=n*m;i++){
t[i]=i; exc(t[i],t[ram()%i+]);
}
while(_q--){
RG int x,y;
Rin(x),Rin(y);
exc(t[x],t[y]);
}
for(RG int i=;i<=n;i++)
for(RG int j=;j<=m;j++){
static size_t tim;
g[i][j]=t[++tim];
}
for(RG int i=;i<=n;i++)
for(RG int j=;j<=m;j++)
t[g[i][j]]=i<<|j;
for(RG int i=;i<=n*m;i++){
static bool adv;
RG int x=t[i]>>,y=t[i]&;
if(lef[x]<=y&&y<=rig[x]){
if(adv)
putchar(' ');
adv=true;
printf("%d",g[x][y]);
limina(x,y);
}
}
putchar('\n');
return ;
}
第1行包含5个整数，依次为 x_0,a,b,c,d ，描述小H采用的随机数生成算法所需的随机种子。第2行包含三个整数 N,M,Q ，表示小H希望生成一个1到 N×M 的排列来填入她 N 行 M 列的棋盘，并且小H在初始的 N×M 次交换操作后，又进行了 Q 次额外的交换操作。接下来 Q 行，第 i 行包含两个整数 u_i,v_i，表示第 i 次额外交换操作将交换 T_(u_i )和 T_(v_i ) 的值。
Output输出一行，包含 N+M-1 个由空格隔开的正整数，表示可以得到的字典序最小的路径序列。
Sample Input1 3 5 1 71
3 4 3
1 7
9 9
4 9
Sample Output1 2 6 8 9 12
HINT
本题的空间限制是 256 MB，请务必保证提交的代码运行时所使用的总内存空间不超过此限制。
一个32位整数（例如C/C++中的int和Pascal中的Longint）为4字节，因而如果在程序中声明一个长度为 1024×1024 的32位整型变量的数组，将会占用 4 MB 的内存空间。
2≤N,M≤5000
0≤Q≤50000
0≤a≤300
0≤b,c≤108
0≤x0<d≤1081≤ui,vi≤N×M
Solution
字典序最小。。。考虑贪心咯
从小到大选数，可以就选
因为方阵中的路径是一段连续区间，我们对每次选完后剩余的数做限制，标记一下就行
#include <stdio.h>
#include <memory.h>
#define MaxN 5003
#define MaxBuf 1<<20
#define L long long
#define RG register
#define dmin(a,b) ((a)<(b)?(a):(b))
#define dmax(a,b) ((a)>(b)?(a):(b))
char B[MaxBuf],*p=B;
template<class Type>inline void Rin(RG Type &x){
x=;
while(*p<''||*p>'')p++;
while(*p>=''&&*p<='')
x=x*+*p++-'';
}
template<class Type>inline void exc(RG Type &x,RG Type &y){
RG Type z=x; x=y; y=z;
}
L x_0,a,b,c,d;
int n,m,_q,lef[MaxN],rig[MaxN],g[MaxN][MaxN],t[MaxN*MaxN];
inline int ram(){
return x_0=(a*x_0*x_0%d+b*x_0%d+c)%d;
}
inline void limina(RG int x,RG int y){
for(RG int i=;i<x;i++)
rig[i]=dmin(rig[i],y);
for(RG int i=x+;i<=n;i++)
lef[i]=dmax(lef[i],y);
}
int main(){
memset(rig,0x3f,sizeof rig);
fread(p,,MaxBuf,stdin);
Rin(x_0),Rin(a),Rin(b),Rin(c),Rin(d),Rin(n),Rin(m),Rin(_q);
for(RG int i=;i<=n*m;i++){
t[i]=i; exc(t[i],t[ram()%i+]);
}
while(_q--){
RG int x,y;
Rin(x),Rin(y);
exc(t[x],t[y]);
}
for(RG int i=;i<=n;i++)
for(RG int j=;j<=m;j++){
static size_t tim;
g[i][j]=t[++tim];
}
for(RG int i=;i<=n;i++)
for(RG int j=;j<=m;j++)
t[g[i][j]]=i<<|j;
for(RG int i=;i<=n*m;i++){
static bool adv;
RG int x=t[i]>>,y=t[i]&;
if(lef[x]<=y&&y<=rig[x]){
if(adv)
putchar(' ');
adv=true;
printf("%d",g[x][y]);
limina(x,y);
}
}
putchar('\n');
return ;
}
输出一行，包含 N+M-1 个由空格隔开的正整数，表示可以得到的字典序最小的路径序列。
1 3 5 1 71
3 4 3
1 7
9 9
4 9
Sample Output1 2 6 8 9 12
HINT
本题的空间限制是 256 MB，请务必保证提交的代码运行时所使用的总内存空间不超过此限制。
一个32位整数（例如C/C++中的int和Pascal中的Longint）为4字节，因而如果在程序中声明一个长度为 1024×1024 的32位整型变量的数组，将会占用 4 MB 的内存空间。
2≤N,M≤5000
0≤Q≤50000
0≤a≤300
0≤b,c≤108
0≤x0<d≤1081≤ui,vi≤N×M
Solution
字典序最小。。。考虑贪心咯
从小到大选数，可以就选
因为方阵中的路径是一段连续区间，我们对每次选完后剩余的数做限制，标记一下就行
#include <stdio.h>
#include <memory.h>
#define MaxN 5003
#define MaxBuf 1<<20
#define L long long
#define RG register
#define dmin(a,b) ((a)<(b)?(a):(b))
#define dmax(a,b) ((a)>(b)?(a):(b))
char B[MaxBuf],*p=B;
template<class Type>inline void Rin(RG Type &x){
x=;
while(*p<''||*p>'')p++;
while(*p>=''&&*p<='')
x=x*+*p++-'';
}
template<class Type>inline void exc(RG Type &x,RG Type &y){
RG Type z=x; x=y; y=z;
}
L x_0,a,b,c,d;
int n,m,_q,lef[MaxN],rig[MaxN],g[MaxN][MaxN],t[MaxN*MaxN];
inline int ram(){
return x_0=(a*x_0*x_0%d+b*x_0%d+c)%d;
}
inline void limina(RG int x,RG int y){
for(RG int i=;i<x;i++)
rig[i]=dmin(rig[i],y);
for(RG int i=x+;i<=n;i++)
lef[i]=dmax(lef[i],y);
}
int main(){
memset(rig,0x3f,sizeof rig);
fread(p,,MaxBuf,stdin);
Rin(x_0),Rin(a),Rin(b),Rin(c),Rin(d),Rin(n),Rin(m),Rin(_q);
for(RG int i=;i<=n*m;i++){
t[i]=i; exc(t[i],t[ram()%i+]);
}
while(_q--){
RG int x,y;
Rin(x),Rin(y);
exc(t[x],t[y]);
}
for(RG int i=;i<=n;i++)
for(RG int j=;j<=m;j++){
static size_t tim;
g[i][j]=t[++tim];
}
for(RG int i=;i<=n;i++)
for(RG int j=;j<=m;j++)
t[g[i][j]]=i<<|j;
for(RG int i=;i<=n*m;i++){
static bool adv;
RG int x=t[i]>>,y=t[i]&;
if(lef[x]<=y&&y<=rig[x]){
if(adv)
putchar(' ');
adv=true;
printf("%d",g[x][y]);
limina(x,y);
}
}
putchar('\n');
return ;
}
1 2 6 8 9 12
本题的空间限制是 256 MB，请务必保证提交的代码运行时所使用的总内存空间不超过此限制。
一个32位整数（例如C/C++中的int和Pascal中的Longint）为4字节，因而如果在程序中声明一个长度为 1024×1024 的32位整型变量的数组，将会占用 4 MB 的内存空间。
2≤N,M≤5000
0≤Q≤50000
0≤a≤300
0≤b,c≤108
0≤x0<d≤1081≤ui,vi≤N×M
Solution
字典序最小。。。考虑贪心咯
从小到大选数，可以就选
因为方阵中的路径是一段连续区间，我们对每次选完后剩余的数做限制，标记一下就行
#include <stdio.h>
#include <memory.h>
#define MaxN 5003
#define MaxBuf 1<<20
#define L long long
#define RG register
#define dmin(a,b) ((a)<(b)?(a):(b))
#define dmax(a,b) ((a)>(b)?(a):(b))
char B[MaxBuf],*p=B;
template<class Type>inline void Rin(RG Type &x){
x=;
while(*p<''||*p>'')p++;
while(*p>=''&&*p<='')
x=x*+*p++-'';
}
template<class Type>inline void exc(RG Type &x,RG Type &y){
RG Type z=x; x=y; y=z;
}
L x_0,a,b,c,d;
int n,m,_q,lef[MaxN],rig[MaxN],g[MaxN][MaxN],t[MaxN*MaxN];
inline int ram(){
return x_0=(a*x_0*x_0%d+b*x_0%d+c)%d;
}
inline void limina(RG int x,RG int y){
for(RG int i=;i<x;i++)
rig[i]=dmin(rig[i],y);
for(RG int i=x+;i<=n;i++)
lef[i]=dmax(lef[i],y);
}
int main(){
memset(rig,0x3f,sizeof rig);
fread(p,,MaxBuf,stdin);
Rin(x_0),Rin(a),Rin(b),Rin(c),Rin(d),Rin(n),Rin(m),Rin(_q);
for(RG int i=;i<=n*m;i++){
t[i]=i; exc(t[i],t[ram()%i+]);
}
while(_q--){
RG int x,y;
Rin(x),Rin(y);
exc(t[x],t[y]);
}
for(RG int i=;i<=n;i++)
for(RG int j=;j<=m;j++){
static size_t tim;
g[i][j]=t[++tim];
}
for(RG int i=;i<=n;i++)
for(RG int j=;j<=m;j++)
t[g[i][j]]=i<<|j;
for(RG int i=;i<=n*m;i++){
static bool adv;
RG int x=t[i]>>,y=t[i]&;
if(lef[x]<=y&&y<=rig[x]){
if(adv)
putchar(' ');
adv=true;
printf("%d",g[x][y]);
limina(x,y);
}
}
putchar('\n');
return ;
}
