锐客网

  1. 首页 > it技术 > >

Codeforces|Codeforces Round #535 (Div. 3) 题解

Codeforces Round #535 (Div. 3)
题目总链接：https://codeforces.com/contest/1108
太懒了啊~好久之前的我现在才更新，赶紧补上吧，不能漏掉了。
A. Two distinct points
题意：
【Codeforces|Codeforces Round #535 (Div. 3) 题解】给出两个区间的左右边界，输出两个数，满足两个数分别在两个区间内且这两个数不相等。

题解：
直接输出左端点然后判断一下就行了。
代码如下：
Codeforces|Codeforces Round #535 (Div. 3) 题解
文章图片
Codeforces|Codeforces Round #535 (Div. 3) 题解
文章图片

#include using namespace std; typedef long long ll; int q; int l1,r1,l2,r2; int main(){ cin>>q; for(int i=1; i<=q; i++){ cin>>l1>>r1>>l2>>r2; if(l1==l2) l2++; cout<
View Code
B. Divisors of Two Integers
题意：
给出n个数，这n个数都为两个数的因子，最后要求你输出这两个数为什么。

题解：
既然是因子，那么答案也肯定包含在这n个数中，并且因子应该是较大的数。
那么我们排序后从后往前枚举，遇到一个没有被删除的数我们就把它当作我们的答案，并且在其它数中删掉它的因子。
代码如下：
Codeforces|Codeforces Round #535 (Div. 3) 题解
文章图片
Codeforces|Codeforces Round #535 (Div. 3) 题解
文章图片
#include using namespace std; typedef long long ll; const int N = 200; int n; int d[N],del[N]; vector vec[N]; int main(){ scanf("%d",&n); for(int i=1; i<=n; i++) scanf("%d",&d[i]); sort(d+1,d+n+1); for(int i=1; i<=n; i++){ int x=d[i]; for(int j=2; j*j<=x; j++){ if(x%j==0){ vec[i].push_back(j); if(j*j!=x) vec[i].push_back(x/j); } } } for(int i=n; i>=1; i--){ if(del[i]) continue ; int cnt = 0; while(cnt
View Code
C. Nice Garland
题意：
给出一个字符串，这个字符串只由三个大写字母"B","G","R"构成，然后问你最少需要修改多少个字符，可以使得这个串成为一个“好串”。
好串的定义是，对于每一个字符，它和其它相同字符位置相差都为3的倍数。

题解：
因为相差都为3的倍数，那么我们可以断定前三个字符是互不相同的，并且之后每三个字符也是互不相同的。
另外也可以知道，后面的位置与前三个的位置是一一对应的，这样才满足相差为3的倍数这个条件。
那么我们就枚举前三个的所有可能情况，然后根据这个去统计后面需要的修改次数，最后取最小值就行了。
直接枚举太麻烦，所以使用全排列函数next_permutation。
代码如下：
Codeforces|Codeforces Round #535 (Div. 3) 题解
文章图片
Codeforces|Codeforces Round #535 (Div. 3) 题解
文章图片
#include using namespace std; typedef long long ll; const int N = 2e5+5; int n; char s[N],a[N]; char p[10]={'R','B','G'}; int main(){ scanf("%d",&n); scanf("%s",s); int ans = 0; sort(p,p+3); ans=0x3f3f3f3f3f; int tot=0; do{ tot++; int cnt = 0; for(int i=0; icnt){ ans=cnt; for(int i=0; i<3; i++) a[i]=p[i]; } }while(next_permutation(p,p+3)); cout
View Code
D. Diverse Garland
题意：
还是给出一个只由"R","G","B"构成的字符串，现在问最少的修改次数使得两两相邻的字符不想等为多少。

题解：
这题可以dp吧，但是我是直接贪心来做的。
直接这样想，对于一段连续且相等的串，我们只需要改变其偶数位置就行了。注意一下改变的时候不要和前面以及后面的相等了。
代码如下：
Codeforces|Codeforces Round #535 (Div. 3) 题解
文章图片
Codeforces|Codeforces Round #535 (Div. 3) 题解
文章图片
#include using namespace std; typedef long long ll; const int N = 2e5+5; int n; char s[N],p[N]; char a[N]={'R','B','G'}; void change(int x){ for(int i=0; i<3; i++){ p[x]=a[i]; if(p[x]!=s[x-1] && p[x]!=s[x+1]) return ; } return ; } int main(){ scanf("%d",&n); scanf("%s",s+1); int ans = 0; int tot=0; for(int i=1; i<=n; i++) p[i]=s[i]; for(int i=1; i<=n; i++){ if(s[i]!=s[i-1]) tot=1; else{ tot++; if(tot%2==0){ change(i); ans++; } } } cout View Code
E1. Array and Segments (Easy version)
题意：
给出n个数ai以及m个区间，现在要求你选择一些区间，然后每个区间里面的所有数减去1，最后问选择区间过后，n个数中最大值减去最小值最大为多少。

