# BZOJ3671: [Noi2014]随机数生成器(贪心)

Time Limit: 50 Sec  Memory Limit: 256 MB

Submit: 2098  Solved: 946

[Submit][Status][Discuss]

## Sample Input

1 3 5 1 71 3 4 3 1 7 9 9 4 9

1 2 6 8 9 12

## HINT

2≤N,M≤5000

0≤Q≤50000

0≤a≤300

0≤b,c≤108

0≤x0<d≤1081≤ui,vi≤N×

## Source

```#include<cstdio>
#include<cstring>
#include<algorithm>
#include<ctime>
#include<cstdlib>
#define LL long long
using namespace std;
const int MAXN = 1e5 + 10, INF = 1e8 + 10, mod = 1e9 + 7, mod2 = 1e9 + 6;
char c = getchar(); int x = 0, f = 1;
while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}
while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
return x * f;
}
int N, M, Q, tot = 0;
LL Xi, X0, a, b, c, d;
int A[5001 * 5001], Map[5001][5001], l[MAXN], r[MAXN];
int xx[3] = {0, +1, 0}, yy[3] = {0, 0, +1};
main() {
#ifdef WIN32
///freopen("a.in", "r", stdin);
#endif
for(int i = 1; i <= N * M; i++) A[i] = i;
for(int i = 1; i <= N * M; i++) swap(A[i], A[(Xi = (a * X0 * X0 + b * X0 + c) % d) % i + 1]), X0 = Xi;

//for(int i = 1; i <= N * M; i++)    printf("%d\n", A[i]);
for(int i = 1; i <= N; i++) for(int j = 1; j <= M; j++) Map[i][j] = A[++tot];
for(int i = 1; i <= N; i++)
for(int j = 1; j <= M; j++)
A[Map[i][j]] =(i - 1) * M + j;
memset(Map, 0, sizeof(Map));

for(int i = 1; i <= N; i++) l[i] = 0, r[i] = M + 1;
for(int i = 1; i <= N * M; i++) {
int y = A[i] % M, x = A[i] / M + 1;
if(y == 0) x--, y = M;
if(y <= l[x] || y >= r[x]) continue;
printf("%d ", i);
for(int j = x - 1; j >= 1; j--) r[j] = min(y + 1, r[j]);
for(int j = x + 1; j <= N; j++) l[j] = max(y - 1, l[j]);
}
return 0;
}```

1811 篇文章120 人订阅

0 条评论

## 相关文章

2027

2339

1443

821

1082

3318

942

1.3K5

1900

### 第12章—使用NoSQL数据库—使用MongoDB+Jpa操作数据库

SpringData还提供了对多种NoSQL数据库的支持,包括MongoDB;neo4j和redis.他不仅支持自动化的repository,还支持基于模板的数...

1052