传送门1：http://www.usaco.org/index.php?page=viewproblem2&cpid=110
传送门2：http://www.lydsy.com/JudgeOnline/problem.php?id=2581
这题我一看就知道自己不会了，只想了个O(2^n * 2 ^ n)即O(2 ^ 2n)的大暴力，也懒得打了，果断看solution。
看了之后惊呆了，看到了一种从未见过，闻所未闻的树叫做And-Or Tree，百度了一下，并没有官方中文翻译，姑且叫他“与或树”好了。这种树是一棵满二叉树，每个节点的属性要么为And要么为Or，若为And，则该节点的值为其左儿子的值 && 右儿子的值；同理若为Or，则该节点的值为其左儿子的值 || 右儿子的值。
对应到这一题，就很明显（好叭我承认并不明显= =）的看出这是一个And-Or Tree的模型了，先上一张图，这张图就是Sample Input对应的And-Or Tree
怎么理解这棵树呢？现在我们有N堆卡片，每堆有8张，FJ的操作是要取当前堆的前4张或后4张，只要这两种操作其中至少一种可以完成任务就ok了，所以这就对应每个Or节点。而由于FJ并不知道在取出这4张卡前并不知道Bessie要如何操作，所以为了保证万无一失，应该要使Bessie不管取这4张卡的前两张还是后两张都可以完成任务，即对应了And节点。上图左子树的意思是选择底部，右子树是选择顶部。具体看代码吧，很好理解的。
#include <cstdio>
#include <cstdlib>
int n;
long long m, k, a[16][9], now;
char s[16];
bool solve_or(int, long long);
bool solve_and(int step, long long dis, int this4) {
int this2 = rand() & 1;
int rt = solve_or(step + 1, (dis * (a[step][this4 * 4 + this2 * 2] + 1) + a[step][this4 * 4 + this2 * 2 + 1]) % m) &&
solve_or(step + 1, (dis * (a[step][this4 * 4 + (this2 ^ 1) * 2] + 1) + a[step][this4 * 4 + (this2 ^ 1) * 2 + 1]) % m);
return rt;
}
bool solve_or(int step, long long dis) {
if (step == n + 1) {return dis <= k || dis >= m - k;
}
int next4 = rand() & 1;
int rt = solve_and(step, dis, next4) || solve_and(step, dis, next4 ^ 1);
return rt;
}
int main(void) {
freopen("cowrun.in", "r", stdin);
freopen("cowrun.out", "w", stdout);
unsigned seed;
scanf("%d%I64d%I64d", &n, &m, &k);
seed += n + m + k;
scanf("%s", s + 1);
for (int i = 1; i <= n; ++i) {
for (int j = 0; j < 8; ++j) {
scanf("%I64d", &a[i][j]);
seed += a[i][j];
}
}
srand(seed);
int t_this2;
for (int i = 1; i <= n; ++i) {
t_this2 = s[i] == ‘B‘;
if (solve_and(i, now, 1)) {
printf("B");
now = (now * (a[i][4 + t_this2 * 2] + 1) + a[i][4 + t_this2 * 2 + 1]) % m;
}
else {
printf("T");
now = (now * (a[i][t_this2 * 2] + 1) + a[i][t_this2 * 2 + 1]) % m;
}
}
puts("");
return 0;
}
真是涨姿势了，这个世界上真是啥奇葩玩意儿都有。。。
bzoj2581 [USACO 2012 Jan Gold] Cow Run【And-Or Tree】
原文：http://www.cnblogs.com/ciao-sora/p/5971398.html