2018-2019 XIX Open Cup, Grand Prix of Korea (Division 2) GYM 102058 F SG函数
2024-10-21 06:46:12
http://codeforces.com/gym/102058/problem/F
题意:平面上n个点 两个人轮流在任意两个点之间连一条线但是不能和已有的线相交,先围成一个凸多边形的获胜,先手赢还是后手赢。
解析: 当一个顶点连了两条边,那么就可以再画一笔组成三角形,
三个点 先手胜
四个点 先手胜
五个点 后手胜
.......
画完一笔之后其实变成了两个子局面假设一边大小为 j 那么就分成了 j 和(n-j-2)两个局面 我们枚举 i 求出两部分的sg值
再用异或连接起来 就是该状态可以到达的状态。
AC代码
#include <bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define all(a) (a).begin(), (a).end()
#define fillchar(a, x) memset(a, x, sizeof(a))
#define huan printf("\n")
#define debug(a,b) cout<<a<<" "<<b<<" "<<endl
#define ffread(a) fastIO::read(a)
using namespace std;
const int maxn = 3e5+;
const int maxm = 1e4+;
const int inf = 0x3f3f3f3f;
const int mod = ;
const double epx = 1e-;
typedef long long ll;
const ll INF = 1e18;
const double pi = acos(-1.0);
int f[],sg[],s[];
int n,m,k;
void SG(int x)
{
fillchar(sg,);
for(int i=;i<=x;i++)
{
fillchar(s,);
for(int j=;j<=i-;j++)
{
s[sg[j]^sg[i--j]]=;
}
for(int j=;;j++)
if(!s[j])
{
sg[i]=j;
break;
}
}
}
int main()
{
SG();
int t;
scanf("%d",&t);
while(t--)
{
scanf("%d",&n);
if(sg[n])
printf("First\n");
else
printf("Second\n");
}
}
最新文章
- [转]SpringMVC+Hibernate+Spring 简单的一个整合实例
- NUnit-Console 命令行选项详解
- 20150624_Andriod _web_service_匹配
- 1-NPM
- MAVEN ERROR: unable to find valid certification path to requested target 解决办法
- ArcGIS学习记录&mdash;属性表的编辑与修改
- busbox编译出错,arm-linux-未找到命令
- 高效操作DOM
- js实现的文章输入检查与测速。(纯js版本)
- jenkins coding.net webhook plugin
- ajax天气查询
- DirectFB 之 动画播放初步
- 南京邮电大学java程序设计作业在线编程第三次作业
- C# string数组转int数组(转载)
- Struts2_配置文件
- CSS属性大全
- _map
- 百练1041-反反复复-2016正式C题
- eclipse中ant打war包
- warning: ignoring option PermSize=256m; support was removed in 8.0
热门文章
- 【HEVC简介】Inter Prediction Tools
- 用JS获取Html中所有图片文件流然后替换原有链接
- Architecture:架构 元素与关系
- scroll offset &; client总结
- python struct.pack方法报错argument for &#39;s&#39; must be a bytes object 解决
- import downloadjs from &#39;downloadjs&#39; 如果是自己写的函数 没用默认导出 记得加花括号 例如 import { download } from &#39;./data.js&#39;
- 运行外部exe
- OSI七层模型和TCP/IP五层模型详解
- 【搜索】P1219 八皇后
- 最短路 || POJ 1511 Invitation Cards