本文主要是介绍Codeforces Round 923 (Div. 3)补题，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
Make it White（Problem - A - Codeforces）
题目大意：有一排格子，其中有黑色和白色两种，我们选择一个区间，将区间中的格子全部染成白色，只能选一次，问将这一排格子都染成白色，选择的区间最短为多少。
思路：显然就是从前往后从后往前分别找到第一个'B'的位置。我最开始用的双指针，但是边界什么好像没处理好，直接死循环了，最后直接分开写了两个循环。但是耽误了一会儿，还是太可惜了。
#include<bits/stdc++.h>
using namespace std;
int main()
{int t;scanf("%d",&t);while(t--){int n;scanf("%d",&n);string s;cin>>s;int flag=0;int i,j;for(i=0;i<n;i++){if(s[i]=='B')break;}for(j=n-1;j>=0;j--){if(s[j]=='B')break;}int ans=j-i+1;printf("%d\n",ans);}
}Following the String（Problem - B - Codeforces）
题目大意：有一个字符串，我们不知道具体的值，但是我们知道每位之前有多少个和它相同的字母，请找出一个合法的字符串。
思路：这道题的数据范围看似很大，但是实际上可以暴力来写。也就是我们用一个st[]数组标记每个数选了多少次，每遍历一位就从st中循环去找。n,t拉满的话，时间复杂度看似到了2e9*30,但实际上不会拉满，所以不用担心。
#include<bits/stdc++.h>
using namespace std;
int a[200010];
int st[30];
int main()
{int t;scanf("%d",&t);while(t--){int n;scanf("%d",&n);for(int i=1;i<=n;i++) scanf("%d",&a[i]);int x=0;for(int i=0;i<26;i++) st[i]=0;for(int i=1;i<=n;i++){for(int j=0;j<26;j++){if(a[i]==st[j]){char c='a'+j;printf("%c",c);st[j]++;break;}}}printf("\n");}
}
Choose the Different Ones!（Problem - C - Codeforces）
题目大意：现有一个长为n的数组a[],一个长为m的数组b[],一个偶数k，问能否在a[]中选取k/2个数，b中选取k/2数，这些数恰好可以构成一个k排列。
思路：这题既要从a[]中选，又要从b[]中选，而且还要各k/2个，另外两者中小于等于k的元素还有可能重复，看似很麻烦，但是实际上我们只需要用一个数组进行标记，属于a[]的标记成1，属于b[]的标记成2,那么同属于两者的就是3，然后我们遍历1-k，同属于两者的先不管，只把个数统计出来，然后再统计一下1-k中独属于a和独属于b的个数，这两个数应该都小于等于k/2，因为是独属于，如果大于k/2，那么另一个中一定没办法选出k/2个合法的数，然后两者再加上共同的，一定是为k的，否则就选不出k个数，一旦这些都没否定掉，那么就是可以的。另外要注意一点，两个数组中的数字只能被统计一次，我们可以额外用一个数组标记。
#include<bits/stdc++.h>
using namespace std;
int st[400010],vis[400010];
int main()
{int t;scanf("%d",&t);while(t--){int n,m,k;scanf("%d%d%d",&n,&m,&k);int x;for(int i=0;i<=k;i++)st[i]=vis[i]=0;for(int i=1;i<=n;i++) {scanf("%d",&x);if(x<=k&&vis[x]!=1) st[x]+=1,vis[x]=1;}for(int i=1;i<=m;i++) {scanf("%d",&x);if(x<=k&&vis[x]!=2) st[x]+=2,vis[x]=2;}int d=k/2;int a=0,b=0,c=0;for(int i=1;i<=k;i++){if(st[i]>=3) c++;if(st[i]==1) a++;if(st[i]==2) b++;}if(a>d||b>d) printf("NO\n");else if(a+b+c<k) printf("NO\n");else printf("YES\n");}
}Find the Different Ones!（Problem - D - Codeforces）
题目大意：现有一个数组a[],我们给定q个查询，每个查询中有一段区间，判断区间中是否可以找出两个不同的数，如果可以那么输出下标，如果不可以那么输出"-1 -1".
思路：这里有多组查询，但是没有修改，所以我们可以用静态数组预处理出来一些东西，进而实现查询。这里我们可以预处理一个数前面第一个与它不同的数在哪里，再预处理每个数后面第一个与它不同的数在哪里。这里实际上有转移方程，我们以找前面那个与它不同的数为例：
令pre[i]表示a[i]前面第一个与a[i]不同的数在哪里：
if(a[i]!=a[i-1])pre[i]=i-1;
else pre[i]=pre[i-1];//如果这两个数相同，那么与前面那个数最近的相异的数，自然也是与后面这个数最近的相异的数。
在查询的时候，我们只需要判断，l后面第一个与它不同的数是否小于等于r，r前面最近的与它不同的数是否大于等于l，如果都不满足就输出"-1 -1"
#include<bits/stdc++.h>
using namespace std;
int a[200010],pre[200010],las[200010];
int main()
{int t;scanf("%d",&t);while(t--){int n;scanf("%d",&n);for(int i=1;i<=n;i++) scanf("%d",&a[i]);a[n+1]=0;for(int i=1;i<=n;i++){if(a[i]!=a[i-1]) pre[i]=i-1;else pre[i]=pre[i-1];}for(int i=n;i>=1;i--){if(a[i]!=a[i+1]) las[i]=i+1;else las[i]=las[i+1];}int q;scanf("%d",&q);while(q--){int l,r;scanf("%d%d",&l,&r);if(las[l]<=r) printf("%d %d\n",l,las[l]);else if(pre[r]>=l) printf("%d %d\n",pre[r],r);else printf("-1 -1\n");}printf("\n");}
}Klever Permutation(Problem - E - Codeforces)
题目大意：我们需要找出一个排列，满足任意连续k个数相加得到的和，差值不超过1.
思路：我们先通过相邻的来找一找规律：
n=6 k=4
a b c d e f
a+b+c+d
b+c+d+e
c+d+e+f
显然就是a与e之间的差值不超过1,b与f之间的差值不超过1，而且它们下标的间距是k,所以我们可以按照这个规律将数组填出来。但是如果这么来填的话第一组和第三组和的差就不满足要求了，如果它们要满足要求的话，那么就要看a+b与e+f之间的关系，|a-e|<=1,|b-f|<=1，因为是排列所以不能有相同的数，那么就是|a-e|==1,|b-f|==1，所以可以令a-e=1,b-f=-1,那么就符合要求了。所以就可以这么来填数组，填第奇数轮的时候递增1来填，填第偶数轮的时候递减来填。
#include<bits/stdc++.h>
using namespace std;
int a[200010],st[200010];
int main()
{int t;scanf("%d",&t);while(t--){int n,k;scanf("%d%d",&n,&k);for(int i=1;i<=n;i++) st[i]=0;int x=1,y=n,c=1;for(int i=1;i<=n;i++){if(!st[i]){if(c%2){for(int j=i;j<=n;j+=k){st[j]=1;a[j]=y--;}}else{for(int j=i;j<=n;j+=k){st[j]=1;a[j]=x++;}}c++;}}for(int i=1;i<=n;i++) printf("%d ",a[i]);printf("\n");}
}Microcycle(Problem - F - Codeforces)
题目大意：现在有一个无向图，我们可以在图中找到若干简单循环，简单循环的意思就是一个没有重复边的循环，也即我们从一个点出发最后回到这个点，不会经过重复的边。每条边都由一个边权，每个简单循环中都有一条边权最小的边，我们要找到所有简单循环中边权最小的边中最轻的边，同时输出这个简单循环。
思路：这里引入桥边的概念
图中的蓝边就是桥，那么很显然桥边不在简单循环中，我们可以找到非桥边中最轻的，然后从它的一个端点遍历到另一个端点的循环就是题目要找的简单循环。找非桥边可以用Tarjan算法，但是我还没学到Tarjan算法，所以这里用并查集来实现。显然非桥边可以连接两个集合，所以我们只需要将所有边按照边权从大到小排序，然后依次判断每条边是否能够连通两个不同的并查集，如果可以的话，那么就是桥，如果不可以那么我们就可以记录它，因为它是非桥边，因为我们按照边权从大到小排序，所以最后一个被记录的非桥边就是我们要找的边。找到这个边之后我们再进行dfs就可以实现。这里有一些小的细节我们一点一点来讨论清楚：
首先是按照边权从大到小排序，有两种实现思路：
1.结构体优先队列，这里就需要在结构体中写一下重载函数。
struct edge
{int a,b,c; bool operator<(const edge other)const{return c<other.c;}
};
priority_queue<edge>q;因为优先队列是大顶堆，所以我们的重载函数需要反一下。
2.用vector<>写，再手写一个cmp函数，这个实现比较简单，就不展开叙述。
然后是并查集，find函数：
int find(int x)
{if(p[x]!=x) p[x]=find(p[x]); return p[x];
}这个要一定要记得把p[x]更新一下。
另外我们在建边的时候，因为最开始一条边都没有，所以有一些非桥边会被当成桥边，但是由于我们是从大到小访问的所有边，所以每个简单循环中的最轻的那条边一定会被记录下来，因为这条边一定是这个循环中最后被加入的边，它的两个端点一定属于同一个集合。
idx=0;memset(h,-1,sizeof h);while(q.size()){auto it=q.top();q.pop();int u=it.a,v=it.b,w=it.c;int x=find(u),y=find(v);if(x==y) mi=w,l=u,r=v;else//非桥边需要连起来{add(u,v,w);add(v,u,w);p[x]=y;}}而且对于每一个循环，我们实际上将最轻的那条边断开了，所以不用担心死循环。
查找的时候，我还是按照完整的循环来写的，也就是哪怕循环是完整的也可以这么来实现。用了两个vector<int>容器，一个用来记录最终的答案，一个用来记录每一步搜索的状态。同时定义了一个全局变量用来表示是否找到了，这样就可以及时退出避免多搜（在完整循环的时候）。
#include<bits/stdc++.h>
using namespace std;
struct edge
{int a,b,c; bool operator<(const edge other)const{return c<other.c;}
};
int h[200010],e[400010],ne[400010],w[400010],idx;
void add(int a,int b,int c)
{e[idx]=b,w[idx]=c,ne[idx]=h[a],h[a]=idx++;
}
vector<int>ans,path;
bool found;
void dfs(int v,int p,int f)
{path.push_back(v);if(v == f){ans = path;found = true;return;}for(int i=h[v];i!=-1;i=ne[i]){int j=e[i];if(j!=p) dfs(j,v,f);if(found) return;}path.pop_back();
}
int p[200010];
int find(int x)
{if(p[x]!=x) p[x]=find(p[x]); return p[x];
}
int main()
{int t;scanf("%d",&t);while(t--){int n,m;scanf("%d%d",&n,&m);for(int i=1;i<=n;i++) p[i]=i;priority_queue<edge>q;for(int i=1;i<=m;i++){int a,b,c;scanf("%d%d%d",&a,&b,&c);q.push({a,b,c});}int mi,l,r;idx=0;memset(h,-1,sizeof h);while(q.size()){auto it=q.top();q.pop();int u=it.a,v=it.b,w=it.c;int x=find(u),y=find(v);if(x==y) mi=w,l=u,r=v;else//非桥边需要连起来{add(u,v,w);add(v,u,w);p[x]=y;}}path.clear();ans.clear();found=0;dfs(l,l,r);printf("%d %d\n",mi,ans.size());for(auto it:ans) cout<<it<<" ";cout<<endl;}
}这篇关于Codeforces Round 923 (Div. 3)补题的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
