牛客周赛Round145
这次比较有进步，可能是因为题不是很难吧，A了5个
目录
A题：小红的好串
map
B题：小红的好串计数
双指针
C题：小红的染色平均数
分数计算
核心目标
关键发现
数学推导
最少操作次数计算
D题：小红的排列构造
构造
核心目标
关键发现
核心逻辑
E题：小红的染色生成树
最小生成树+强制加边
核心目标
关键发现
核心逻辑
A题：小红的好串
map
这个主要就是用map统计一下字符出现个数就好了嘛，不用多说
#include<bits/stdc++.h> using namespace std; string s; int main() { cin>>s; unordered_map<char,int>mp; for(int i=0;i<s.size();i++) { mp[s[i]]++; } bool flag=false; for(int i=0;i<s.size();i++) { if(mp[s[i]]==2) { flag=true; break; } } if(flag)cout<<"Yes"<<endl; else cout<<"No"<<endl; return 0; }B题：小红的好串计数
双指针
先算出所有子串的个数，然后再减去不是好串的子串个数就好了，不是子串，就是连续字符相同嘛，就是双指针
#include<bits/stdc++.h> using namespace std; const int N=1e6+10; typedef long long LL; string s; int main() { int n; cin>>n>>s; LL res=1LL*n*(n+1)/2; for(int i=0;i<n;) { int j=i; while(s[i]==s[j]&&j<n)j++; int num=j-i; res-=1LL*num*(num+1)/2; i=j; } cout<<res<<endl; return 0; }C题：小红的染色平均数
分数计算
核心目标
让红色元素的平均值 = 蓝色元素的平均值。
关键发现
- 操作不改变总和：每次 “一加一减”，整个数组的总和不变。
- 只跨颜色操作才有效：同颜色之间的加减，对平均值没任何影响。
数学推导
设：
cnt0：红色元素个数，sum0：红色元素总和cnt1：蓝色元素个数，sum1：蓝色元素总和
要让平均值相等，等价于：sum0 / cnt0 = sum1 / cnt1交叉相乘消分母：sum0 * cnt1 = sum1 * cnt0
最少操作次数计算
每次跨颜色操作，会让上面的差值变化n（总元素个数）。所以最少操作次数就是：|sum0 * cnt1 - sum1 * cnt0| / n。如果差值不能被n整除，就永远不可能实现，输出-1。
#include<bits/stdc++.h> using namespace std; const int N=2e5+10; int a[N]; string s; typedef long long LL; int n; int main() { cin>>n; for(int i=0;i<n;i++)cin>>a[i]; cin>>s; LL sum1=0,sum0=0; LL res1=0,res0=0; for(int i=0;i<n;i++) { if(s[i]=='1') { sum1++; res1+=a[i]; } else { sum0++; res0+=a[i]; } } //cout<<sum1<<' '<<sum0<<endl; //cout<<res1<<' '<<res0<<endl; LL num=sum1+sum0; res1*=sum0; res0*=sum1; //cout<<res1<<' '<<res0<<endl; if(abs(res1-res0)%num) { cout<<-1<<endl; } else { cout<<abs(res1-res0)/num<<endl; } return 0; }D题：小红的排列构造
构造
核心目标
构造两个长度为 n 的排列 b 和 c，满足：
- 每个位置 i，b [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-k（k 是出现 2 次的数的个数），而 k≤n/2，所以自动满足 "至少 n/2 个匹配" 的要求。
- 循环填空位：把 a 中没出现过的数收集起来，循环填充到 b 和 c 数组剩下的空位里，保证两个数组都是合法的排列。
#include<bits/stdc++.h> using namespace std; const int N=2e5+10; int a[N]; int x[N],y[N]; int cnt[N]; bool st[N]; int main() { int n; cin>>n; for(int i=1;i<=n;i++)cin>>a[i]; for(int i=1;i<=n;i++) { if(a[i]>n) { cout<<-1<<endl; return 0; } cnt[a[i]]++; if(cnt[a[i]]>2) { cout<<-1<<endl; return 0; } } queue<int>q; for(int i=1;i<=n;i++) { if(cnt[i]==0)q.push(i); } for(int i=1;i<=n;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 i=1;i<=n;i++) { if(cnt[a[i]]==2) { if(x[i])cout<<x[i]<<' '; else { cout<<q.front()<<' '; q.push(q.front()); q.pop(); } } else cout<<a[i]<<' '; } cout<<endl; for(int i=1;i<=n;i++) { if(cnt[a[i]]==2) { if(y[i])cout<<y[i]<<' '; else { cout<<q.front()<<' '; q.push(q.front()); q.pop(); } } else cout<<a[i]<<' '; } return 0; }E题：小红的染色生成树
最小生成树+强制加边
核心目标
找一棵原图的生成树，满足：
- 恰好包含两种颜色的边（不能是单色，也不能是三色）
- 是合法的生成树（n-1 条边，连通所有节点，无环）
关键发现
- 颜色只有三种：所以可能的双色组合一共只有 3 种，暴力枚举完全可行，时间复杂度毫无压力
- 直接跑 Kruskal 会踩坑：如果其中一种颜色的边本身就能连通整个图，普通 Kruskal 会生成一棵单色树，不符合题目要求
- 强制加边就能解决问题：只要在跑 Kruskal 之前，先手动加入一条第一种颜色和一条第二种颜色的边，就能 100% 保证生成树是双色的
核心逻辑
- 枚举所有组合：依次检查 (0,1)、(0,2)、(1,2) 这三种双色组合
- 第一步：可行性检查
- 检查图中是否同时存在这两种颜色的边，如果缺一种，直接跳过这个组合
- 检查只用这两种颜色的边，能不能把整个图连通，如果不能，也跳过
- 第二步：强制加边（最关键的一步）
- 随便找一条第一种颜色的边，加入生成树，合并它的两个端点
- 再随便找一条第二种颜色的边，加入生成树，合并它的两个端点
- 这一步直接解决了 "生成单色树" 的大坑，保证了最终的树一定有两种颜色
- 第三步：补全剩余边
- 用标准的 Kruskal 算法，遍历所有边
- 只要是这两种颜色的边，并且不会形成环，就加入生成树
- 直到生成树有 n-1 条边为止
- 输出结果：只要找到一个合法的生成树，就直接输出并结束程序
#include<bits/stdc++.h> using namespace std; const int N=100010,M=200010; 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 i=1;i<=n;i++) p[i]=i; for(int i=0;i<m;i++) { int a=edges[i].a,b=edges[i].b,w=edges[i].w; if(w==c1 || w==c2) { a=find(a),b=find(b); if(a!=b) p[a]=b; } } int root=find(1); for(int i=2;i<=n;i++) if(find(i)!=root) return false; return true; } int find_edge(int color) { for(int i=0;i<m;i++) if(edges[i].w==color) return i; return -1; } int main() { cin>>n>>m; for(int i=0;i<m;i++) { int a,b,w; cin>>a>>b>>w; edges[i]={a,b,w}; } int pairs[3][2]={{0,1},{0,2},{1,2}}; for(int k=0;k<3;k++) { int c1=pairs[k][0],c2=pairs[k][1]; bool has1=false,has2=false; for(int i=0;i<m;i++) { if(edges[i].w==c1) has1=true; if(edges[i].w==c2) has2=true; } if(!has1 || !has2) continue; if(!check(c1,c2)) continue; int res[N]; int cnt=0; for(int i=1;i<=n;i++) p[i]=i; int e1=find_edge(c1); res[cnt++]=e1; p[find(edges[e1].a)]=find(edges[e1].b); int e2=find_edge(c2); res[cnt++]=e2; p[find(edges[e2].a)]=find(edges[e2].b); for(int i=0;i<m && cnt<n-1;i++) { int a=edges[i].a,b=edges[i].b,w=edges[i].w; if(w==c1 || w==c2) { a=find(a),b=find(b); if(a!=b) { res[cnt++]=i; p[a]=b; } } } for(int i=0;i<cnt;i++) { cout<<edges[res[i]].a<<' '<<edges[res[i]].b<<endl; } return 0; } cout<<-1<<endl; return 0; }其实有心的人已经发现了，这次的题解是AI帮我写的，但是代码都是我自己比赛时写的，有时候自己说不清楚，借AI之口让大家明白，何乐而不为呢！