Codeforces Round #535 (Div. 3)
题目总链接：https://codeforces.com/contest/1108
太懒了啊~好久之前的我现在才更新，赶紧补上吧，不能漏掉了。
A. Two distinct points
题意：
给出两个区间的左右边界，输出两个数，满足两个数分别在两个区间内且这两个数不相等。
题解：
直接输出左端点然后判断一下就行了。
代码如下：
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int q;
int l1,r1,l2,r2;
int main(){
cin>>q;
for(int i=;i<=q;i++){
cin>>l1>>r1>>l2>>r2;
if(l1==l2) l2++;
cout<<l1<<" "<<l2<<endl;
}
return ;
}
B. Divisors of Two Integers
题意：
给出n个数，这n个数都为两个数的因子，最后要求你输出这两个数为什么。
题解：
既然是因子，那么答案也肯定包含在这n个数中，并且因子应该是较大的数。
那么我们排序后从后往前枚举，遇到一个没有被删除的数我们就把它当作我们的答案，并且在其它数中删掉它的因子。
代码如下：
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = ;
int n;
int d[N],del[N];
vector <int> vec[N];
int main(){
scanf("%d",&n);
for(int i=;i<=n;i++) scanf("%d",&d[i]);
sort(d+,d+n+);
for(int i=;i<=n;i++){
int x=d[i];
for(int j=;j*j<=x;j++){
if(x%j==){
vec[i].push_back(j);
if(j*j!=x) vec[i].push_back(x/j);
}
}
}
for(int i=n;i>=;i--){
if(del[i]) continue ;
int cnt = ;
while(cnt<vec[i].size()){
for(int j=;j<=i;j++){
if(del[j]) continue ;
if(d[j]==vec[i][cnt]){
cnt++;
del[j]=;
break ;
}
}
}
}
int tot=;
for(int i=;i<=n;i++) if(!del[i]) tot++;
int now = ;
int x=,y=;
for(int i=;i<=n;i++){
if(now==tot-){
if(!del[i]) y*=d[i];
}
else if(!del[i]) x*=d[i],now++;
}
cout<<x<<" "<<y;
return ;
}
C. Nice Garland
题意：
给出一个字符串，这个字符串只由三个大写字母"B","G","R"构成，然后问你最少需要修改多少个字符，可以使得这个串成为一个“好串”。
好串的定义是，对于每一个字符，它和其它相同字符位置相差都为3的倍数。
题解：
因为相差都为3的倍数，那么我们可以断定前三个字符是互不相同的，并且之后每三个字符也是互不相同的。
另外也可以知道，后面的位置与前三个的位置是一一对应的，这样才满足相差为3的倍数这个条件。
那么我们就枚举前三个的所有可能情况，然后根据这个去统计后面需要的修改次数，最后取最小值就行了。
直接枚举太麻烦，所以使用全排列函数next_permutation。
代码如下：
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 2e5+;
int n;
char s[N],a[N];
char p[]={'R','B','G'};
int main(){
scanf("%d",&n);
scanf("%s",s);
int ans = ;
sort(p,p+);
ans=0x3f3f3f3f3f;
int tot=;
do{
tot++;
int cnt = ;
for(int i=;i<min(n,);i++){
if(p[i]!=s[i]) cnt++;
}
for(int i=;i<n;i++){
if(p[i%]!=s[i]) cnt++;
}
if(ans>cnt){
ans=cnt;
for(int i=;i<;i++) a[i]=p[i];
}
}while(next_permutation(p,p+));
cout<<ans<<endl;
for(int i=;i<n;i++) cout<<a[i%];
return ;
}
D. Diverse Garland
题意：
还是给出一个只由"R","G","B"构成的字符串，现在问最少的修改次数使得两两相邻的字符不想等为多少。
题解：
这题可以dp吧，但是我是直接贪心来做的。
直接这样想，对于一段连续且相等的串，我们只需要改变其偶数位置就行了。注意一下改变的时候不要和前面以及后面的相等了。
代码如下：
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 2e5+;
int n;
char s[N],p[N];
char a[N]={'R','B','G'};
void change(int x){
for(int i=;i<;i++){
p[x]=a[i];
if(p[x]!=s[x-] && p[x]!=s[x+]) return ;
}
return ;
}
int main(){
scanf("%d",&n);
scanf("%s",s+);
int ans = ;
int tot=;
for(int i=;i<=n;i++) p[i]=s[i];
for(int i=;i<=n;i++){
if(s[i]!=s[i-]) tot=;
else{
tot++;
if(tot%==){
change(i);
ans++;
}
}
}
cout<<ans<<endl;
for(int i=;i<=n;i++) cout<<p[i];
return ;
}
E1. Array and Segments (Easy version)
题意：
给出n个数ai以及m个区间，现在要求你选择一些区间，然后每个区间里面的所有数减去1，最后问选择区间过后，n个数中最大值减去最小值最大为多少。
题解：
简单版本的数据范围比较小，直接暴力就行了。
暴力的话考虑枚举最后最小的位置是哪一个，然后就选择所有覆盖这个点的区间，暴力计算就ok。
代码如下：
#include <bits/stdc++.h>
#define INF 0x3f3f3f3f
using namespace std;
typedef long long ll;
const int N = ,M = ;
int a[N],mx[N],mn[N],b[N];
struct seg{
int l,r,id;
bool operator < (const seg &A)const{
return r<A.r;
}
}p[M];
int n,m;
int main(){
scanf("%d%d",&n,&m);
for(int i=;i<=n;i++) scanf("%d",&a[i]),b[i]=a[i];
for(int i=;i<=m;i++) scanf("%d%d",&p[i].l,&p[i].r),p[i].id=i;
sort(p+,p+m+);
memset(mn,INF,sizeof(mn));
for(int i=;i<=n+;i++) mx[i]=-INF;
for(int i=n;i>=;i--)
mx[i]=max(mx[i+],a[i]);
for(int i=n;i>=;i--)
mn[i]=min(mn[i+],a[i]);
int ans = mx[]-mn[];
int num=;
for(int i=;i<=n;i++){
for(int j=;j<=n;j++) a[j]=b[j];
for(int j=;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=;j<=n;j++) minx=min(minx,a[j]),maxx=max(maxx,a[j]);
if(ans<maxx-minx){
ans=maxx-minx;
num=i;
}
}
cout<<ans<<endl;
int tot=;
vector <int> vec;
for(int i=;i<=m;i++){
if(p[i].l<=num && p[i].r>=num) tot++,vec.push_back(p[i].id);
}
cout<<tot<<endl;
for(auto v:vec) cout<<v<<" ";
return ;
}
E2. Array and Segments (Hard version)
题意：
这题和E1的题目描述都是一样的，不同的就是数据范围变大了，现在是n<=1e5,m<=300，显然不能直接暴力枚举每个最小值了。
题解：
区间个数还是那么多，注意到区间个数比n小很多，那么我们可以考虑离散化，这样数轴上最多只剩下600个点，然后我们记录一下每一段的最大最小值。
这样段数也只有最多600个，区间还是300个，暴力枚举就不会超时了。
为啥可以把每一段看成点呢？因为对于被区间“分隔”的每一段区间，它们所拥有的区间覆盖都是相同的，这个画下图就知道了。
给出代码:
#include <bits/stdc++.h>
#define INF 0x3f3f3f3f
using namespace std;
typedef long long ll;
const int N = 1e5+,M = ;
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=;i<=n;i++) scanf("%d",&a[i]);
for(int i=;i<=m;i++){
scanf("%d%d",&l[i],&r[i]);
r[i]++;
b[++tot]=l[i];
b[++tot]=r[i];
}
b[++tot]=;b[++tot]=n+;
sort(b+,b+tot+);
tot = unique(b+,b+tot+)-(b+);
for(int i=;i<=m;i++){
l[i]=lower_bound(b+,b+tot+,l[i])-b;
r[i]=lower_bound(b+,b+tot+,r[i])-b;
}
int t1=-INF,t2=INF;
for(int i=;i<tot;i++){
mx[i]=mn[i]=a[b[i]];
for(int j=b[i]+;j<b[i+];j++){
mx[i]=max(mx[i],a[j]);
mn[i]=min(mn[i],a[j]);
}
t1=max(t1,mx[i]);t2=min(t2,mn[i]);
}
vector <int> ans[N];
int Ans=t1-t2,pos=;
for(int x=;x<tot;x++){
memset(c,,sizeof(c));
for(int j=;j<=m;j++){
if(l[j]<=x && r[j]>x)
ans[x].push_back(j);
}
if(!ans[x].size()) continue ;
for(auto v:ans[x]){
c[l[v]]--;c[r[v]]++;
}
int s = ,minx = INF,t=,maxx=-INF;
for(int i=;i<tot;i++){
s+=c[i];
if(!t || mn[i]+s<minx) minx=mn[t=i]+s;
}
s = ;
for(int i=;i<tot;i++){
s+=c[i];
if(mx[i]+s>maxx) maxx=mx[i]+s;
}
if(maxx-minx>Ans){
Ans=maxx-minx;
pos=x;
}
}
cout<<Ans<<endl<<ans[pos].size()<<endl;
for(auto v:ans[pos]) cout<<v<<" ";
return ;
}
还有一种更巧妙地解法，用不上离散化，直接搞就是了。
就是还是从1~n进行枚举，只有当前点为某个区间的端点时进行更新，然后再暴力求最大最小值来计算。
这个复杂度是O(n*m)的。
代码如下：
#include <bits/stdc++.h>
#define INF 0x3f3f3f3f
using namespace std;
typedef long long ll;
const int N = 1e5+,M = ;
int n,m;
int a[N],b[N],l[N],r[N];
vector <int> pl[N],pr[N];
int main(){
cin>>n>>m;
int mx = -INF ,mn= INF;
for(int i=;i<=n;i++){
scanf("%d",&a[i]);
mx=max(mx,a[i]);
mn=min(mn,a[i]);
}
for(int i=;i<=m;i++){
scanf("%d%d",&l[i],&r[i]);
pl[l[i]].push_back(i);
pr[r[i]+].push_back(i);
}
int ans = mx-mn,pos=-,tmp;
for(int i=;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=;i<=n;i++){
mx=max(mx,a[i]);
if(a[i]<mn){
mn=a[i];
tmp=i;
}
if(mx-mn>ans){
ans=mx-mn;
pos=tmp;
}
}
}
}
cout<<ans<<endl;
int cnt = ;
for(int i=;i<=m;i++){
if(l[i]<=pos && r[i]>=pos) cnt++;
}
cout<<cnt<<endl;
for(int i=;i<=m;i++){
if(l[i]<=pos && r[i]>=pos) cout<<i<<" ";
}
return ;
}
F. MST Unification
题意：
给出一个无向图，每条边有相应边权，然后现在你可以对某些边的边权加上一个值。
现在问你最少需要多少次操作，可以使得这个图的最小生成树唯一。
题解：
这个思路还是挺巧妙的，也是求最小生成树。我们假设目前边权为x的边有c条，那么我们先剔除不用的边a，再尽可能地在途中加边b，最后的c-a-b条边就是我们需要对其进行操作的边。
然后稍微修改一下Kruskal就行了，具体见代码吧：
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 2e5+;
int n,m;
int f[N];
struct Edge{
int u,v,w;
bool operator <(const Edge &A)const{
return w<A.w;
}
}e[N];
int find(int x){
return f[x]==x ? f[x] : f[x]=find(f[x]);
}
int main(){
scanf("%d%d",&n,&m);
for(int i=;i<=m;i++){
int u,v,w;
scanf("%d%d%d",&u,&v,&w);
e[i]={u,v,w};
}
sort(e+,e+m+);
for(int i=;i<=n+;i++) f[i]=i;
int ans = ;
for(int i=,j=;i<=m;i=j){
while(e[i].w==e[j].w) j++;
int cnt = j-i;
for(int k=i;k<j;k++){
int fx=find(e[k].u),fy=find(e[k].v);
if(fx==fy) cnt--;
}
for(int k=i;k<j;k++){
int fx=find(e[k].u),fy=find(e[k].v);
if(fx==fy) continue ;
cnt--;
f[fx]=fy;
}
ans+=cnt;
}
cout<<ans;
return ;
}
这份题解总算写完了~还有几个找时间再补吧。