题意：两人取一堆石子，石子有n个。 先手第一次不能全部取完但是至少取一个。之后每人取的个数不能超过另一个人上一次取的数的K倍。拿到最后一颗石子的赢。先手是否有必胜策略？若有，先手第一步最少取几个？ 先来篇论文 再来篇博客（感觉人家讲的比我好，我就不献丑了）
#include<cstdio> #include<cstring> #include<iostream> #include<algorithm> using namespace std; const int maxn=1e6+10; int a[maxn],b[maxn]; int main() { int ncase,Z=0; scanf("%d",&ncase); while(ncase--) { int n,k; scanf("%d%d",&n,&k); a[0]=b[0]=1; int i=0,j=0; while(n>a[i])//构造数列 { i++; a[i]=b[i-1]+1; while(a[j+1]*k<a[i]) j++; if(a[j]*k<a[i]) b[i]=b[j]+a[i]; else b[i]=a[i]; } printf("Case %d: ",++Z); if(a[i]==n) { printf("lose\n"); continue; } int ans; while(n)//减法求先手第一步 { if(n>=a[i]) n-=a[i],ans=a[i]; i--; } printf("%d\n",ans); } }