C. Permutation Game

http://codeforces.com/contest/1033/problem/C

题意:

  一个排列,每个位置i走到的位置j满足:a[j]>a[i],(j-i)是a[i]的倍数。问从每个位置开始,是否有必胜策略。

分析:

  博弈论+拓扑。

  由于是一个排列,那么可以枚举每个数,判断这个位置的a是否大于它,如果可以连边。这样的复杂度是$nlogn$的。

  然后对于一些无路可走的点,这是必败态,根据必胜和必败的定义:必胜态的后继状态中存在至少一个必败态,必败态的后继状态全是必胜态。

  然后建反图,在DAG上拓扑。

代码:

 #include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<iostream>
#include<cctype>
#include<set>
#include<vector>
#include<queue>
#include<map>
#define fi(s) freopen(s,"r",stdin);
#define fo(s) freopen(s,"w",stdout);
using namespace std;
typedef long long LL; inline int read() {
int x=,f=;char ch=getchar();for(;!isdigit(ch);ch=getchar())if(ch=='-')f=-;
for(;isdigit(ch);ch=getchar())x=x*+ch-'';return x*f;
} const int N = ;
int a[N], deg[N], q[N], f[N];
vector<int>T[N]; int main() {
int n = read();
for (int i=; i<=n; ++i) a[i] = read(); for (int i=; i<=n; ++i) {
for (int j=i+a[i]; j<=n; j+=a[i])
if (a[j] > a[i]) T[j].push_back(i), deg[i] ++;
for (int j=i-a[i]; j>=; j-=a[i])
if (a[j] > a[i]) T[j].push_back(i), deg[i] ++;
} int L = , R = ;
memset(f, -, sizeof(f));
for (int i=; i<=n; ++i)
if (!deg[i]) q[++R] = i, f[i] = ; while (L <= R) {
int u = q[L ++];
for (int sz=T[u].size(),i=; i<sz; ++i) {
int v = T[u][i];
if (f[v] == -) {
if (f[u] == ) f[v] = ;
else f[v] = ;
}
else {
if (f[u] == ) f[v] = ;
}
deg[v] --;
if (!deg[v]) q[++R] = v;
}
}
for (int i=; i<=n; ++i) {
if (f[i]) putchar('A');
else putchar('B');
}
return ;
}

最新文章

  1. J2EE应用监控后台执行SQL
  2. android知识杂记(一)
  3. Android之Activity启动模式
  4. Windows Azure&#174; 由世纪互联运营发布MySQL Database on Azure正式商用版
  5. Android支付接入(四):联通VAC计费
  6. C# Delegate 异步调用
  7. loading.io一个loading图标网站,跟大家分享
  8. 复习交换代数——Noether正规化
  9. Spring Boot 学习之路二 配置文件 application.yml
  10. 【原创】大叔问题定位分享(18)beeline连接spark thrift有时会卡住
  11. JavaWeb项目三要素
  12. jcifs windows 域账户单点登录(转)
  13. Python人工智能第二篇
  14. NDK/JNI学习--环境搭建
  15. 推荐一个 .Net Core 的 Redis 库
  16. php中经常使用的string函数
  17. 小学四则运算APP 第一个冲刺阶段 第五天
  18. 10个实用的Django建议(转)
  19. 牌型种数|2015年蓝桥杯B组题解析第七题-fishers
  20. 合成冷色黑暗恐怖魔法师图片的PS教程

热门文章

  1. Hibernate映射Map属性2
  2. [19/04/03-星期三] IO技术_其它流(RandomAccessFile 随机访问流,SequenceInputStream 合并流)
  3. 使用npm uninstall卸载express无效
  4. springboot启动报错:Could not resolve placeholder
  5. CSS技巧之向下箭头
  6. iOS:UICollectionView流式布局及其在该布局上的扩展的线式布局
  7. Zabbix——创建网络配置模板
  8. mongo配置项说明
  9. Ubuntu下Zabbix结合percona监控mysql数据
  10. Tornado异步与延迟任务