CSDN 同步
原题链接 https://www.luogu.com.cn/problem/P6270
POJ 链接 http://poj.org/problem?id=1067
简要题意:
双方轮流拿石子, 共两堆石子, 每次可以拿去一堆中的任意个或者两堆中的相同多个. 先走方是否一定能获胜 (失败)?
博弈论经典: 威佐夫博弈 模板题.
显然, 我们用 \(P\) 态表示必败态,\(A\) 态表示必胜态, 用 \(f_{x,y}\) 表示两堆分别为 \(x\) 个和 \(y\) 个的状态. 显然:
\[f_{x,y} \in \bigg( A,P \bigg) \]
然后, 先规定边界:
\[f_{0,0} = P , f_{0,x} = f_{x,0} = A \]
且
\[f_{x,y} = f{y,x} \]
我们只需考虑 \(x<y\) 的情况.
去处边界,\(f_{1,2} = P\), 这是显然的, 你无论如何都是输.
然后,\(f_{1,k} = A(k>2)\), 这是因为, 你只要把 \(k\) 个石子降为 \(2\) 个石子, 然后对方是先手,\(\because f_{1,2} = P\),\(\therefore f_{1,k} = A(k> 2)\). 其中式子中可以认为 \(P=0,A=1\).
同理,\(f_{2,k} = A(k>1)\), 因为 \(f_{2,1} = P\), 把 \(k\) 堆石子弄成一堆就行.
从上面可以看出, 如果把 \(f_{x,y}\) 写在平面直角坐标系上, 那么 每一列只有一个 \(P\) 态 (因为其它的都转移成它).
我们继续寻找 \(f_{3,k} = P\) 的 \(k\) 值.
下面, 我们用 \(x^1\) 表示 \(x\) 状态的取反值.(取反即 \(P \gets A\),\(A \gets P\))
- \[f_{
- 3,4
- } = f(1,2)^1 = P^1 = A \]
- \[f_{
- 3,5
- }=\max(f_{
- 3,4
- },f_{
- 3,3
- },f_{
- 2,4
- },f_{
- 1,3
- })^1 = A^1 = P \]
\(\max\) 即在所有状态中取最优解 (能赢则赢, 全输则输).
因此,\(f_{1,2}\),\(f_{3,5}\) 是 \(P\) 态.
然后经过类似枚举发现:(其实是用电脑动态规划打表的)
\(f_{1,2} , f_{3,5},f_{4,7},f_{6,10},f_{8,13} = P\)
这时我们大概发现了一点规律.
首先, 第 \(i\) 个 \(P\) 态一定是 \(f_{x,x+i}\) 的形式.
你发现这个数列有极了规律.
第 \(i\) 个 \(P\) 态应当时 \(f(m_i,m_i+i)\), 其中 \(m_i\) 表示前 \(i-1\) 个 必败态中未出现的最小数.
什么意思? 比方说, 第 \(3\) 个 \(P\) 态.
前面出现过 \(1,2,3,5\),\(\therefore\) 就是 \(f_{4,4+3} = f_{4,7}\)
然后, 给出一段伪代码, 求出前 \(1\) ~ \(10^5\) 的 \(P\) 态.
- freopen("data.txt","w",stdout);
- bool h[1000001]; int last=1; //last 表示上次出现的位置, 用来优化搜索, 保证线性
- memset(h,0,sizeof(h)); // 桶清 0
- for(int i=1;i<=100000;i++) {
- for(int j=last;j<=INT_MAX;j++)
- if(!h[j]) {
- last=j; h[j]=1; h[j+i]=1;
- printf("%d %d\n",j,j+i);
- break;
- }
- }
时间复杂度是 \(O(10^5)\), 然后我们得到一个表:
打表真快乐 https://paste.ubuntu.com/p/xddFww45Tq/
(如果你想分析, 也可以试着分析一下这种大数据)
(天哪, 你不会以为我想把 \(10^9\) 的表滚出来然后交吧, 不好意思)
然后经过 看题解 分析发现:
\[m_i = i \times \frac{1 + \sqrt{5}}{2} \]
然后直接判断即可.
时间复杂度:\(O(n)\).
期望得分;\(100pts\).
实际得分:\(90pts\).(始终不知道怎么错的, 但 \(\texttt{POJ}\) 上交是 \(\text{AC}\) 的)
- #include<math.h>
- #include<cstdio>
- #include<iostream>
- #include<cstring>
- using namespace std;
- typedef long long ll; // 后来调试无果开了 long long
- inline ll read(){char ch=getchar();int f=1;while(ch<'0' || ch>'9') {if(ch=='-') f=-f; ch=getchar();}
- ll x=0;while(ch>='0' && ch<='9') x=(x<<3)+(x<<1)+ch-'0',ch=getchar();return x*f;}
- int main(){
- ll a,b;
- while(scanf("%lld%lld",&a,&b)!=EOF) {
- if(a<b) swap(a,b);
- a=(int)((a-b)*(1+sqrt(5))/2.0);
- if(a==b) puts("0");
- else puts("1");
- }
- return 0;
- }
来源: http://www.bubuko.com/infodetail-3489213.html