B. Hyperset

http://codeforces.com/contest/1287/problem/B

思路：

俩俩配对确定唯一的第三张就可以。每一张卡片可以用64为整数表示，所以找第三张就是找这个整数有没有。找第三张卡片不能用哈希map，因为有输入数据会导致重复的key比较多，导致超时。回忆起了当年自己为什么坚持用红黑树map。

两个卡片确定第三个可以用位运算提高效率，不过暴力计算也可以过。

 1 #include <iostream>
 2 #include <string>
 3 #include <stdio.h>
 4 #include <algorithm>
 5 #include <map>
 6 #include <unordered_map>
 7 #include <set>
 8 #include <string.h>
 9  
10 using namespace std;
11  
12 typedef long long LL;
13  
14 const int N = 1501;
15 int n,m;
16 string str[N];
17 LL sm2[N];
18 LL sm3[N];
19  
20 inline LL fb3(char c)
21 {
22     if (c == 'S')
23     {
24         return 1;
25     }
26     if (c == 'E')
27     {
28         return 2;
29     }
30     return 3;
31 }
32 inline LL fb2(char c)
33 {
34     if (c == 'S')
35     {
36         return 0;
37     }
38     if (c == 'E')
39     {
40         return 0;
41     }
42     return 3;
43 }
44  
45 LL fun(const string& s, int index)
46 {
47     LL k2 = 0;
48     LL k3 = 0;
49     for (int i = 0; i < m; ++i)
50     {
51         k2 |= (fb2(s[i]) << (i<<1));
52         k3 |= (fb3(s[i]) << (i<<1));
53     }
54     sm2[index] = k2;
55     sm3[index] = k3;
56     return k3;
57 }
58  
59 inline LL fun(LL s3_1, LL s3_2, LL s2_1, LL s2_2)
60 {
61     return (s3_1^s3_2) | (((~s2_1)^s2_2)&(s3_1|s3_2));
62 }
63  
64 int main()
65 {
66     while(cin>>n>>m)
67     {
68         set<LL> s_t;
69         for (int i = 0; i < n; ++i)
70         {
71             cin>>str[i];
72             s_t.insert(fun(str[i], i));
73         }
74  
75         int ans = 0;
76         for (int i = 0; i < n; ++i)
77         {
78             for (int j = i + 1; j < n; ++j)
79             {
80                 if (s_t.find(fun(sm3[i], sm3[j], sm2[i], sm2[j])) != s_t.end())
81                 {
82                     ans++;
83                 }
84             }
85         }
86         cout <<(ans/3) << endl;
87     }
88     return 0;
89 }