前言
写题解纯粹是对 cf 的爱好。
以后就按难度倒序来写题解吧。
E. Monsters
题意：
给定一张无向图，每个点上有一只体力为 ai 的怪兽，0<=ai<=n。
要选择一个点作为起点，然后不停的打怪兽，当怪兽的体力 ai 小于 已经打败的怪兽的数量的时候，这只怪兽就可以被打败。如果这只怪兽被打败，那么这只怪兽所在的点是可以访问的。
问最终能否打败所有的怪兽。
思路：
乍一看很容易想到的做法就是从点权为 0 的点开始 dfs，但是如果点权为 0 的点数量过多的话，很显然这个复杂度就变成 n2了。
一步步的来，先考虑这个问题：
对于已经打败过的怪兽，他们一定处于一个联通块，联通块所连接的，但是不属于这个联通块的点，（也就是联通块相邻的外面的点），怎样找到这个集合内点权最小的点呢？
答案是 priorityqueue 或者 set。
假设联通块之外的点权最小的点是 y，y 也是有自己的出边的，那么还要将 y 所连接的点，加入当前的集合。显然这里就要用上启发式合并了。
解决了合并点的问题，现在考虑 0 的数量太多怎么处理：
这个问题的答案其实与上一步有所联系。
上一步中提到的 y，如果他已经在另一个联通块中了，那么很显然这两个联通块是可以合并的。
所以答案是并查集。
这题就这样做完了。
int a[N];
struct node {
int y, val;
bool operator < (const node &k) const {
return val > k.val;
}
};
priority_queue<node> q[N];
int fa[N], siz[N];
int getf(int x)
{
if (x == fa[x]) return x;
return fa[x] = getf(fa[x]);
}
void solve()
{
int n, m;
cin >> n >> m;
for (int i = 1; i <= n; i++) {
cin >> a[i];
fa[i] = i;
siz[i] = 1;
}
for (int i = 1; i <= m; i++) {
int x, y;
cin >> x >> y;
q[x].push({y, a[y]});
q[y].push({x, a[x]});
}
for (int i = 1; i <= n; i++) {
if (a[i] == 0) {
int f = getf(i);
// 子节点的y的祖先的外部集合 与 当前的外部集合 合并
// 内部集合的大小 并查集维护
while(q[f].size() && q[f].top().val <= siz[f]) {
int y = getf(q[f].top().y);
q[f].pop();
if (y == f) continue;
if (q[y].size() > q[f].size()) {
swap(f, y);
}
siz[f] += siz[y];
fa[y] = f;
while(!q[y].empty()) {
q[f].push(q[y].top());
q[y].pop();
}
}
}
}
bool ok = 0;
for (int i = 1; i <= n; i++) {
if (siz[i] == n) {
ok = 1;
}
while(!q[i].empty()) {
q[i].pop();
}
}
if (ok) cout << "YES\n";
else cout << "NO\n";
}
D. Climbing the Tree
感觉这题 easy，不配 1700 的难度。
题意：
有一些蜗牛要爬树，现在有 q 次询问。
每次询问又两种情况：
1、给定蜗牛白天能爬的高度，晚上下滑的高度，爬上树所用的天数。
2、给定蜗牛白天能爬的高度，晚上下滑的高度
对于情况 1，要回答真或者假。
对于情况 2，要回答爬上树需要几天，或者是不知道。
做法：
很显然如果给了情况 1，那么树的高度范围就可以确定了。每次都可以缩小这个范围。如果给定的情况算出来的范围，与当前的范围交集是空，显然回答假。反之回答真。
对于情况2：
可以二分天数，最快几天爬上树，最慢几天爬上树。因为树的高度是一个范围，所以这里存在最快几天和最慢几天。
如果最快天数和最慢天数不一致，就回答不知道。否则回答出这个天数。
int a[N];
int L, R;
bool check(int mid, int a, int b)
{
int tl = a + (mid - 2) * (a - b) + 1;
if (mid == 1) tl = 1;
int tr = a + (mid - 1) * (a - b);
// 拿到区间，只要区间的右端点比当前的左端点 大
return L <= tr;
}
bool check1(int mid, int a, int b)
{
int tl = a + (mid - 2) * (a - b) + 1;
if (mid == 1) tl = 1;
int tr = a + (mid - 1) * (a - b);
return tl <= R;
}
bool checkok(int mid, int a, int b)
{
int tl = a + (mid - 2) * (a - b) + 1;
if (mid == 1) tl = 1;
int tr = a + (mid - 1) * (a - b);
int l = max(tl, L);
int r = min(R, tr);
// cout << "\n l = " << l << " " << r << "\n";
return l <= r;
}
void solve()
{
long long q;
cin >> q;
L = 1, R = 1e18;
while (q--) {
long long op;
cin >> op;
if (op == 1) {
long long a, b, n;
cin >> a >> b >> n;
int tL;
if (n == 1) tL = L;
else tL = max(L, (__int128) a + (n - 2) * (a - b) + 1);
int tR = min(R, (__int128) a + (n - 1) * (a - b));
if (tL > tR) {
cout << "0 ";
}
else {
cout << "1 ";
L = tL;
R = tR;
}
} else {
long long a, b;
cin >> a >> b;
int l = 1, r = 1e18;
while (l < r) {
int mid = (l + r) >> 1;
if (check(mid, a, b)) r = mid;
else l = mid + 1;
}
int temp = l;
l = 1, r = 1e18;
while(l < r) {
int mid = (l + r + 1) >> 1;
if (check1(mid, a, b)) l = mid;
else r = mid - 1;
}
if (temp != l || !checkok(l, a, b)) {
cout << "-1 ";
} else {
cout << (long long) l << " ";
}
}
}
cout << "\n";
}
C. Make It Permutation
题意：
给定一组数，你可以删除一个数，代价是c；也可以添加一个数，代价是 b。
问变成一个排列的最小代价。
做法：
枚举删除掉几个数就好了。为什么不枚举添加的数呢，因为数的范围比较大，这样枚举会喜提TLE。
int a[N];
void solve()
{
int n, c, d;
cin >> n >> c >> d;
for (int i = 1; i <= n; i++) {
cin >> a[i];
}
sort(a + 1, a + 1 + n);
int cnt = unique(a + 1, a + 1 + n) - a - 1;
int ans = 1e18;
for (int i = 1; i <= cnt; i++) {
ans = min(ans, (a[i] - i) * d + (cnt - i) * c);
// cout << (a[i] - i) * d + (cnt - i) * c << " " << a[i] - i << " " << cnt - i << "\n";
}
ans = min(ans, cnt * c + d);
// cout << "\n";
cout << ans + (n - cnt) * c << "\n";
}
