2020牛客暑期多校训练营（第八场）G Game SET

题目大意

一张纸牌有4个特征，每种特征有3种不同的情况，所以一套牌中有81张不重复的牌。
对于4种特征中的每种，当任意三张卡牌这项特征完全相同，或完全不同时，这三张牌组成一个set。
有一些万能卡，万能卡的某些特征可以任意决定，例如[*][diamond][solid][red]可以任意决定第一项特征。

给定N张不一样的卡牌，找到任意一种合法的set。

解题思路

暴力出奇迹，直接冲！三层循环判断即可。
但是题目中的牌数N≤256，而样例数T≤1000，好像不满足时间要求啊。

但是，由于某些神奇的结论，不能构成set的集合最大就是20，枚举21张肯定可以找到set。
（原来出题人提供了原论文，但是我网站上不去）

AC代码

#include<bits/stdc++.h>
using namespace std;
const int N=110,M=310,mod=1e9+7;
int m[5][M];
char c[N];
void scan(int x)
{
    int l=strlen(c+1),s=0,t=0,i;
    for(i=1;i<=l;i++)
    {
        if(c[i]=='[')
        {
            s=0;
            continue;
        }
        if(c[i]==']')
        {
            m[++t][x]=s;
            continue;
        }
        if(c[i]=='*') s=-1;
        else s=(1ll*s*29+c[i]-'a')%mod;
    }
}
bool check(int x,int y,int z)
{
    int a,b,c,i;
    for(i=1;i<=4;i++)
    {
        a=m[i][x],b=m[i][y],c=m[i][z];
        if(a>b) a^=b^=a^=b;
        if(a>c) a^=c^=a^=c;
        if(b>c) b^=c^=b^=c;
        if(c==-1 || b==-1) continue;
        else if(b==c && (b==a||a==-1)) continue;
        else if(b!=c && a!=b) continue;
        else return 0;
    }
    return 1;
}
int main()
{
    int T,n,h,i,j,k;
    bool flag;
    scanf("%d",&T);
    for(h=1;h<=T;h++)
    {
        flag=0;
        scanf("%d",&n);
        for(int i=1;i<=n;i++)
        {
            scanf("%s",c+1);
            scan(i);
        }
        for(i=1;i<=n;i++)
        {
            if(flag) break;
            for(j=i+1;j<=n;j++)
            {
                if(flag) break;
                for(k=j+1;k<=n;k++)
                    if(check(i,j,k))
                    {
                        printf("Case #%d: %d %d %d\n",h,i,j,k);
                        flag=1;
                        break;
                    }
            }
        }
        if(!flag) printf("Case #%d: -1\n",h);
    }
}