Codeforces Round #535 (Div. 3)

提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

E：

题意：

给出n个整数ai和m个区间[li,ri] 你可以选择一些区间，并且将区间内的数字都减一。你要选择一些区间，然后使得改变后的数列中maxbi-minbi的值最大。

题解：

假设我们已经知道了这n个数中最大值的位置pmax,和最小值的位置pmin，那么对于一个区间[li,ri]，有三种情况。

1.如果pmax和pmin在区间[li,ri]内，那么这个区间加不加都对答案没有贡献。

2.如果pmin在区间内pmax不在区间内，那么这个区间加上对答案的贡献就为1

3.如果pmax在区间内pmin不在区间内，那么加上这个区间对答案的贡献为-1.

所以我们发现，只要pmin在区间内的区间，选上它答案一定不会变的更差。

那么n*m的复杂度就可以解决这个问题了，将区间按照左区间排序，从1到n扫，当前i为某个区间的开始或者结束点的时候，更新和消除影响。

F：

题意：

给出n个点和m条边，没有重边和自环。问你最少要给多少条边的权值+1使得MST不变且唯一。

题解：

我们定义一下冲突边：存在一些边，权值都是当前都小的，且只能从这里面选一条边加入MST，即，原本他们都能加入MST，但是加入一条以后剩余的都没法加入MST了。

对于所有的冲突边，选一条加入MST，然后其他边的权值都要+1.

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream> using namespace std;
const int maxn=2e5+;
struct Edge{
int from,to,w;
bool operator<(const Edge& rhs)const{
return w<rhs.w;
}
}edges[maxn];
int n,m;
int p[maxn];
int find(int x){
return p[x]==x?x:p[x]=find(p[x]);
} int main(){
scanf("%d%d",&n,&m);
for(int i=;i<=n;i++)p[i]=i;
for(int i=;i<=m;i++)
scanf("%d%d%d",&edges[i].from,&edges[i].to,&edges[i].w);
sort(edges+,edges++m);
int ans=;
for(int i=;i<=m;){
int j=i;
while(edges[j].w==edges[i].w){
j++;
}
j--;
int num=;
for(int k=i;k<=j;k++){
int x=find(edges[k].from);
int y=find(edges[k].to);
if(x!=y)
num++;
}
for(int k=i;k<=j;k++){
int x=find(edges[k].from);
int y=find(edges[k].to);
if(x!=y){
p[x]=y;
num--;
}
}
ans+=num;
i=j+;
}
printf("%d\n",ans);
return ;
}