容易想歪的简单题。
考虑社团人数上限很高，是 (lfloorfrac{n}{2}rfloor)，很容易发现，其实两个社团就可以塞满 (n) 个人。
于是对于一个人，只需考虑三个社团中的最大值和次大值，那么首先，如果按所有人都分配到对于那个人中三个社团最大值之后，人数最大的社团也是小于等于 (lfloorfrac{n}{2}rfloor) 的话，那么答案直接就是将所有人对应的最大值加起来就行了，设这个值为 (sum)，否则的话，考虑如何微调。
那么考虑一个人的贡献，其实可以设成他的最大值和次大值的差，然后按贡献从小到大排序，容易证明这是对的。
然后其实考虑我们设目前人数超过 (lfloorfrac{n}{2}rfloor) 的社团人数和 (lfloorfrac{n}{2}rfloor) 的差为 (s)，然后删掉前 (s) 个人的贡献就行了。
代码：
#include<bits/stdc++.h> using namespace std; const int N = 1e5+5; struct node { int x; int y; int z; int maxxx; int cha; }a[N]; int num[3]; int b[N]; signed main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); int _; cin >> _; while(_--) { num[0] = num[1] = num[2] = 0; int n,sum = 0; cin >> n; for(int i = 1;i<=n;++i) { cin >> a[i].x >> a[i].y >> a[i].z; int maxx = a[i].x,maxxx = 0; if(a[i].y>maxx) { maxx = a[i].y; maxxx = 1; } if(a[i].z>maxx) { maxx = a[i].z; maxxx = 2; } int cmax; if(maxx == a[i].x) { if(a[i].y>a[i].z) { cmax = a[i].y; } else { cmax = a[i].z; } } else if(maxx == a[i].y) { if(a[i].x>a[i].z) { cmax = a[i].x; } else { cmax = a[i].z; } } else { if(a[i].x>a[i].y) { cmax = a[i].x; } else { cmax = a[i].y; } } a[i].maxxx = maxxx; a[i].cha = maxx-cmax; sum+=maxx; ++num[maxxx]; } int ss = 0; if(num[ss]<num[1]) { ss = 1; } if(num[ss]<num[2]) { ss = 2; } if((num[ss]<<1)<=n) { cout << sum << 'n'; continue; } int cnt = 0; for(int i = 1;i<=n;++i) { if(a[i].maxxx == ss) { b[++cnt] = a[i].cha; } } sort(b+1,b+cnt+1); int s = num[ss]-n/2; for(int i = 1;i<=s;++i) { sum-=b[i]; } cout << sum << 'n'; } return 0; } 小小优化题。
看到 (k le 10)，直接考虑状压。
首先有一个朴素做法，直接建边，然后对于所有状态限制它的连边，直接做就行了。发现复杂度是 (O(2^k (m+kn) log (m+kn)))，直接爆炸。
考虑第一个优化，首先我们一开始没建乡镇之前跑一遍最小生成树，此时不再最小生成树之内的边之后一定是没有贡献的，所以我们的边数可以从 (m+kn) 变成 (n-1+kn)，此时复杂度是 (O(2^k (n-1+kn) log (n-1+kn)))，还是炸。
考虑第二个优化，我们根本没有必要每次都排序，直接在枚举状态之前跑一遍就行了，复杂度是 (O(2^k (n-1+kn)))，此时已经可以通过。
但是可以更优，因为对于每次跑最小生成树，设有 (num) 个乡镇可以用，然后其实当边数是 (n+num-1) 时，就可以退了，因为树的边数就是这个。
代码：
#include<bits/stdc++.h> using namespace std; const int N = 1.15e6+5; struct node { int x; int y; int w; }a[N]; int b[15][N]; int fa[N]; int f(int x) { return x == fa[x]?x:fa[x] = f(fa[x]); } int cmp(node x,node y) { return x.w<y.w; } signed main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); int n,m,k; cin >> n >> m >> k; for(int i = 1;i<=n;++i) { fa[i] = i; } for(int i = 1;i<=m;++i) { cin >> a[i].x >> a[i].y >> a[i].w; } stable_sort(a+1,a+m+1,cmp); long long sum = 0; int tot = 0; for(int i = 1;i<=m;++i) { int x = f(a[i].x),y = f(a[i].y); if(x!=y) { fa[x] = y; sum+=a[i].w; ++tot; a[tot] = a[i]; if(tot == n-1) { break; } } } m = tot; tot = 0; for(int i = 1;i<=k;++i) { cin >> b[i][0]; for(int j = 1;j<=n;++j) { cin >> b[i][j]; ++tot; a[m+tot] = {j,n+i,b[i][j]}; } } stable_sort(a+1,a+m+tot+1,cmp); int zong = (1<<k)-1; for(int i = 1;i<=zong;++i) { long long res = 0; int num = 0; for(int j = 1;j<=k;++j) { if(i&(1<<j-1)) { res+=b[j][0]; ++num; } } for(int j = 1;j<=n+k;++j) { fa[j] = j; } int cnt = 0; for(int j = 1;j<=m+tot;++j) { if(a[j].y>n&&!(i&(1<<a[j].y-n-1))) { continue; } int x = f(a[j].x),y = f(a[j].y); if(x!=y) { fa[x] = y; res+=a[j].w; ++cnt; if(cnt == n+num-1) { break; } } } sum = min(sum,res); } cout << sum; return 0; } 哇！数据真水！
正解太难，考虑乱搞。
观察到题目的这个条件，(sum_{i = 1}^n |s_{i,0}|+|s_{i,1}| le 5 times 10^6)，那么显然所有匹配方案的长度种类数不会超过 (sqrt{5 times 10^6})，证明后面说，那么既然长度只有根号级别……嘿嘿，没错，考虑对于每一个询问直接枚举匹配左端点 (l) 然后枚举长度 (k)，那么 (r = l+k-1)，直接采用回滚哈希进行检测就行了（后续除了证明之外还有后话，先别走）。
补一下刚刚那个结论的证明：
因为 (|s_{i,0}| = |s_{i,1}|)，所以：
考虑什么情况下可以使得 (|s_{i,0}|) 的种类数最多，首先重复肯定是不优的，然后你发现最坏情况是 (1,2,3,dots)，这样不会重复，而且和是最小的方案，但是你很容易看到这是等差数列，直接 (frac{n(n-1)}{2})，然后也就是：
考虑 (m) 的最大取值其实就是 (sqrt{5 times 10^6})，得证。
后话：仔细思考……不对啊，这么说的话，复杂度应该是 (O(L_1sqrt{L_2}))，然而 (L_1,L_2 le 5 times 10^6)，这不是必炸吗！但是其实你要想到造数据的人哪有那么阴险，(L_1,L_2) 不会那么卡点取值，而且，你要想到我们可以在询问中加一个特判 (|t_{i,0}| not= |t_{i,1}|) 就直接输出 (0)，这样可以
大大加快速度，不仅如此，你写代码时发现其实可以加特判，可以叉掉一些东西，先看这个特判：
if(pre[i-1][0]!=pre[i-1][1]) { break; } 就是在查询的时候枚举左端点 (l) 时（我代码里把 (l) 写成变量 (i)），判一下我们存下来的前缀哈希从 (1 sim l-1) 中 (t_{i,0}) 和 (t_{i,1}) 是否完全相同，不相同直接
break，原理显然，因为我们只能匹配一次，所以不在 (l sim r) 范围之内的字符必须相同才行，不然根本替换不了（这不是显然叉掉了一堆情况吗）。这是你可能会想问unordered_map的常数问题，虽然查找和插入的确有常数，但是我们还可以加一个这个针对查找的特判：
if(pre1[r+1][0]!=pre1[r+1][1]) { continue; } 原理不多说了，这样可以减少
unordered_map的查找次数，同时，还有一个这个特判：
if(r>len) { break; } 这个特判没什么好说了，但是不要小看它的威力，也是可以积少成多地叉掉一些没用的东西的。
代码：
#include<bits/stdc++.h> using namespace std; const int N = 2e5+5; const int M = 5e6; const unsigned long long base = 131; struct node { template<typename T, typename U> size_t operator()(const pair<T,U>&p)const { return hash<T>()(p.first)^hash<U>()(p.second); } }; struct node1 { template<typename T, typename U> bool operator()(const pair<T,U>&p1,const pair<T,U>&p2)const { return p1.first == p2.first&&p1.second == p2.second; } }; unordered_map<pair<unsigned long long,unsigned long long>,int,node,node1>mp[N]; string s[N][2]; int num[N]; int biao[M]; unsigned long long pre[M][2],pre1[M][2],ha[N],hb[N],p[M]; int ji[N]; signed main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); p[0] = 1; for(int i = 1;i<=M;++i) { p[i] = p[i-1]*base; } int n,_,cnt = 0; cin >> n >> _; for(int i = 1;i<=n;++i) { cin >> s[i][0] >> s[i][1]; num[++cnt] = s[i][0].size(); int len = num[cnt]; s[i][0] = ' '+s[i][0]; s[i][1] = ' '+s[i][1]; for(int j = 1;j<=len;++j) { ha[i] = ha[i]*base+s[i][0][j]; hb[i] = hb[i]*base+s[i][1][j]; } } stable_sort(num+1,num+cnt+1); int tot = unique(num+1,num+cnt+1)-num-1; for(int i = 1;i<=tot;++i) { biao[num[i]] = i; ji[i] = num[i]; } for(int i = 1;i<=n;++i) { ++mp[biao[s[i][0].size()-1]][{ha[i],hb[i]}]; } while(_--) { string a,b; cin >> a >> b; if(a.size()!=b.size()) { cout << 0 << 'n'; continue; } int len = a.size(); a = ' '+a; b = ' '+b; pre[0][0] = pre[0][1] = pre1[len+1][0] = pre1[len+1][1] = 0; for(int i = 1;i<=len;++i) { pre[i][0] = pre[i-1][0]*base+a[i]; pre[i][1] = pre[i-1][1]*base+b[i]; } for(int i = len;i;--i) { pre1[i][0] = pre1[i+1][0]*base+a[i]; pre1[i][1] = pre1[i+1][1]*base+b[i]; } int ans = 0; for(int i = 1;i<=len;++i) { if(pre[i-1][0]!=pre[i-1][1]) { break; } for(int j = 1;j<=tot;++j) { int l = i,r = i+ji[j]-1; if(r>len) { break; } if(pre1[r+1][0]!=pre1[r+1][1]) { continue; } unsigned long long hsa = pre[r][0]-pre[l-1][0]*p[r-l+1],hsb = pre[r][1]-pre[l-1][1]*p[r-l+1]; if(mp[j].find({hsa,hsb})!=mp[j].end()) { ans+=mp[j][{hsa,hsb}]; } } } cout << ans << 'n'; } return 0; } 最后：
如果有人能卡掉我的这份代码（洛谷机子和洛谷时限），请私信交流。
