bzoj 3671 随机数生成器 —— 暴力
2024-10-21 15:44:50
题目:https://www.lydsy.com/JudgeOnline/problem.php?id=3671
原来256M是可以开两个3e7的数组的;
因为答案只有 n+m-1 个数,所以暴力判断能否放即可,不用线段树;
然而 O(n) 判断 O(1) 修改和 O(1) 判断 O(n) 修改是不同的。呵呵。
代码如下:
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long ll;
int const xn=,xxn=,xm=5e4+;
int n,m,t[xxn],ps[xxn],mn[xn],mx[xn];
int rd()
{
int ret=,f=; char ch=getchar();
while(ch<''||ch>''){if(ch=='-')f=; ch=getchar();}
while(ch>=''&&ch<='')ret=ret*+ch-'',ch=getchar();
return f?ret:-ret;
}
int mnn(int x,int y){return x<y?x:y;}
int mxx(int x,int y){return x<y?y:x;}
int main()
{
int xx=rd(),a=rd(),b=rd(),c=rd(),d=rd();
n=rd(); m=rd(); int Q=rd();
for(int i=;i<=n*m;i++)t[i]=i;
for(int i=;i<=n*m;i++)
{
xx=((ll)a*xx*xx+(ll)b*xx+c)%d;//!%d
swap(t[i],t[xx%i+]);
}
for(int i=,u,v;i<=Q;i++)u=rd(),v=rd(),swap(t[u],t[v]);
for(int i=;i<=n*m;i++)ps[t[i]]=i;
for(int i=;i<=m;i++)mn[i]=,mx[i]=n;
int num=;
for(int i=,x,y;i<=n*m;i++)
{
x=(ps[i]-)/m+; y=(ps[i]-)%m+;
if(mn[y]>x||mx[y]<x)continue;
printf("%d ",i); num++;
if(num==n+m-)break;
for(int i=;i<y;i++)mx[i]=mnn(mx[i],x);
for(int i=y+;i<=m;i++)mn[i]=mxx(mn[i],x);
}
puts("");
return ;
}
最新文章
- ABP中使用Redis Cache(2)
- linux命令**50
- 关于tableView的优化
- 设计模式之工厂模式(Factory)
- Golang学习 - bufio 包
- Project Euler 86:Cuboid route 长方体路径
- BNUOJ-26586 Simon the Spider 最小生成树+枚举
- OC中-方法到底是如何使用的?
- codeforce 651B Beautiful Paintings
- OpenOffice 服务开机启动
- .NET 中易混淆的概念(Delegate vs Event)
- HDU 5811 Colosseo
- motan负载均衡/zookeeper集群/zookeeper负载均衡的关系
- (五)SpringBoot2.0基础篇- Mybatis与插件生成代码
- SQL Server 创建索引
- Python3自定义日志类教程
- 纯CSS3实现打火机火焰动画
- Fiddler 抓包https配置 提示:creation of the root certificate was not successful 证书安装不成功
- oracle数据类型表
- git关于 LF 与 CRLF