题解：
简单版本的数据范围比较小，直接暴力就行了。
暴力的话考虑枚举最后最小的位置是哪一个，然后就选择所有覆盖这个点的区间，暴力计算就ok。
代码如下：
Codeforces|Codeforces Round #535 (Div. 3) 题解
文章图片
Codeforces|Codeforces Round #535 (Div. 3) 题解
文章图片
#include #define INF 0x3f3f3f3f using namespace std; typedef long long ll; const int N = 305,M = 305; int a[N],mx[N],mn[N],b[N]; struct seg{ int l,r,id; bool operator < (const seg &A)const{ return r=1; i--) mx[i]=max(mx[i+1],a[i]); for(int i=n; i>=1; i--) mn[i]=min(mn[i+1],a[i]); int ans = mx[1]-mn[1]; int num=0; for(int i=1; i<=n; i++){ for(int j=1; j<=n; j++) a[j]=b[j]; for(int j=1; j<=m; j++){ if(p[j].l<=i && p[j].r>=i){ for(int k=p[j].l; k<=p[j].r; k++) a[k]--; } } int minx = INF,maxx = -INF; for(int j=1; j<=n; j++) minx=min(minx,a[j]),maxx=max(maxx,a[j]); if(ans vec; for(int i=1; i<=m; i++){ if(p[i].l<=num && p[i].r>=num) tot++,vec.push_back(p[i].id); } cout<
View Code
E2. Array and Segments (Hard version)
题意：
这题和E1的题目描述都是一样的，不同的就是数据范围变大了，现在是n<=1e5,m<=300，显然不能直接暴力枚举每个最小值了。

题解：
区间个数还是那么多，注意到区间个数比n小很多，那么我们可以考虑离散化，这样数轴上最多只剩下600个点，然后我们记录一下每一段的最大最小值。
这样段数也只有最多600个，区间还是300个，暴力枚举就不会超时了。
为啥可以把每一段看成点呢？因为对于被区间“分隔”的每一段区间，它们所拥有的区间覆盖都是相同的，这个画下图就知道了。
给出代码:
Codeforces|Codeforces Round #535 (Div. 3) 题解
文章图片
Codeforces|Codeforces Round #535 (Div. 3) 题解
文章图片
#include #define INF 0x3f3f3f3f using namespace std; typedef long long ll; const int N = 1e5+5,M = 305; int a[N],l[N],r[N],b[N],c[N]; int n,m,tot; int mx[N],mn[N]; int main(){ scanf("%d%d",&n,&m); for(int i=1; i<=n; i++) scanf("%d",&a[i]); for(int i=1; i<=m; i++){ scanf("%d%d",&l[i],&r[i]); r[i]++; b[++tot]=l[i]; b[++tot]=r[i]; } b[++tot]=1; b[++tot]=n+1; sort(b+1,b+tot+1); tot = unique(b+1,b+tot+1)-(b+1); for(int i=1; i<=m; i++){ l[i]=lower_bound(b+1,b+tot+1,l[i])-b; r[i]=lower_bound(b+1,b+tot+1,r[i])-b; } int t1=-INF,t2=INF; for(int i=1; i ans[N]; int Ans=t1-t2,pos=0; for(int x=1; xx) ans[x].push_back(j); } if(!ans[x].size()) continue ; for(auto v:ans[x]){ c[l[v]]--; c[r[v]]++; } int s = 0,minx = INF,t=0,maxx=-INF; for(int i=1; imaxx) maxx=mx[i]+s; } if(maxx-minx>Ans){ Ans=maxx-minx; pos=x; } } cout
View Code
还有一种更巧妙地解法，用不上离散化，直接搞就是了。
就是还是从1~n进行枚举，只有当前点为某个区间的端点时进行更新，然后再暴力求最大最小值来计算。
这个复杂度是O(n*m)的。
代码如下：
Codeforces|Codeforces Round #535 (Div. 3) 题解
文章图片
Codeforces|Codeforces Round #535 (Div. 3) 题解
文章图片
#include #define INF 0x3f3f3f3f using namespace std; typedef long long ll; const int N = 1e5+5,M = 305; int n,m; int a[N],b[N],l[N],r[N]; vector pl[N],pr[N]; int main(){ cin>>n>>m; int mx = -INF ,mn= INF; for(int i=1; i<=n; i++){ scanf("%d",&a[i]); mx=max(mx,a[i]); mn=min(mn,a[i]); } for(int i=1; i<=m; i++){ scanf("%d%d",&l[i],&r[i]); pl[l[i]].push_back(i); pr[r[i]+1].push_back(i); } int ans = mx-mn,pos=-1,tmp; for(int i=1; i<=n; i++){ int len1=pl[i].size(),len2=pr[i].size(); if(len1){ for(auto v:pl[i]){ for(int j=l[v]; j<=r[v]; j++) a[j]--; } } if(len2){ for(auto v:pr[i]){ for(int j=l[v]; j<=r[v]; j++) a[j]++; } } if(len1 || len2){ mx = -INF,mn = INF; for(int i=1; i<=n; i++){ mx=max(mx,a[i]); if(a[i]ans){ ans=mx-mn; pos=tmp; } } } } cout=pos) cnt++; } cout<=pos) cout<
View Code
F. MST Unification
题意：
给出一个无向图，每条边有相应边权，然后现在你可以对某些边的边权加上一个值。
现在问你最少需要多少次操作，可以使得这个图的最小生成树唯一。

题解：
这个思路还是挺巧妙的，也是求最小生成树。我们假设目前边权为x的边有c条，那么我们先剔除不用的边a，再尽可能地在途中加边b，最后的c-a-b条边就是我们需要对其进行操作的边。
然后稍微修改一下Kruskal就行了，具体见代码吧：
Codeforces|Codeforces Round #535 (Div. 3) 题解
文章图片
Codeforces|Codeforces Round #535 (Div. 3) 题解
文章图片
#include using namespace std; typedef long long ll; const int N = 2e5+5; int n,m; int f[N]; struct Edge{ int u,v,w; bool operator <(const Edge &A)const{ return w
View Code
这份题解总算写完了~还有几个找时间再补吧。
转载于:https://www.cnblogs.com/heyuhhh/p/10352569.html

    推荐阅读


    上一篇：一次遍历，等概率随机排列数组与带权随机选取问题

    下一篇：从产品角度读《产品心经》