Play the game SET

C++14(g++5.4) 解法, 执行用时: 3969ms, 内存消耗: 656K, 提交时间: 2020-02-20 16:36:05

#include <bits/stdc++.h>
using namespace std;

struct ast {
    int id[3];
    ast(int a = 0, int b = 0, int c = 0) { id[0] = a, id[1] = b, id[2] = c; }
    bool operator==(const ast &t) const {
        for(int i = 0; i < 3; i++)
            for(int j = 0; j < 3; j++)
                if(id[i] == t.id[j]) return false;
        return true;
    }
};

const int Z = 'z' + 5;
const int N = 45;
const int L = 15;
const int M = 1e3 + 5;
int x[Z][Z], y[Z][Z];
int t, n;
char s[L];
int cas, m, f[M], ft[N][4];
ast st[M];
bool flag, e[M][M];
vector<int> ans, cnt, a[M];

void init(void);
void solve(void);
bool check(int x, int y, int z);
void max_clique(void);
bool dfs(int d = 1);

int main(void) {
    init(), scanf("%d", &t);
    while(t--) solve();
}

inline void init(void) {
    x['d']['i'] = x['s']['q'] = x['o']['v'] = 1;
    x['s']['o'] = x['s']['t'] = x['o']['p'] = 2;
    x['r']['e'] = x['g']['r'] = x['p']['u'] = 3;
    y['t']['w'] = y['s']['q'] = y['s']['t'] = y['g']['r'] = 1;
    y['t']['h'] = y['o']['v'] = y['o']['p'] = y['p']['u'] = 2;
}

void solve(void) {
    scanf("%d", &n), m = 0, getchar();
    for(int i = 1; i <= n; i++, getchar())
        for(int j = 0; j < 4; j++)
            scanf("[%[^]]]", s + 1), ft[i][x[s[1]][s[2]]] = y[s[1]][s[2]];
    for(int i = 1; i < n - 1; i++)
        for(int j = i + 1; j < n; j++)
            for(int k = j + 1; k <= n; k++)
                if(check(i, j, k)) st[++m] = ast(i, j, k);
    for(int i = 1; i < m; i++)
        for(int j = i + 1; j <= m; j++) e[i][j] = e[j][i] = st[i] == st[j];
    max_clique(), printf("Case #%d: %d\n", ++cas, ans.size());
    for(int i: ans)
        for(int j = 0; j < 3; j++) printf("%d%c", st[i].id[j], " \n"[j == 2]);
}

bool check(int x, int y, int z) {
    for(int i = 0; i < 4; i++) {
        if(ft[x][i] == ft[y][i] && ft[x][i] ^ ft[z][i]) return false;
        if(ft[x][i] ^ ft[y][i])
            if(ft[x][i] == ft[z][i] || ft[y][i] == ft[z][i]) return false;
    }
    return true;
}

void max_clique(void) {
    memset(f, 0, (m + 1) * sizeof(int)), ans.clear();
    for(int i = m; i; i--) {
        cnt.push_back(i), a[1].clear();
        for(int j = i + 1; j <= m; j++)
            if(e[i][j]) a[1].push_back(j);
        dfs(), cnt.pop_back(), f[i] = ans.size();
    }
}

bool dfs(int d) {
    if(a[d].empty()) return d > ans.size() ? ans = cnt, true : false;
    for(int i = 0; i < a[d].size(); i++) {
        if(d + a[d].size() - i <= ans.size()) return false;
        if(d + f[a[d][i]] <= ans.size()) return false;
        cnt.push_back(a[d][i]), a[d + 1].clear();
        for(int j = i + 1; j < a[d].size(); j++)
            if(e[a[d][i]][a[d][j]]) a[d + 1].push_back(a[d][j]);
        flag = dfs(d + 1), cnt.pop_back();
        if(flag) return true;
    }
    return false;
}

C++(clang++11) 解法, 执行用时: 3631ms, 内存消耗: 504K, 提交时间: 2020-11-29 15:39:26

#include<bits/stdc++.h>
using namespace std;
const int N = 40;
int a[N];
map<string, int> id;
char str[][N] = {"one", "two", "three", "diamond", "squiggle", 
	"oval", "solid", "striped", "open", "red", "green", "purple"};
int p[N][4], vis[N];
int ans = 0, n;
vector<vector<int> > res;
vector<vector<int> > now; 
void dfs(int x, int cnt) {
	//cout << ans << endl;
	//cout << x << endl;
	int c = 0;
	for (int i = x; i <= n; i++) {
		if (!vis[i]) c ++;
	}
	if (c / 3 + cnt <= ans) return ;
	if (cnt > ans) {
		ans = cnt;
		res = now;
	}
	if (x > n) return ;
	if (!vis[x]) {
		for (int i = x + 1; i <= n; i++) {
			if (vis[i]) continue;
			for (int j = i + 1; j <= n; j++) {
				if (vis[j]) continue;
				bool ok2 = 1;
				for (int q = 0; q < 4; q++) {
					if (p[i][q] == p[j][q] && p[i][q] == p[x][q] || p[i][q] != p[j][q] && p[i][q] != p[x][q] && p[j][q] != p[x][q]) ;
					else ok2 = 0;
				}		
				if (ok2) {
					vis[x] = vis[i] = vis[j] = 1;
					now.push_back({x, i, j});
					//cout << x << " " << i << " " << j << endl; 
					dfs(x + 1, cnt + 1);
					now.pop_back();
					vis[x] = vis[i] = vis[j] = 0;
				}		
			}
		}
	}
	dfs(x + 1, cnt);
}
int main() {
	//freopen("out.txt", "r", stdin);
	int T; cin >> T;
	int kase = 1;
	for (int i = 0; i < 12; i++) id[str[i]] = i;
	while (T--) {
		cin >> n;
		res.clear();
		for (int i = 1; i <= n; i++) {
			string s ; cin >> s;
			for (int j = 0; j < 4; j++) {
				for (int k = 0; k < 3; k++) {
					if (s.find(str[j * 3 + k]) != string :: npos) {
						p[i][j] = k;		
					}
				}
			}
		}
		ans = 0;
		dfs(1, 0);
		printf("Case #%d: %d\n", kase++, ans);
		for (auto & c : res) {
			for (auto & o : c) {
				cout << o << " ";
			}
			cout << endl;
		}
	}
}

详情