首页 > 代码库 > CF154D. Flatland Fencing [博弈论 对称 平局]
CF154D. Flatland Fencing [博弈论 对称 平局]
传送门
题意：
背景是$knights‘ tournament$，好棒的样子！
这道题不一样很恶心的地方就是有平局的存在
首先判断能不能一步杀
不能的话，如果可以走$0$步或者$a,b$一负一正那么一定会平局，因为这时候两人移动范围相同肯定不会去送死啊
剩下的，可以简化成，有$d=|x_1-x_2|$个石子，每人每次可以取$[a,b]$个，谁取完最后一颗就胜利
这时候$SG$定理显然没什么用，应该往“对称”方向考虑
发现一个$a+b$一定可以两人走完
然后按照$d%(a+b)$的结果分类
注意如果处在$[1,a-1] \bigcup [b+1,a+b-1]$也是平局！
#include <iostream>#include <cstdio>#include <cstring>#include <algorithm>#include <cmath>using namespace std;const int N=1005;inline int read(){ char c=getchar();int x=0,f=1; while(c<‘0‘||c>‘9‘){if(c==‘-‘)f=-1; c=getchar();} while(c>=‘0‘&&c<=‘9‘){x=x*10+c-‘0‘; c=getchar();} return x*f;}int x1,x2,a,b,f=1;void solve(){ if(x1+a<=x2 && x2<=x1+b) {puts("FIRST"),printf("%d\n",x2);return;} if(a==0 || b==0) {puts("DRAW");return;} if(a<0 && b>0) {puts("DRAW");return;} if(a>0){ if(x1>x2) {puts("DRAW");return;} }else{ if(x1<x2) {puts("DRAW");return;} a=-a;b=-b;swap(a,b);f=-1; } int d=abs(x1-x2),t=d%(a+b);//printf("d %d %d\n",d,t); if(t==0) puts("SECOND"); else if(a<=t&&t<=b) puts("FIRST"),printf("%d\n",x1+t*f); else puts("DRAW");}int main(){ //freopen("in","r",stdin); x1=read();x2=read();a=read();b=read(); solve();}
CF154D. Flatland Fencing [博弈论 对称 平局]
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。