Codeforces - 1033C - Permutation Game - 简单dp - 简单数论
2024-08-27 22:19:30
https://codeforces.com/problemset/problem/1033/C
一开始觉得自己的答案会TLE,但是吸取徐州赛区的经验去莽了一发。
其实因为下面这个公式是 $O(nlogn)$ 的,不是 $O(n²)$ ,所以这样做是可行的。学到了新的知识。
$$\sum\limits_{i=1}^{n}\lfloor\frac{n}{i}\rfloor$$
PS:学会LaTeX啦!
#include<bits/stdc++.h>
using namespace std;
#define ll long long int res[];
int p[];
int a[]; int n;
void solve(int num,int c){
for(int k=;p[num]+k*num<=n;k++){
if(a[p[num]+k*num]>num){
if(res[a[p[num]+k*num]]==){
//存在一种转移到先手赢的情况?不应该让对方赢
//存在一种转移到先手输的情况,转移过去自己就赢了
//printf("%d can move to %d\n",num,a[p[num]+k*num]);
res[num]=;
return;
}
}
}
for(int k=;p[num]-k*num>=;k++){
if(a[p[num]-k*num]>num){
if(res[a[p[num]-k*num]]==){
//存在一种转移到先手赢的情况?不应该让对方赢
//存在一种转移到先手输的情况,转移过去自己就赢了
//printf("%d can move to %d\n",num,a[p[num]-k*num]);
res[num]=;
return;
}
}
}
} int main(){
scanf("%d",&n);
for(int i=;i<=n;i++){
scanf("%d",&a[i]);
p[a[i]]=i;
} res[n]=;
//先手赢=false
for(int i=n-;i>=;i--){
res[i]=;
//一开始假设没办法转移,先手赢=false
solve(i,'A');
if(res[i]==){
//printf("%d cannot move\n",i);
}
} for(int i=;i<=n;i++){
int t=a[i];
if(res[t]==){
printf("A");
}
else{
printf("B");
}
} printf("\n");
}
2019-01-16
最新文章
- CentOS7之按时间段截取指定的Tomcat日志到指定文件的方法
- How To Use Goto?
- 转-squid介绍及其简单配置
- 【转】aspx与aspx.cs的关系
- 警惕USB键盘记录器
- netty 粘包问题处理
- 【2013微软面试题】输出节点数为n的二叉树的所有形态
- Python 基础【第八篇】变量
- 《Linux设备驱动开发详解(第2版)》配套视频登录51cto教育频道
- CSS元素分类及区别
- C#,.net获取字符串中指定字符串的个数、所在位置与替换字符串
- 小代码编写神器:LINQPad 使用入门
- HTML5扩展之微数据与丰富网页摘要itemscope, itemtype, itemprop
- 获取打开文件的PID
- cudaMemcpy与cudaMemcpyAsync的区别
- Asp .Net MVC4笔记之目录结构
- Python 3.7 将引入 dataclass 装饰器
- ImitateUCM项目启动Tomcat的过程
- 应对WannaCry勒索危机之关闭445端口等危险端口——以本人Windows7系统为例
- 【python练习题】程序17
热门文章
- Service具体解释(一):什么是Service
- php-cpp用来开发php的拓展
- hdu 1710 Binary Tree Traversals 前序遍历和中序推后序
- 在OpenStack中绕过或停用security group (iptables)
- HDU 3420 Bus Fair [补]
- 项目记录26--unity-tolua框架 View03-UIManager.lua
- IPv4与IPv6数据报格式
- 记一次OGG数据写入HBase的丢失数据原因分析
- Designing a RESTful API with Python and Flask 201
- 【POJ3740】Easy Finding DLX(Dancing Links)精确覆盖问题