题解 P3042 【[USACO12JAN]牛跑Cow Run】

星爵 · 2017-10-24 16:28:07 · 题解

好像没什么人做这道题。。。

首先肯定是想4^n暴枚，可惜会超时。

考虑到某一轮作出某个选择的条件是：无论以后牛怎么选，农夫都有合法的选择方案。

如果枚举两个选择的话肯定不行，但是两种选择的结果逻辑运算有神奇的短路性质，所以在某一种满足条件的情况下另一种无需计算，这样会减小计算量。

那么数据故意卡怎么办呢？神奇的随机选择解决它。

附上真*题解：http://txhwind.blog.163.com/blog/static/203524179201211109155143/

#include<cstdio>
#include<iostream>
#include<cstdlib>
const int MAXN=14;
int m,x[MAXN<<3];
inline int calc(long long run,int n,bool a,bool b){
        int t=n*8+a*4+b*2;
        return (run*(x[t]+1)+x[t+1])%m;
}
int n,k;
bool check2(int,int);
bool check1(int now,int run,bool a){
        bool b=rand()&1;
        return check2(now+1,calc(run,now,a,b)) && check2(now+1,calc(run,now,a,!b));
}
bool check2(int now,int run){
        if(now==n)
                return run<=k || run+k>=m;
        bool a=rand()&1;
        return check1(now,run,a) || check1(now,run,!a);
}
int main(){
    int i,run=0;
    char c[MAXN];
    scanf("%d%d%d%s",&n,&m,&k,c);
    for(i=0;i<n<<3;++i)
        scanf("%d",x+i);
    for(i=0;i<n;++i)
        if(check1(i,run,1)){
            putchar('B');
            run=calc(run,i,1,c[i]=='B');
        }
        else{
            putchar('T');
            run=calc(run,i,0,c[i]=='B');
        }
    return 0;
}