这次比较有进步可能是因为题不是很难吧A了5个目录A题小红的好串mapB题小红的好串计数双指针C题小红的染色平均数分数计算核心目标关键发现数学推导最少操作次数计算D题小红的排列构造构造核心目标关键发现核心逻辑E题小红的染色生成树最小生成树强制加边核心目标关键发现核心逻辑A题小红的好串map这个主要就是用map统计一下字符出现个数就好了嘛不用多说#includebits/stdc.h using namespace std; string s; int main() { cins; unordered_mapchar,intmp; for(int i0;is.size();i) { mp[s[i]]; } bool flagfalse; for(int i0;is.size();i) { if(mp[s[i]]2) { flagtrue; break; } } if(flag)coutYesendl; else coutNoendl; return 0; }B题小红的好串计数双指针先算出所有子串的个数然后再减去不是好串的子串个数就好了不是子串就是连续字符相同嘛就是双指针#includebits/stdc.h using namespace std; const int N1e610; typedef long long LL; string s; int main() { int n; cinns; LL res1LL*n*(n1)/2; for(int i0;in;) { int ji; while(s[i]s[j]jn)j; int numj-i; res-1LL*num*(num1)/2; ij; } coutresendl; return 0; }C题小红的染色平均数分数计算核心目标让红色元素的平均值 蓝色元素的平均值。关键发现操作不改变总和每次 “一加一减”整个数组的总和不变。只跨颜色操作才有效同颜色之间的加减对平均值没任何影响。数学推导设cnt0红色元素个数sum0红色元素总和cnt1蓝色元素个数sum1蓝色元素总和要让平均值相等等价于sum0 / cnt0 sum1 / cnt1交叉相乘消分母sum0 * cnt1 sum1 * cnt0最少操作次数计算每次跨颜色操作会让上面的差值变化n总元素个数。所以最少操作次数就是|sum0 * cnt1 - sum1 * cnt0| / n。如果差值不能被n整除就永远不可能实现输出-1。#includebits/stdc.h using namespace std; const int N2e510; int a[N]; string s; typedef long long LL; int n; int main() { cinn; for(int i0;in;i)cina[i]; cins; LL sum10,sum00; LL res10,res00; for(int i0;in;i) { if(s[i]1) { sum1; res1a[i]; } else { sum0; res0a[i]; } } //coutsum1 sum0endl; //coutres1 res0endl; LL numsum1sum0; res1*sum0; res0*sum1; //coutres1 res0endl; if(abs(res1-res0)%num) { cout-1endl; } else { coutabs(res1-res0)/numendl; } return 0; }D题小红的排列构造构造核心目标构造两个长度为 n 的排列 b 和 c满足每个位置 ib [i] 或 c [i] 等于 a [i]b 和 c 中等于 a [i] 的位置都至少有 n/2 个b 和 c 都是 1~n 的排列每个数恰好出现一次关键发现最多出现 2 次任何数在 a 中出现超过 2 次就一定无解因为两个排列加起来最多只能放 2 个这个数。单次数双份放只出现 1 次的数可以同时放在 b 和 c 的对应位置既不破坏排列因为只出现一次又能同时增加两个数组的匹配数。空位数量相等出现 2 次的数会在每个数组里各留下 k 个空位而 a 中没出现过的数也正好有 k 个刚好能填满。核心逻辑先判无解统计每个数的出现次数只要有一个数出现超过 2 次直接输出 - 1。双次数分家对于出现 2 次的数第一次出现放在 b 数组第二次出现放在 c 数组。这样既保证了每个位置都有一个数组等于 a [i]又保证了两个数组里这个数都只出现一次。单次数双放对于出现 1 次的数b 和 c 数组在这个位置都直接放 a [i]。这一步是整个算法的灵魂它让两个数组的匹配数自动都达到了 n-kk 是出现 2 次的数的个数而 k≤n/2所以自动满足 至少 n/2 个匹配 的要求。循环填空位把 a 中没出现过的数收集起来循环填充到 b 和 c 数组剩下的空位里保证两个数组都是合法的排列。#includebits/stdc.h using namespace std; const int N2e510; int a[N]; int x[N],y[N]; int cnt[N]; bool st[N]; int main() { int n; cinn; for(int i1;in;i)cina[i]; for(int i1;in;i) { if(a[i]n) { cout-1endl; return 0; } cnt[a[i]]; if(cnt[a[i]]2) { cout-1endl; return 0; } } queueintq; for(int i1;in;i) { if(cnt[i]0)q.push(i); } for(int i1;in;i) { if(cnt[a[i]]2) { if(!st[a[i]]) { x[i]a[i]; st[a[i]]true; } else y[i]a[i]; } } for(int i1;in;i) { if(cnt[a[i]]2) { if(x[i])coutx[i] ; else { coutq.front() ; q.push(q.front()); q.pop(); } } else couta[i] ; } coutendl; for(int i1;in;i) { if(cnt[a[i]]2) { if(y[i])couty[i] ; else { coutq.front() ; q.push(q.front()); q.pop(); } } else couta[i] ; } return 0; }E题小红的染色生成树最小生成树强制加边核心目标找一棵原图的生成树满足恰好包含两种颜色的边不能是单色也不能是三色是合法的生成树n-1 条边连通所有节点无环关键发现颜色只有三种所以可能的双色组合一共只有 3 种暴力枚举完全可行时间复杂度毫无压力直接跑 Kruskal 会踩坑如果其中一种颜色的边本身就能连通整个图普通 Kruskal 会生成一棵单色树不符合题目要求强制加边就能解决问题只要在跑 Kruskal 之前先手动加入一条第一种颜色和一条第二种颜色的边就能 100% 保证生成树是双色的核心逻辑枚举所有组合依次检查 (0,1)、(0,2)、(1,2) 这三种双色组合第一步可行性检查检查图中是否同时存在这两种颜色的边如果缺一种直接跳过这个组合检查只用这两种颜色的边能不能把整个图连通如果不能也跳过第二步强制加边最关键的一步随便找一条第一种颜色的边加入生成树合并它的两个端点再随便找一条第二种颜色的边加入生成树合并它的两个端点这一步直接解决了 生成单色树 的大坑保证了最终的树一定有两种颜色第三步补全剩余边用标准的 Kruskal 算法遍历所有边只要是这两种颜色的边并且不会形成环就加入生成树直到生成树有 n-1 条边为止输出结果只要找到一个合法的生成树就直接输出并结束程序#includebits/stdc.h using namespace std; const int N100010,M200010; int p[N]; int n,m; struct Edge { int a,b,w; }edges[M]; int find(int u) { if(p[u]!u) p[u]find(p[u]); return p[u]; } bool check(int c1,int c2) { for(int i1;in;i) p[i]i; for(int i0;im;i) { int aedges[i].a,bedges[i].b,wedges[i].w; if(wc1 || wc2) { afind(a),bfind(b); if(a!b) p[a]b; } } int rootfind(1); for(int i2;in;i) if(find(i)!root) return false; return true; } int find_edge(int color) { for(int i0;im;i) if(edges[i].wcolor) return i; return -1; } int main() { cinnm; for(int i0;im;i) { int a,b,w; cinabw; edges[i]{a,b,w}; } int pairs[3][2]{{0,1},{0,2},{1,2}}; for(int k0;k3;k) { int c1pairs[k][0],c2pairs[k][1]; bool has1false,has2false; for(int i0;im;i) { if(edges[i].wc1) has1true; if(edges[i].wc2) has2true; } if(!has1 || !has2) continue; if(!check(c1,c2)) continue; int res[N]; int cnt0; for(int i1;in;i) p[i]i; int e1find_edge(c1); res[cnt]e1; p[find(edges[e1].a)]find(edges[e1].b); int e2find_edge(c2); res[cnt]e2; p[find(edges[e2].a)]find(edges[e2].b); for(int i0;im cntn-1;i) { int aedges[i].a,bedges[i].b,wedges[i].w; if(wc1 || wc2) { afind(a),bfind(b); if(a!b) { res[cnt]i; p[a]b; } } } for(int i0;icnt;i) { coutedges[res[i]].a edges[res[i]].bendl; } return 0; } cout-1endl; return 0; }其实有心的人已经发现了这次的题解是AI帮我写的但是代码都是我自己比赛时写的有时候自己说不清楚借AI之口让大家明白何乐而不为呢