USACO COWRUN 随机化搜索+双重递归调用
题面描述：给出8*N（<=14）组牌，每次按顺序选择8张，FJ可以选择前4张或者后4张，COW从FJ选出的牌中选择前两张或者后两张，然后COW会在环上走\(R \times A+B\),R为已经走的距离，A,B分别为选出的第一张和第二张牌，COW会在长度为M的换上走，要求最终cow，离起点的距离小于等于K，题目给出COW的决策，你要确定FJ的决策，注意由于FJ在COW 之前决策，也就说FJ所选出的决策一定要满足，无论之后COW如何选择，COW都能满足条件，求字典序最小
题目非常巧妙：N很小我们 可以搜索，如何去判断FJ的决策合法：枚举到下一层奶牛选择的两种可能，他们必须都合法，如何验证他们的合法性，分别进入下一层搜索树，只要有一个FJ的决策合法即可
这样做只有80分：数据可能会K你的决策 比如有很多的T
code
#include#include #include using namespace std;int n;long long m,k;int aa[20][10];char s[20];inline int cal(int pos,long long now,int a,int b){ int temp=4*a+2*b+1; return (now*(aa[pos][temp]+1)%m+aa[pos][temp+1])%m;}inline bool dfs(int pos,long long now,int a);inline bool efs(int pos,long long now){ if(pos>n)return now<=k || now>=m-k; return dfs(pos,now,1)||dfs(pos,now,0);}inline bool dfs(int pos,long long now,int a){ return efs(pos+1,cal(pos,now,a,1))&&efs(pos+1,cal(pos,now,a,0));}int main(){ cin>>n>>m>>k; scanf("%s",s+1); for(int i=1;i<=n;++i) for(int j=1;j<=8;++j)cin>>aa[i][j]; long long now=0; for(int i=1;i<=n;++i){ if(dfs(i,now,1)){ cout<<"B"; now=cal(i,now,1,s[i]=='B'); } else { cout<<"T"; now=cal(i,now,0,s[i]=='B'); } } return 0;}/*2 2 0 TT 1 0 0 0 0 0 0 1 0 1 1 1 0 0 1 0 */
类似TREAP的思想：随机化COW的选择判断答案的合法性不会被数据HACK
code:
#include#include #include #include using namespace std;int n;long long m,k;int aa[20][10];char s[20];inline int cal(int pos,long long now,int a,int b){ int temp=4*a+2*b+1; return (now*(aa[pos][temp]+1)%m+aa[pos][temp+1])%m;}//第pos次拿牌，当前位置在now，fj选了a，cow选了b后的位置inline bool dfs(int pos,long long now,int a);inline bool efs(int pos,long long now){ if(pos>n)return now<=k || now>=m-k; int x=rand()&1; return dfs(pos,now,x)||dfs(pos,now,!x);//个}//第pos次拿牌，当前位置在now，是否可行，验证就是FJ强制选或强制不选inline bool dfs(int pos,long long now,int a){ int x=rand()&1; return efs(pos+1,cal(pos,now,a,x))&&efs(pos+1,cal(pos,now,a,!x));}//第pos次拿牌，当前位置在now,fj选择a是否可行，验证只需后一个奶牛是否可以随便选int main(){ cin>>n>>m>>k; scanf("%s",s+1); for(int i=1;i<=n;++i) for(int j=1;j<=8;++j)cin>>aa[i][j]; long long now=0; for(int i=1;i<=n;++i){ if(dfs(i,now,1)){ cout<<"B"; now=cal(i,now,1,s[i]=='B'); } else { cout<<"T"; now=cal(i,now,0,s[i]=='B'); } } return 0;}/*2 2 0 TT 1 0 0 0 0 0 0 1 0 1 1 1 0 0 1 0 */