题目链接: https://acm.ecnu.edu.cn/contest/196/problem/A/
题目:
解题报告:
由于必胜点是 n, 所以 n 点的必胜状态为 yes(走到这个点的人必胜), 考虑 n-1 到 n/2+1 这一段 (因为这一段都无法整除), 所以 i 点的状态可以由 i+1 得到, 接着从再从 n/2 推到 1, 由于有两种取法, 所以对于当前状态 i, 如果 i+1 或者 2*i 的状态 (这两点的状态前面已经推出来了), 有一个为 yes, 那么这个 i 点的状态就为 no(因为前面是由两者取最优的决策得出的), 因为我走到这里, 另一个玩家就可以从这里开始转移到下一个他必胜的状态.
所以由前面的结论, 将 Cuber QQ Win 赢的情况的前 10000 项打表 O(n) 后, 发现表中每个偶数项都能被 8 整除, 奇数项能通过前一个偶数项 + 2 得到.
打表代码:
- #include<bits/stdc++.h>
- #define numm ch-48
- using namespace std;
- template <typename T>
- void read(T &res) {
- bool flag=false;char ch;
- while(!isdigit(ch=getchar())) (ch=='-')&&(flag=true);
- for(res=numm;isdigit(ch=getchar());res=(res<<1)+(res<<3)+numm);
- flag&&(res=-res);
- }
- template <typename T>
- void write(T x) {
- if(x<0) putchar('-'),x=-x;
- if(x>9) write(x/10);
- putchar(x%10+'0');
- }
- typedef pair<int,int> pi;
- typedef long long ll;
- const int maxn=10010;
- int a[maxn];
- int main()
- {
- int n;
- #define local
- #ifdef local
- freopen("1.txt","w",stdout);
- #endif
- #define p1 puts("Little Fang Win")
- #define p2 puts("Cuber QQ Win")
- for(int j=2;j<=10000;j++) {
- n=j;
- if(n==1) {
- p1;
- continue;
- }
- if(n%2) {
- a[n]=1;
- n--;
- a[n]=0;
- for(int i=n-1;i>n/2&&i>1;i--)
- if((n-i)%2) a[i]=1;
- else a[i]=0;
- }
- else {
- a[n]=1;
- for(int i=n-1;i>n/2&&i>1;i--)
- if((n-i)%2) a[i]=0;
- else a[i]=1;
- }
- for(int i=n/2;i>1;i--)
- a[i]=max(a[i*2],a[i+1])?0:1;
- if(a[2]) write(j),cout<<"->",p2;
- }
- return 0;
- }
代码在这里!
然后将偶数项除以 8 拿出来, 发现有规律的 (其实口述不好说), 序列是 1,4,5,16,17,20,21,64,65,68,69,80,81,84,85. 规律就自己看了, 然后用 vector 打表发现存不下, 后来写个算法把 n 往 1 推, 发现 4234 这个数行不通, 赛后看题解是有关二进制的, 只要所有奇数位都为 0, 那么就是 Cuber QQ Win, 反之 Little Fang Win, 懵逼国有懵逼路, 懵逼树旁懵逼树, 懵逼树下只有我...
AC 代码:
- #include<bits/stdc++.h>
- #define numm ch-48
- using namespace std;
- template <typename T>
- void read(T &res) {
- bool flag=false;char ch;
- while(!isdigit(ch=getchar())) (ch=='-')&&(flag=true);
- for(res=numm;isdigit(ch=getchar());res=(res<<1)+(res<<3)+numm);
- flag&&(res=-res);
- }
- template <typename T>
- void write(T x) {
- if(x<0) putchar('-'),x=-x;
- if(x>9) write(x/10);
- putchar(x%10+'0');
- }
- typedef long long ll;
- #define p1 puts("Little Fang Win")
- #define p2 puts("Cuber QQ Win")
- int main()
- {
- int _;
- ll n;
- read(_);
- while(_--) {
- read(n);
- bitset<64>b(n);
- bool flag=false;
- for(int i=0;i<63;i+=2)
- if(b[i]) {
- p1;
- flag=true;
- break;
- }
- if(!flag) p2;
- }
- return 0;
- }
代码在这里!
来源: http://www.bubuko.com/infodetail-3186440.html