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)的更多相关文章
-
Codeforces Round #535 (Div. 3) 题解
Codeforces Round #535 (Div. 3) 题目总链接:https://codeforces.com/contest/1108 太懒了啊~好久之前的我现在才更新,赶紧补上吧,不能漏掉 ...
-
Codeforces Round #535 (Div. 3) E2. Array and Segments (Hard version) 【区间更新 线段树】
传送门:http://codeforces.com/contest/1108/problem/E2 E2. Array and Segments (Hard version) time limit p ...
-
Codeforces Round #535 (Div. 3) [codeforces div3 难度测评]
hhhh感觉我真的太久没有接触过OI了 大约是前天听到JK他们约着一起刷codeforces,假期里觉得有些颓废的我忽然也心血来潮来看看题目 今天看codeforces才知道居然有div3了,感觉应该 ...
-
C. Nice Garland Codeforces Round #535 (Div. 3) 思维题
C. Nice Garland time limit per test 1 second memory limit per test 256 megabytes input standard inpu ...
-
D. Diverse Garland Codeforces Round #535 (Div. 3) 暴力枚举+贪心
D. Diverse Garland time limit per test 1 second memory limit per test 256 megabytes input standard i ...
-
Codeforces Round #535 (Div. 3) 解题报告
CF1108A. Two distinct points 做法:模拟 如果两者左端点重合就第二条的左端点++就好,然后输出左端点 #include <bits/stdc++.h> usin ...
-
Codeforces Round #535 (Div. 3) 1108C - Nice Garland
#include <bits/stdc++.h> using namespace std; int main() { #ifdef _DEBUG freopen("input.t ...
-
Codeforces Round #535(div 3) 简要题解
Problem A. Two distinct points [题解] 显然 , 当l1不等于r2时 , (l1 , r2)是一组解 否则 , (l1 , l2)是一组合法的解 时间复杂度 : O(1 ...
-
Codeforces Round #535 (Div. 3) F
F. MST Unification 题目传送门 题意: 给你n个顶点,m条边:保证没有重边,其中存在多个MST(最小生成树), 你可以修改一些边的权值,让其中有且仅有一个最小生成树,求最少操作的边数 ...
随机推荐
-
牛X的CSS3
See the Pen Dot Wave by Rich Howell (@roborich) on CodePen
-
DataGridView中的单元格提示错误信息
http://*.com/questions/7713988/winforms-problems-validating-a-cell-in-a-datagridview
-
git上解决代码冲突
1.切换到master: git co master 2.拉最新代码:git pull origin master 3.删掉多余符号 4.切换到提交的分支:git br Txxxx 5.合并:git ...
-
多核CPU利用测试
一直在想程序上是否特意让线程在指定的CPU上去运行,这样可以提高运行效率,所以特地写个代码让CPU使用率画正弦曲线的实验,我使用的是AMD X4 641的CPU,为四核四线程的片子. 代码如下 # ...
-
命令查询分离原则Command-query separation principle
在UML和模式应用一书中,发送给Die的roll消息之后跟随着第二个消息getFaceValue用于提取其新的faceValue,特别是:roll()方法是void的,没有返回值,例如: public ...
-
mmap函数实现
转自:https://www.cnblogs.com/huxiao-tee/p/4660352.htmlmmap是一种内存映射文件的方法,即将一个文件或者其它对象映射到进程的地址空间,实现文件磁盘地址 ...
-
【转载】FPGA算法映射要点
近期一直在学习利用FPGA完成算法的定点运算,转载些相关的博客方面回顾查找.本博文原文链接为:https://blog.csdn.net/u013989284/article/details/7899 ...
-
tomcat错误The superclass ";javax.servlet.http.HttpServlet"; was not found on the Java Build Path
在更换tomcat版本后,原来的项目文件中jsp会出现错误The superclass "javax.servlet.http.HttpServlet" was not found ...
-
转:【专题三】自定义Web服务器
前言: 经过前面的专题中对网络层协议和HTTP协议的简单介绍相信大家对网络中的协议有了大致的了解的, 本专题将针对HTTP协议定义一个Web服务器,我们平常浏览网页通过在浏览器中输入一个网址就可以看到 ...
-
关于dict的formkeys方法注意
使用容器中的元素生成k, v为统一值, 指向同一个内存地址 默认值指向同一个内存, 修改就全部修改 strvar = 'abcd' listvar = [] dictvar = {} dictvar ...