首页 > 代码库 > 【bzoj3671】[Noi2014]随机数生成器 贪心
【bzoj3671】[Noi2014]随机数生成器 贪心
题目描述
.jpg)
输入
第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 ) 的值。
输出
输出一行，包含 N+M-1 个由空格隔开的正整数，表示可以得到的字典序最小的路径序列。
样例输入
1 3 5 1 71
3 4 3
1 7
9 9
4 9
样例输出
1 2 6 8 9 12
题目大意
给定你一个用乱七八糟的方法生成的n*m的矩阵，矩阵中的元素是1~n*m的全排列，问从左上走到右下的路径中，把经过的元素从小到大排序后得到的字典序最小的路径是什么
题解
贪心
其实我真不知道出题人是怎么想的，题目描述搞得和数论似的，结果目的就是给出这个序列 = =
显然要考虑从小到大的n*m个数，如果能选就选，选了就更新其它不能选的位置。
如果一个点被选择，那么它的严格左下方和严格右上方的点都不能被选择，开一个标记数组记录它。
如果扫到一个点，它已经被标记过，那么它的左下（或右上）的点一定都被标记过。适当终止循环，时间复杂度是均摊$O(nm)$的。
但是本题卡内存差评，所以不能开数组记录每次的x，标记数组必须开成bool的等等。
另外本题需要使用桶排序，否则会TLE。
#include <cstdio>#include <cstring>#include <algorithm>using namespace std;int val[25000010] , pos[25000010];bool tag[5010][5010];int main(){ int a , b , c , d , n , m , k , q , i , jx , jy , px , py , cnt = 0; long long x; scanf("%lld%d%d%d%d%d%d%d" , &x , &a , &b , &c , &d , &n , &m , &q) , k = n * m; for(i = 1 ; i <= k ; i ++ ) val[i] = i , x = (a * x * x + b * x + c) % d , pos[i] = (int)x; for(i = 1 ; i <= k ; i ++ ) swap(val[i] , val[pos[i] % i + 1]); while(q -- ) scanf("%d%d" , &px , &py) , swap(val[px] , val[py]); for(i = 1 ; i <= k ; i ++ ) pos[val[i]] = i; for(i = 1 ; i <= k ; i ++ ) { px = (pos[i] - 1) / m + 1 , py = (pos[i] - 1) % m + 1; if(!tag[px][py]) { printf("%d%c" , i , ++cnt == n + m - 1 ? ‘\n‘ : ‘ ‘); if(py > 1) { for(jx = px + 1 ; jx <= n ; jx ++ ) { if(tag[jx][py - 1]) break; for(jy = py - 1 ; jy >= 1 ; jy -- ) { if(tag[jx][jy]) break; tag[jx][jy] = 1; } } } if(py < m) { for(jx = px - 1 ; jx >= 1 ; jx -- ) { if(tag[jx][py + 1]) break; for(jy = py + 1 ; jy <= m ; jy ++ ) { if(tag[jx][jy]) break; tag[jx][jy] = 1; } } } } } return 0;}
【bzoj3671】[Noi2014]随机数生成器 贪心
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。