本文同步更新于洛谷博客

题目描述

给定两个四面骰子 \(A\) 和 \(B\)，且骰子上的数均在 \(1\) 和 \(10\) 之间。问是否存在骰子 \(C\)，使得三个骰子的胜负关系形成一个环。

题解

直接暴力枚举 \(C\) 上的数即可，不要忘了有平局的情况。

小优化

1. 如果存在一种情况满足条件就不用继续枚举了；
2. 由于 \(1,2,4,5\) 和 \(1,5,2,4\) 是一样的，所以我们可以把 \(C\) 当作一个单调不降的序列来枚举，即 \(c_i\ge c_{i-1}\)。

Code

#include
using namespace std;
int t,k,a[5],b[5],c[5],ans;
int cmp(int *x,int *y)
{
    int p=0,q=0;
    for(int i=1;i<=4;i++)
    {
	for(int j=1;j<=4;j++)
	{
	    if(x[i]>y[j]) p++;
	    if(x[i]q) return 1;//x胜
    if(pb,b->c,c->a
	b->a,a->c,c->b
	*/ 
	return;
    }
    for(int i=y;i<=10;i++)
	dfs(x+1,c[x]=i);
}
int main()
{
    scanf("%d",&t);
    while(t--)
    {
	ans=0;
	for(int i=1;i<=4;i++)
	    scanf("%d",&a[i]);
	sort(a+1,a+5);
	for(int i=1;i<=4;i++)
	    scanf("%d",&b[i]);
	sort(b+1,b+5);
	k=cmp(a,b);
	if(!k)
	{
	    printf("no\n");
	    continue; 
	}//平局不符合条件
	dfs(1,1);//枚举c的四个数
	printf("%s\n",ans?"yes":"no");
    }
    return 0;
}