首页 > 代码库 > BZOJ 3671 NOI 2014 随机数生成器 贪心
BZOJ 3671 NOI 2014 随机数生成器 贪心
题目大意:实在是太难说明了,自己看pdf吧。。
思路:优先按照它说明的方法处理数组,然后为了让数列中尽可能多的出现小的数字,所以1是必须要出现的,这样才能使整个数列的排序后字典序最小。我们思考,如果2也能在这个数列中那就最好不过了,但是2有可能不在这个数列里,就是2在走了1就不可能走的地方的话,就不能走2了。所以从小到大枚举数字,如果当前数字能走,就输出,然后标记所有走了这个节点就不能走的节点。空间比较紧,5000*5000可以开int*2+bool*1,极限了。。
CODE:
#include <cstdio> #include <algorithm> #define MAX 5010 using namespace std; long long seed,a,b,c,d; int arr[MAX * MAX],map[MAX][MAX]; bool v[MAX][MAX]; int ans[MAX << 1]; int m,n,asks; inline int GetX(); int main() { scanf("%lld%lld%lld%lld%lld%d%d%d",&seed,&a,&b,&c,&d,&m,&n,&asks); for(int i = 1;i <= m * n; ++i) arr[i] = i,swap(arr[i],arr[GetX() % i + 1]); for(int x,y,i = 1;i <= asks; ++i) { scanf("%d%d",&x,&y); swap(arr[x],arr[y]); } for(int i = 1;i <= m; ++i) for(int j = 1;j <= n; ++j) map[i][j] = arr[(i - 1) * n + j]; for(int i = 1;i <= m; ++i) for(int j = 1;j <= n; ++j) arr[map[i][j]] = (i - 1) * n + j; for(int i = 1;i <= m * n; ++i) { int x = arr[i] / n + 1 - (arr[i] % n == 0); int y = arr[i] - (x - 1) * n; if(!v[x][y]) { if(i != 1) putchar(' '); printf("%d",i); for(int j = x + 1;j <= m; ++j) for(int k = y - 1;k > 0; --k) { if(v[j][k]) break; v[j][k] = true; } for(int j = x - 1;j > 0; --j) for(int k = y + 1;k <= n; ++k) { if(v[j][k]) break; v[j][k] = true; } } } return 0; } inline int GetX() { return seed = (a * seed * seed % d + b * seed % d + c) % d; }
BZOJ 3671 NOI 2014 随机数生成器 贪心
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。