Advertisement
Guest User

Untitled

a guest
Jul 23rd, 2014
421
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 3.00 KB | None | 0 0
  1. #include <iostream>
  2. #include <algorithm>
  3. #include <cmath>
  4. #include <cstring>
  5. #include <cstdlib>
  6. #include <string>
  7. #include <vector>
  8. #include <cstdio>
  9. #include <cassert>
  10. #include <ctime>
  11. #include <unordered_map>
  12. #include <unordered_set>
  13.  
  14. using namespace std;
  15.  
  16. typedef long long ll;
  17. typedef long double ld;
  18.  
  19. #ifdef WIN32
  20.     #define LLD "%I64d"
  21. #else
  22.     #define LLD "%lld"
  23. #endif
  24.  
  25. unordered_map<int, vector<int>> poss;
  26. unordered_map<int, unordered_map<int, int>> was;
  27.  
  28. const int maxn = 1005;
  29. char s[maxn][10];
  30. int st27[10];
  31. int len;
  32.  
  33. void add(char *s)
  34. {
  35.     int posmask = 0;
  36.     for (int i = 0; i < len; i++) posmask |= (1 << (s[i] - 'A'));
  37.     for (int mask = 0; mask < (1 << len); mask++)
  38.     {
  39.         int cur = 0;
  40.         for (int i = 0; i < len; i++) cur = cur * 27 + ((mask & (1 << i)) ? 0 : s[i] - 'A' + 1);
  41.         poss[cur].push_back(posmask);
  42.     }
  43. }
  44.  
  45. inline int get(int pos, int pl)
  46. {
  47.     return (pos / st27[pl]) % 27;
  48. }
  49.  
  50. inline int set(int pos, int pl, int x)
  51. {
  52.     return pos + (x - (pos / st27[pl]) % 27) * st27[pl];
  53. }
  54.  
  55. inline void printmask(int mask)
  56. {
  57.     for (int i = 0; i < 26; i++) if (mask & (1 << i)) cout << (char)('A' + i);
  58. }
  59.  
  60. inline void printpos(int pos)
  61. {
  62.     for (int i = 0; i < len; i++)
  63.     {
  64.         if (pos % 27 == 0) cout << '?';
  65.         else cout << (char)('A' + pos % 27 - 1);
  66.         pos /= 27;
  67.     }
  68. }
  69.  
  70. bool go(int curpos, int nowmask, int delmask)
  71. {
  72.     if (__builtin_popcount(nowmask) == len) return false;
  73.     auto whwas = was[curpos].find(delmask);
  74.     if (whwas != was[curpos].end()) return whwas->second;
  75. //  cout << "go ";
  76. //  printmask(delmask);
  77. //  cout << " ";
  78. //  printpos(curpos);
  79. //  cout << endl;
  80.     bool can = false;
  81.     for (auto x : poss[curpos]) can |= ((x & delmask) == 0);
  82. //  if (!can) cout << "not found " << endl;
  83.     if (!can)
  84.     {
  85.         was[curpos][delmask] = false;
  86.         return false;
  87.     }
  88.     if (__builtin_popcount(delmask) > len)
  89.     {
  90.         was[curpos][delmask] = true;
  91.         return true;
  92.     }
  93.     for (int c = 0; c < 26; c++) if (!((delmask | nowmask) & (1 << c)))
  94.     {
  95.         bool ok = go(curpos, nowmask, delmask | (1 << c));
  96.         for (int pl = 0; pl < len && !ok; pl++) if (get(curpos, pl) == 0)
  97.         {
  98.             ok |= go(set(curpos, pl, c + 1), nowmask | (1 << c), delmask);
  99.         }
  100.         if (!ok)
  101.         {
  102.             was[curpos][delmask] = false;
  103.             return false;
  104.         }
  105.     }
  106. //  cout << "true ";
  107. //  printmask(delmask);
  108. //  cout << " ";
  109. //  printpos(curpos);
  110. //  cout << endl;
  111.     was[curpos][delmask] = true;
  112.     return true;
  113. }
  114.  
  115. int main()
  116. {
  117.     st27[0] = 1;
  118.     for (int i = 1; i <= 6; i++) st27[i] = st27[i - 1] * 27;
  119.     int NT;
  120.     scanf("%d", &NT);
  121.     for (int T = 0; T < NT; T++)
  122.     {
  123.         int n;
  124.         scanf("%d", &n);
  125.         for (int i = 0; i < n; i++) scanf("%s", s[i]);
  126.         bool ok = false;
  127.         for (len = 1; len < 7; len++)
  128.         {
  129. //          cout << "len = " << len << endl;
  130.             poss.clear();
  131.             was.clear();
  132.             for (int i = 0; i < n; i++) if ((int)strlen(s[i]) == len)
  133.             {
  134.                 add(s[i]);
  135.             }
  136. //          cout << poss.size() << endl;
  137.             if (go(0, 0, 0))
  138.             {
  139.                 ok = true;
  140.                 printf("Yes\n");
  141.                 break;
  142.             }
  143.         }
  144.         if (!ok) printf("No\n");
  145.     }
  146.     return 0;
  147. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement