Codeforces Round #535 (Div. 3)

时间:2021-09-14 10:00:38

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 ;
}

Codeforces Round #535 (Div. 3)的更多相关文章

  1. Codeforces Round &num;535 &lpar;Div&period; 3&rpar; 题解

    Codeforces Round #535 (Div. 3) 题目总链接:https://codeforces.com/contest/1108 太懒了啊~好久之前的我现在才更新,赶紧补上吧,不能漏掉 ...

  2. Codeforces Round &num;535 &lpar;Div&period; 3&rpar; E2&period; Array and Segments &lpar;Hard version&rpar; 【区间更新 线段树】

    传送门:http://codeforces.com/contest/1108/problem/E2 E2. Array and Segments (Hard version) time limit p ...

  3. Codeforces Round &num;535 &lpar;Div&period; 3&rpar; &lbrack;codeforces div3 难度测评&rsqb;

    hhhh感觉我真的太久没有接触过OI了 大约是前天听到JK他们约着一起刷codeforces,假期里觉得有些颓废的我忽然也心血来潮来看看题目 今天看codeforces才知道居然有div3了,感觉应该 ...

  4. C&period; Nice Garland Codeforces Round &num;535 &lpar;Div&period; 3&rpar; 思维题

    C. Nice Garland time limit per test 1 second memory limit per test 256 megabytes input standard inpu ...

  5. D&period; Diverse Garland Codeforces Round &num;535 &lpar;Div&period; 3&rpar; 暴力枚举&plus;贪心

    D. Diverse Garland time limit per test 1 second memory limit per test 256 megabytes input standard i ...

  6. Codeforces Round &num;535 &lpar;Div&period; 3&rpar; 解题报告

    CF1108A. Two distinct points 做法:模拟 如果两者左端点重合就第二条的左端点++就好,然后输出左端点 #include <bits/stdc++.h> usin ...

  7. Codeforces Round &num;535 &lpar;Div&period; 3&rpar; 1108C - Nice Garland

    #include <bits/stdc++.h> using namespace std; int main() { #ifdef _DEBUG freopen("input.t ...

  8. Codeforces Round &num;535&lpar;div 3&rpar; 简要题解

    Problem A. Two distinct points [题解] 显然 , 当l1不等于r2时 , (l1 , r2)是一组解 否则 , (l1 , l2)是一组合法的解 时间复杂度 : O(1 ...

  9. Codeforces Round &num;535 &lpar;Div&period; 3&rpar; F

    F. MST Unification 题目传送门 题意: 给你n个顶点,m条边:保证没有重边,其中存在多个MST(最小生成树), 你可以修改一些边的权值,让其中有且仅有一个最小生成树,求最少操作的边数 ...

随机推荐

  1. 牛X的CSS3

    See the Pen Dot Wave by Rich Howell (@roborich) on CodePen

  2. DataGridView中的单元格提示错误信息

    http://*.com/questions/7713988/winforms-problems-validating-a-cell-in-a-datagridview

  3. git上解决代码冲突

    1.切换到master: git co master 2.拉最新代码:git pull origin master 3.删掉多余符号 4.切换到提交的分支:git br Txxxx 5.合并:git  ...

  4. 多核CPU利用测试

      一直在想程序上是否特意让线程在指定的CPU上去运行,这样可以提高运行效率,所以特地写个代码让CPU使用率画正弦曲线的实验,我使用的是AMD X4 641的CPU,为四核四线程的片子. 代码如下 # ...

  5. 命令查询分离原则Command-query separation principle

    在UML和模式应用一书中,发送给Die的roll消息之后跟随着第二个消息getFaceValue用于提取其新的faceValue,特别是:roll()方法是void的,没有返回值,例如: public ...

  6. mmap函数实现

    转自:https://www.cnblogs.com/huxiao-tee/p/4660352.htmlmmap是一种内存映射文件的方法,即将一个文件或者其它对象映射到进程的地址空间,实现文件磁盘地址 ...

  7. 【转载】FPGA算法映射要点

    近期一直在学习利用FPGA完成算法的定点运算,转载些相关的博客方面回顾查找.本博文原文链接为:https://blog.csdn.net/u013989284/article/details/7899 ...

  8. tomcat错误The superclass &quot&semi;javax&period;servlet&period;http&period;HttpServlet&quot&semi; was not found on the Java Build Path

    在更换tomcat版本后,原来的项目文件中jsp会出现错误The superclass "javax.servlet.http.HttpServlet" was not found ...

  9. 转:【专题三】自定义Web服务器

    前言: 经过前面的专题中对网络层协议和HTTP协议的简单介绍相信大家对网络中的协议有了大致的了解的, 本专题将针对HTTP协议定义一个Web服务器,我们平常浏览网页通过在浏览器中输入一个网址就可以看到 ...

  10. 关于dict的formkeys方法注意

    使用容器中的元素生成k, v为统一值, 指向同一个内存地址 默认值指向同一个内存, 修改就全部修改 strvar = 'abcd' listvar = [] dictvar = {} dictvar ...