USACO Non-Transitive Dice B [22JAN]
清小秋ovo
·
·
题解
USACO 铜组 T2 题解
看到数据立马暴力。
因为筛子只有 4 面，且每面数字最大为 10。
哪怕是 O(n ^4) 的复杂度也无伤大雅。
题意
当 A 筛 赢 B 筛的可能性更大时，则需满足： B 筛赢 C 筛可能性更大，且 C 筛赢 A 筛可能性更大。
反之，当 B 赢 A 时，则需满足 C 赢 B, A 赢 C。
代码
结构比较清晰，可以对上刚刚解释的思路，所以就不放注释了。
```cpp
#include<bits/stdc++.h>
using namespace std;
int T, a[4],b[4],c[4];
inline int read()
{
int f = 1, x = 0; char c = getchar();
while (c < '0' || c > '9') { if (c == '-') f = -1; c = getchar();}
while (c >= '0' && c <= '9') { x = x * 10 + c - '0'; c = getchar();}
return f * x;
}
bool x_win_y(int x[4], int y[4]){
int x_cnt =0, y_cnt = 0;
for(int i=0;i<4;i++){
for(int j=0;j<4;j++){
if(x[i]>y[j])x_cnt++;
else if(x[i]<y[j])y_cnt++;
}
}
return x_cnt > y_cnt;
}
bool check(){
if(x_win_y(a,b) && x_win_y(b,c) && x_win_y(c,a))return true;
if(x_win_y(b,a) && x_win_y(c,b) && x_win_y(a,c))return true;
return false;
}
void solve(){
for(c[0]=1;c[0]<=10;c[0]++){
for(c[1]=c[0];c[1]<=10;c[1]++){
for(c[2]=c[1];c[2]<=10;c[2]++){
for(c[3]=c[2];c[3]<=10;c[3]++){
if(check()){
puts("yes");
return;
}
}
}
}
}
puts("no");
}
int main()
{
T = read();
while(T--){
for(int i=0;i<4;i++) a[i] = read();
for(int i=0;i<4;i++) b[i] = read();
solve();
}
return 0;
}
```