题意：你有一个字符串， 有两种操作，一种是改变字符串，一种是某个用户询问这个字符串，如果一个用户每次查询字符串的时候都是他的用户名，他就会高兴。问最多有多少个用户会高兴？
题意：容易发现，在两个1操作之间，如果有多个用户的的询问，只能满足一个。换句话说，如果满足了其中的一个，那么其它的便不能满足。我们可以对所有两个1之间的操作两两连边，那么问题就变成了最大独立集问题。
对于这个问题，可以用状压DP解决，但是最多有40个不同的用户，所以需要分成两半，分别预处理，然后枚举其中的一半，在保证于这边一半不相交的情况下，找到对应的另一半。
代码：
#include <bits/stdc++.h>
using namespace std;
int f[1 << 20], g[1 << 20];
map<string, int> mp;
int G[50][50];
vector<int> v;
int cnt;
string s;
int main() {
int n, m, op;
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++) {
scanf("%d", &op);
if (op == 1) {
v.clear();
continue;
} else {
cin >> s;
if(!mp.count(s))
mp[s] = cnt++;
v.push_back(mp[s]);
for (int j = 0; j < v.size() - 1; j++)
G[v[j]][v[v.size() - 1]] = G[v[v.size() - 1]][v[j]] = 1;
}
}
if(v.size()) {
for (int j = 0; j < v.size() - 1; j++)
G[v[j]][v[v.size() - 1]] = G[v[v.size() - 1]][v[j]] = 1;
}
int s1 = m / 2;
int s2 = m - s1;
for (int i = 0; i < (1 << s1); i++) {
for (int j = 0; j < s1; j++) {
if(((i >> j) & 1) == 0) {
int flag = 1;
for (int k = 0; k < s1; k++) {
if((i >> k) & 1)
if(G[j][k] == 1) {
flag = 0;
break;
}
}
f[i | (1 << j)] = max(f[i | (1 << j)], f[i] + flag);
}
}
}
for (int i = 0; i < (1 << s2); i++) {
for (int j = 0; j < s2; j++) {
if(((i >> j) & 1) == 0) {
int flag = 1;
for (int k = 0; k < s2; k++) {
if((i >> k) & 1)
if(G[j + s1][k + s1] == 1) {
flag = 0;
break;
}
}
g[i | (1 << j)] = max(g[i | (1 << j)], g[i] + flag);
}
}
}
int ans = 0;
for (int i = 0; i < (1 << s1); i++) {
int now = (1 << s2) - 1;
for (int j = 0; j < s2; j++) {
for (int k = 0; k < s1; k++) {
if((i >> k) & 1)
if(G[k][j + s1] == 1) {
now ^= (1 << j);
break;
}
}
}
ans = max(ans, f[i] + g[now]);
}
printf("%d
", ans);
}