Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <algorithm>
- #include <cmath>
- #include <cstring>
- #include <cstdlib>
- #include <string>
- #include <vector>
- #include <cstdio>
- #include <cassert>
- #include <ctime>
- #include <unordered_map>
- #include <unordered_set>
- using namespace std;
- typedef long long ll;
- typedef long double ld;
- #ifdef WIN32
- #define LLD "%I64d"
- #else
- #define LLD "%lld"
- #endif
- unordered_map<int, vector<int>> poss;
- unordered_map<int, unordered_map<int, int>> was;
- const int maxn = 1005;
- char s[maxn][10];
- int st27[10];
- int len;
- void add(char *s)
- {
- int posmask = 0;
- for (int i = 0; i < len; i++) posmask |= (1 << (s[i] - 'A'));
- for (int mask = 0; mask < (1 << len); mask++)
- {
- int cur = 0;
- for (int i = 0; i < len; i++) cur = cur * 27 + ((mask & (1 << i)) ? 0 : s[i] - 'A' + 1);
- poss[cur].push_back(posmask);
- }
- }
- inline int get(int pos, int pl)
- {
- return (pos / st27[pl]) % 27;
- }
- inline int set(int pos, int pl, int x)
- {
- return pos + (x - (pos / st27[pl]) % 27) * st27[pl];
- }
- inline void printmask(int mask)
- {
- for (int i = 0; i < 26; i++) if (mask & (1 << i)) cout << (char)('A' + i);
- }
- inline void printpos(int pos)
- {
- for (int i = 0; i < len; i++)
- {
- if (pos % 27 == 0) cout << '?';
- else cout << (char)('A' + pos % 27 - 1);
- pos /= 27;
- }
- }
- bool go(int curpos, int nowmask, int delmask)
- {
- if (__builtin_popcount(nowmask) == len) return false;
- auto whwas = was[curpos].find(delmask);
- if (whwas != was[curpos].end()) return whwas->second;
- // cout << "go ";
- // printmask(delmask);
- // cout << " ";
- // printpos(curpos);
- // cout << endl;
- bool can = false;
- for (auto x : poss[curpos]) can |= ((x & delmask) == 0);
- // if (!can) cout << "not found " << endl;
- if (!can)
- {
- was[curpos][delmask] = false;
- return false;
- }
- if (__builtin_popcount(delmask) > len)
- {
- was[curpos][delmask] = true;
- return true;
- }
- for (int c = 0; c < 26; c++) if (!((delmask | nowmask) & (1 << c)))
- {
- bool ok = go(curpos, nowmask, delmask | (1 << c));
- for (int pl = 0; pl < len && !ok; pl++) if (get(curpos, pl) == 0)
- {
- ok |= go(set(curpos, pl, c + 1), nowmask | (1 << c), delmask);
- }
- if (!ok)
- {
- was[curpos][delmask] = false;
- return false;
- }
- }
- // cout << "true ";
- // printmask(delmask);
- // cout << " ";
- // printpos(curpos);
- // cout << endl;
- was[curpos][delmask] = true;
- return true;
- }
- int main()
- {
- st27[0] = 1;
- for (int i = 1; i <= 6; i++) st27[i] = st27[i - 1] * 27;
- int NT;
- scanf("%d", &NT);
- for (int T = 0; T < NT; T++)
- {
- int n;
- scanf("%d", &n);
- for (int i = 0; i < n; i++) scanf("%s", s[i]);
- bool ok = false;
- for (len = 1; len < 7; len++)
- {
- // cout << "len = " << len << endl;
- poss.clear();
- was.clear();
- for (int i = 0; i < n; i++) if ((int)strlen(s[i]) == len)
- {
- add(s[i]);
- }
- // cout << poss.size() << endl;
- if (go(0, 0, 0))
- {
- ok = true;
- printf("Yes\n");
- break;
- }
- }
- if (!ok) printf("No\n");
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement