codeforces gym 100917 Interactive Casino 交互题+找种子

https://codeforces.com/gym/100917/problem/I

题目大意：交互题，初始你有$160$元，设你当前的钱数为$n$，每一轮可以赌$k$元($k<=n$)，此时系统会按照规律产生一个数字，如果该数字二进制有奇数个$1$，那么你可以拿回本金并获得额外的$k$元，否则你将失去本金。数字的产生规律为：$F_i=(487237\ast F_{i-1}+1011807)\%2^{20}$；你并不能得到这个数字，判断将由系统完成并返回你的剩余金钱数，当某个时刻你恰好有$200$元的时候，你就获得了胜利。

思路：看见这种题思路还是不够清晰啊，既然能找到必胜态说明一定有循环节。打表找规律，会发现：(1)任取$F_1=[0,2^{20}-1]$，$F_i=(487237\ast F_{i-1}+1011807)\%2^{20}$均有一个长度为$2^{20}$的循环节；(2)任取$F_1=[0,2^{20}-1]$，进行$38$轮游戏，我们记录这$38$轮游戏的结果：$s_i=1$表示第$i$轮胜利了，$s_i=0$表示第$i$轮失败了，那么我们可以得到一个$01$串，计算出其对应的二进制数会发现，这些二进制数没有重复的，也就是说我们进行$38$轮游戏后就可以确定这个序列的种子了(即$F_1$)。那么思路就很清晰了，每次只赌$1$块钱，赌$38$次后根据胜负情况还原出二进制数，然后依据这个二进制数找种子。找到种子后就知道系统以后生成的数据是什么了~

#include<bits/stdc++.h> #define INF 0x3f3f3f3f typedef long long ll; using namespace std; const int mod=1<<20; //map<ll,bool> m; //bool vis[mod+5]; int main() { //38 次即可鉴别 /* for(ll i=0;i<mod;i++) { ll ret=0; ll tmp=i; for(ll j=1;j<=38;j++) { if(__builtin_popcount(tmp)&1) ++ret; ret<<=1; tmp=(487237*tmp+1011807)%mod; } if(m.count(ret)) { cout<<"fail"<<endl; break; } m[ret]=1; } cout<<"success"<<endl;*/ //周期为 1<<20 /* for(ll i=0,j=0;i<mod;i++) { vis[j]=1; j=(487237*j+1011807)%mod; if(vis[j]) cout<<j<<endl; } for(int i=0;i<mod;i++) if(!vis[i]) cout<<"ok"<<endl; cout<<"no"<<endl;*/ int pre,cur; ll ret=0; cin>>pre; for(int i=1;i<=38;i++) { cout<<1<<endl; fflush(stdout); cin>>cur; ret<<=1; if(cur>pre)//赢了 ++ret; pre=cur; } //得到 唯一标识 ret ll v1=0,v2=0,tmp=0; for(int i=1;i<=38;i++) { tmp<<=1; if(__builtin_popcount(v1)&1) ++tmp; v1=(487237*v1+1011807)%mod; } if(tmp!=ret) //开始找种子 { ll base=0; for(int i=0;i<=36;i++) base|=1ll<<i; for(int i=1;i<mod;i++) { tmp&=base; //消去第一位的影响 tmp<<=1; if(__builtin_popcount(v1)&1) ++tmp; if(tmp==ret) //找到种子 { v1=(487237*v1+1011807)%mod; break; } v1=(487237*v1+1011807)%mod; } }//已经找到种子 下一次输入的数为 v1 while(1) { if(__builtin_popcount(v1)&1) //下一次必胜 cout<<200-cur<<endl; else cout<<1<<endl; fflush(stdout); cin>>cur; if(cur==-1) break; v1=(487237*v1+1011807)%mod; } return 0; }