Contest Info
| Solved | A | B | C | D | E | F |
|---|---|---|---|---|---|---|
| 4/6 | O | Ø | Ø | Ø | ! | Ø |
- O 在比赛中通过
- Ø 赛后通过
- ! 尝试了但是失败了
- - 没有尝试
Solutions
D.Harmonious Graph
题意：
给你一个有$n$个节点$(1-n)$、$m$条边的无向图，让你通过加边的方式使得这个图满足
对于任意的$ (l,m,r)(1leq l < m < r leq r)$如果存在一条$l$到$r$的路径，则存在$l$到$m$的路径（即有$l$到$(l+1),(l+2), cdots , (r-1)$的路径）
求需要加多少条边
思路：
这题当时看的时候第一想法就是并查集，但是也只是知道还没有做出来。
后来看别的代码才发现的确用的是并查集，那个方法就觉得很到位，完全是按照题目的意思来做的。为什么要这么说？假如我们把题目中所有的集合全部找出来，每个集合中的元素相互间就有路径，只要我们确保这个集合中标号最小的$l$和最大的$r$满足上述关系，那么集合中其他节点也满足这个关系，这个可以自己去想想。
为了方便起见，我们合并的时候就将标号大的作为父节点，这样这个集合最大的标号节点就是这个集合的根。最后这个集合中所有节点的根应该都是$r$，如果不是就进行合并操作，$ans++$
#include<cstdio> #include<iostream> #include<cstring> #include<algorithm> typedef long long ll; using namespace std; int n, m, ans; int f[200005]; int find(int x){ if (f[x]!=x) f[x]=find(f[x]); return f[x]; } //将节点标号数字大的作为父节点 void merge(int x,int y){ x = find(x), y = find(y); if(x<y) f[x] = y; else f[y] = x; } int main(){ scanf("%d%d", &n, &m); for(int i = 1; i <= n; i++) f[i] = i; for(int i = 1; i <=m; i++){ int x, y; scanf("%d%d", &x, &y); if (find(x)!=find(y)) merge(x,y); } //下面这里就写的非常好, 是这道题的灵魂, 完全根据题目意思来 for(int i = 1; i <= n; i = find(i)+1) for(int j = i+1; j <= find(i); j++) if (find(i)!=find(j)) merge(i,j), ans++; cout << ans; }
E.Antenna Coverage
两个WA的贪心代码
#include <cstdio> #include <cstring> #include <algorithm> using namespace std; const int maxn = 10005; int n, m; int x[maxn], s[maxn]; int main(){ scanf("%d%d", &n, &m); int ds, ans, index = 0; for(int i = 1; i <= n; i++){ scanf("%d%d", x+i, s+i); ds = (x[i]-s[i]-index-1)>0 ? (x[i]-s[i]-index-1) :0; //(x[i]-s[i]-1)-(index+1)+1 ans += ds; index = max(index, x[i]+s[i]+ds); } if(index<m) ans += m-index; printf("%d", ans); }
#include <cstdio> #include <cstring> #include <algorithm> using namespace std; const int maxn = 10005; int n, m; int x[maxn], s[maxn]; struct ant{ int x, s; bool operator <(const ant&b)const{ return x < b.x-b.s; } }ant[maxn]; int main(){ scanf("%d%d", &n, &m); int ds, ans, index = 0; for(int i = 1; i <= n; i++) scanf("%d%d", &ant[i].x, &ant[i].s); sort(ant+1, ant+1+n); for(int i = 1; i <= n; i++){ ds = (ant[i].x-ant[i].s-index-1)>0 ? (ant[i].x-ant[i].s-index-1) :0; //(x[i]-s[i]-1)-(index+1)+1 ans += ds; index = max(index, ant[i].x+ant[i].s+ds); } if(index<m) ans += m-index; printf("%d", ans); }
F.Cheap Robot
算是我挖的一个坑吧，有点难补，看了好久~
实在是啃不动了，需要去看些图论的知识，就像LCA，树链剖分，缩点，强连通分量这些，因为这个题需要这块的知识，刚好之前又没有接触过，但是比赛里也碰到了很多。
终于补完了，在这里>_<