UOJ #6.[NOI2014]随机数生成器 | Kyons'Blog 




 
 
 
 



 
 



UOJ #6.[NOI2014]随机数生成器

这个题,难在阅读.

题目大意

跳过!
链接:🔗

解析

  1. 首先根据题目得到一个随机数列$\lbrace x_i=(a×x_{i−1}^2+b×x_{i−1}+c)$mod$d\rbrace$其中$i\in{1…n×m}$
  2. 搞一个数列$T$,其中$T_i=i$,$i\in{1….n×m}$
  3. 对每一项$T_i$,我们$swap(T_i,$$T_{x_imodi+1})$
  4. 以上$3$步结束后,得到的就是棋盘要填的数$T_i$

样例一数据生成的棋盘如下:

12917
51162
41038

  路线便是$12->9->1->6->2->8$
  一个有技巧的贪心来选数.
  首先,$map[1][1]$必定选.
  如果我们不考虑棋盘顺序,若要序列最小,显然是选最小数的放进去,那么我们便从$1$这个数开始贪心.
那么,这个数我们什么时候才取它呢?
  根据题目要求,我们从左上角到右下角,只能向右或者向下走,只要选过的数在要选的数左上方或右下方的时候,这个数才是可选的,或者说是可到达的.
  假设当我们要选$9$时,我们已经选了$1,2,6,8,12$,我们看$9$能否到达呢?
  显然,左侧离它最近的数要$\ge$它的行,右侧离它最近的数要$\leq$它的行.这样我们就可以选它.
  当然,选完后更新$L[],R[]$.

即代码:

1
2
3
4
5
6
7
8
9
10
11
12
//x为行,y为列
//n行,m列
for (int i = 1; i <= n; i++)
L[i] = 1 ,R[i] = m;
for (int i = 1; i <= n * m; i++){
L[x] <= y && y <= R[x]
for (int j = 1; j < x; j++)
R[j] = min(R[j], y);

for (int j = n; j > x; j--)
L[j] = max(L[j], y);
}

  理解了这个贪心,题目就很水了.
  据说要注意空间,时间…..全程cin好像没啥事.

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
54
#include <algorithm>
#include <iostream>
using namespace std;

typedef long long ll;

const int INF = 1e7;
const int MAXN = 5e3 + 10;

int T[MAXN * MAXN], l[MAXN * MAXN], R[MAXN], L[MAXN];

int main()
{
int a, b, c, d;
int n, m, q;
cin >> l[0] >> a >> b >> c >> d >> n >> m >> q;

for (int i = 1; i <= m * n; i++)
T[i] = i, l[i] = (1LL * a * l[i - 1] * l[i - 1] + 1LL * b * l[i - 1] + c) % d;

for (int i = 1; i <= n * m; i++)
swap(T[i], T[l[i] % i + 1]);

int x, y;
for (int i = 0; i < q; i++) {
cin >> x >> y;
swap(T[x], T[y]);
}

for (int i = 1; i <= n * m; i++)
l[T[i]] = i;

for (int i = 1; i <= n; i++)
R[i] = m, L[i] = 1;

for (int i = 1, sum = 0; i <= n * m; i++) {
x = (l[i] - 1) / m + 1, y = l[i] % m ? l[i] % m : m;

if (L[x] <= y && y <= R[x]) {
cout << i << ' ';
sum++;
if (sum == n * m - 1)
break;

for (int j = 1; j < x; j++)
R[j] = min(R[j], y);

for (int j = n; j > x; j--)
L[j] = max(L[j], y);
}
}

return 0;
}

 


 
 
 





 

 


 


 

 

 

 

 
 

 

 

 //删除Valine核心代码库外链调用 //调用刚下载的本地文件以加速加载速度 //这里改为从本地加载