【随机化】Petrozavodsk Summer Training Camp 2016 Day 5: Petr Mitrichev Contest 14, Saturday, August 27, 2016 Problem I. Vier
2024-08-25 04:58:34
给你一个1~n的排列,让你找出4个下标a b c d,满足
(a+b)%n=(c+d)%n
(w(a)+w(b))%n=(w(c)+w(d))%n,并且是非平凡解。
发现对于每个数i,找出两个数和为其的数量大概是O(n),于是可以随机找,压到vector里存下,直到找到一个解为止。
#include<cstdio>
#include<cstdlib>
#include<vector>
using namespace std;
int n,a[1000010];
vector<int>b[1000010],c[1000010];
int main(){
freopen("vier.in","r",stdin);
freopen("vier.out","w",stdout);
srand(233);
scanf("%d",&n);
for(int i=1;i<=n;++i){
scanf("%d",&a[i]);
}
while(1){
int A=rand()%n+1;
int B=rand()%n+1;
int t=(A+B+a[A]+a[B])%n;
for(int i=0;i<b[t].size();++i){
if((A+B)%n==(b[t][i]+c[t][i])%n && (a[A]+a[B])%n==(a[b[t][i]]+a[c[t][i]])%n && !(A==b[t][i] && B==c[t][i]) && !(A==c[t][i] && B==b[t][i])){
puts("Ja");
printf("%d %d %d %d\n",A,B,b[t][i],c[t][i]);
return 0;
}
}
b[t].push_back(A);
c[t].push_back(B);
}
return 0;
}
最新文章
- Basic Tutorials of Redis(3) -Hash
- U8采购订单联查采购入库单
- C#冒泡排序法
- HIbernate的基本包——八个,详细条目
- RocEDU.阅读.写作
- ax 的错误处理范例
- gcd 最大公约数 模版!
- 使用Codis搭建redis集群服务
- 表单javascript checkbox全选 反选 全不选
- React模块化开发
- JavaScript遍历对象-总结一
- Scratch 2.0-Find The Mouse 发布!
- Spring Data JPA框架
- 查看和指定SpringBoot内嵌Tomcat的版本
- mysql知识积累
- CPU IO MEM NETWork 监控命令
- shell中$(( ))、$( )与${ }的区别
- R12_专题知识总结提炼-AP模块
- NetCore偶尔有用篇:NetCore项目发布为Nuget包
- NodeJS-001-Nodejs学习文档整理(转-出自http://www.cnblogs.com/xucheng)