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

Time Limit: 50 Sec  Memory Limit: 256 MB

Submit: 2098  Solved: 946

[Submit][Status][Discuss]

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 Input

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

Sample Output

1 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×

Source

这题究竟是几个意思???

为了科普随机化算法??(雾)

字典序最小?那不就是贪心走小的就行了么?

顺便维护一下每一个$x$,对应那些$y$是能选的

选了一个数之后它左下和右上的矩阵就都不能选了

#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; 
inline int read() {
    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
    X0 = read(); a = read(), b = read(), c = read(), d = read();
    N = read(); M = read(); Q = read();
    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]);    
    while(Q--) {int x = read(), y = read(); swap(A[x], A[y]);}
    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;
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏函数式编程语言及工具

Scalaz(18)- Monad: ReaderWriterState-可以是一种简单的编程语言

  说道FP,我们马上会联想到Monad。我们说过Monad的代表函数flatMap可以把两个运算F[A],F[B]连续起来,这样就可以从程序的意义上形成一种串...

2027
来自专栏软件开发

JavaSE学习总结(八)—— 异常处理(Exception)

一、理解异常及异常处理的概念 异常就是在程序的运行过程中所发生的不正常的事件,它会中断正在运行的程序。 异常不是错误 程序中关键的位置有异常处理,提高程序的稳定...

2339
来自专栏小工匠技术圈

【小工匠聊密码学】-- Base64算法

1443
来自专栏鸿的学习笔记

简单定义Python和Scala的类和对象

在现代编程语言里,类和对象都是绕不过的话题。对象这个概念可以是生活的抽象,为了更好的理解使用书来做比喻,每一本书都是一个对象,也就是一个实例,书本身具有的页码等...

821
来自专栏C/C++基础

C++运算符重载形式——成员函数or友元函数

运算符重载是C++多态的重要实现手段之一。通过运算符重载对运算符功能进行特殊定制,使其支持特定类型对象的运算,执行特定的功能,增强C++的扩展功能。

1082
来自专栏数据之美

简化你的 java 字符串操作:Guava 之 CharMatcher 用法简介

对字符串的处理应该是编程活动中最频繁的操作了,而原生的 JDK 以及 Java 本身的语法特性使得在 Java 中进行字符串操作是一件极其麻烦的事情,如果你熟...

3318
来自专栏李蔚蓬的专栏

Java基础知识的全面巩固_note1(附各种demo code)

上面的cmd中,javac程序是一个Java编译器,它将文件Welcome.java编译成Welcome.class.java程序启动Java虚拟机。虚拟机执行...

942
来自专栏猿人谷

获取对象属性类型、属性名称、属性值的研究:反射和JEXL解析引擎

先简单介绍下反射的概念:java反射机制是在运行状态中,对于任意一个类,都能够知道这个类的所有属性和方法;对于任意一个对象,都能够调用它的任意方法和属性;这种动...

1.3K5
来自专栏Java进阶之路

Java8 Optional 的正确使用方式

1900
来自专栏Spring相关

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

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

1052

扫码关注云+社区

领取腾讯云代金券