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

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

题解：

比赛的时候算错复杂度了，以为可以过就交了，结果居然还过了。。。

#include <bits/stdc++.h>
#define inf 0x3f3f3f3f
#define debug(x) cout<<"debug:"<<#x<<" = "<<x<<endl;
using namespace std;
typedef long long ll;
int num[300][30];
char s[110];
vector<int>vis[300];

int dfs1(int i,int j,int dep,int sum){
//    printf("dep=%d i=%d j=%d sum=%d
",dep,i,j,sum);
    if(dep>4){
        for(int k=0;k<vis[sum].size();k++){
            int v = vis[sum][k];
            if(v!=i&&v!=j){
                return v;
            }
        }
        return 0;
    }
    int x = num[i][dep];
    int y = num[j][dep];
//    printf("x=%d y=%d
",x,y);
    if(x==3|y==3){
        int f = dfs1(i,j,dep+1,sum*3+0);
        if(f) return f;
        f = dfs1(i,j,dep+1,sum*3+1);
        if(f) return f;
        f = dfs1(i,j,dep+1,sum*3+2);
        if(f) return f;
    }
    else if(x==y) {
        int f = dfs1(i,j,dep+1,sum*3+y);
        if(f) return f;
    }
    else{
//    	printf("x=%d y=%d dep=%d i=%d j=%d sum=%d
",x,y,dep,i,j,sum);
        int f = dfs1(i,j,dep+1,sum*3+3-x-y);
        if(f) return f;
    }
    return 0;
}

void dfs(int i,int dep,int sum){
    if(dep>4) {
        vis[sum].push_back(i);
        return ;
    }
    if(num[i][dep]==3){
        dfs(i,dep+1,sum*3+0);
        dfs(i,dep+1,sum*3+1);
        dfs(i,dep+1,sum*3+2);
    }
    else dfs(i,dep+1,sum*3+num[i][dep]);
}


int main(){
    int t;
    scanf("%d",&t);
    for(int cas=1;cas<=t;cas++){
        int n;
        scanf("%d",&n);
        for(int i=0;i<300;i++) vis[i].clear();
        memset(num,0,sizeof(num));
        for(int i=1;i<=n;i++){
            scanf("%s",s+1);
            int len = strlen(s+1),cnt=0;
            for(int j=1;j<=len;j++){
                if(s[j]=='['){
                    ++cnt;
                    int x = 0;
                    if(s[j+1]=='*'){num[i][cnt]=3;continue;}

                    if(s[j+1]=='o'&&s[j+2]=='n'&&s[j+3]=='e') x = 0;
                    if(s[j+1]=='t'&&s[j+2]=='w'&&s[j+3]=='o') x = 1;
                    if(s[j+1]=='t'&&s[j+2]=='h'&&s[j+3]=='r') x = 2;

                    if(s[j+1]=='d'&&s[j+2]=='i'&&s[j+3]=='a') x = 0;
                    if(s[j+1]=='s'&&s[j+2]=='q'&&s[j+3]=='u') x = 1;
                    if(s[j+1]=='o'&&s[j+2]=='v'&&s[j+3]=='a') x = 2;

                    if(s[j+1]=='s'&&s[j+2]=='o'&&s[j+3]=='l') x = 0;
                    if(s[j+1]=='s'&&s[j+2]=='t'&&s[j+3]=='r') x = 1;
                    if(s[j+1]=='o'&&s[j+2]=='p'&&s[j+3]=='e') x = 2;

                    if(s[j+1]=='r'&&s[j+2]=='e'&&s[j+3]=='d') x = 0;
                    if(s[j+1]=='g'&&s[j+2]=='r'&&s[j+3]=='e') x = 1;
                    if(s[j+1]=='p'&&s[j+2]=='u'&&s[j+3]=='r') x = 2;

                    num[i][cnt]=x;
                }
            }
            dfs(i,1,0);
        }
        ll ans1 = 0,ans2 = 0,ans3 = 0;
        for(int i=1;i<=n;i++){
            for(int j=i+1;j<=n;j++){
                int f = dfs1(i,j,1,0);
                if(f){
                    ans1 = i,ans2 = j,ans3= f;
                    break;
                }
            }
            if(ans1) break;
        }
        if(!ans1) printf("Case #%d: -1
",cas);
        else printf("Case #%d: %lld %lld %lld
",cas,ans1,ans2,ans3);
    }
}