板刷 Edu
Educational Codeforces Round 100
弱智题，但是我一眼上去不会。
一轮操作总共造成 \(9\) 点伤害，所以符合要求的一个必要条件是 \(9|sum\)，还要注意每个怪物每轮至少受到一点伤害，生命最小的不能被刮死，所以还要 \(min(a,b,c) \ge \dfrac{sum}{9}\)，两个合起来是充要的。
void solve() {
int a, b, c; cin >> a >> b >> c;
int mn = min({a, b, c}), sum = a + b + c;
if(sum % 9 == 0 && mn >= sum / 9) cout << "Yes\n";
else cout << "No\n";
}
注意到式子里有个 \(2\)，吸引人从 \(2\) 的次幂考虑。
发现可以对于每个 \(a_i\)，匹配小于等于它的最大 \(2\) 的幂，这样 \(\left\vert a_i - b_i\right\vert < \dfrac{a}{2}\)，所以 \(\sum_{i = 1}^{n} 2\left\vert a_i - b_i\right\vert < S\)，符合要求。
void solve() {
cin >> n;
rep(i, 1, n) {int x; cin >> x; cout << (1 << __lg(x)) << " \n"[i == n];}
}
小模拟，动态更新当前正在执行的操作，判断指令是否被忽略。注意到对于 \([t_i, t_{i + 1}]\) 这个区间，执行的操作要么完全包含这个区间，要么在这个区间中结束。所以对于每一个区间，机器人走过的区间是容易计算的。
假设当前在执行的指令开始时间、结束时间、起始位置、方向分别是 \(st,ed, from, d\)，那么对于 \(t \in [st,ed]\)，机器人位置为 \(from + (t - st) * d\)，代入 \(t_i, t_{i + 1}\) 计算，检查 \(x_i\) 是否在这个区间内即可。注意特判 \(t_{i + 1}\) 超过 \(ed\) 的情况。
int n;
pair<ll, ll> a[N], b[N];
void solve() {
cin >> n; rep(i, 1, n) cin >> a[i].fi >> a[i].se;
ll ed = 0, from, to = 0, d, st;
rep(i, 1, n) {
if(ed <= a[i].fi) {
from = to, to = a[i].se; ed = a[i].fi + abs(from - to), st = a[i].fi;
d = to - from > 0 ? 1 : -1;
}
b[i].fi = from + d * (a[i].fi - st);
if(i < n) b[i].se = a[i + 1].fi > ed ? to : from + d * (a[i + 1].fi - st);
else b[i].se = to;
if(b[i].fi > b[i].se) swap(b[i].fi, b[i].se);
}
int ans = 0;
rep(i, 1, n) if(b[i].fi <= a[i].se && a[i].se <= b[i].se) ans++;
cout << ans << "\n";
}
首先有直观的贪心，对于 \(x\) 个取最小值的组合，尽量用 \(b\) 里较小的和补集里较大的匹配，剩下 \(n - x\) 同理，这个可以交换证明，但很显然。
然后可以发现会有某些数必须放最小值，有些必须放最大值，这个可以双指针，但我用 set，STL 给我的自信。
int a[N], b[N], n, vis[2 * N], cnt;
void solve() {
cin >> n; rep(i, 1, n) cin >> b[i];
rep(i, 1, n) vis[b[i]] = 1;
int ans1 = n, ans2 = n;
set<int> s;
rep(i, 1, 2 * n) if(!vis[i]) s.insert(i);
rep(i, 1, n) {
if(s.upper_bound(b[i]) == s.end()) break;
ans1--; s.erase(s.upper_bound(b[i]));
}
s.clear();
rep(i, 1, 2 * n) if(!vis[i]) s.insert(i);
req(i, n, 1) {
if(s.lower_bound(b[i]) == s.begin()) break;
ans2--; s.erase(prev(s.lower_bound(b[i])));
}
rep(i, 1, n) vis[b[i]] = 0;
cout << n - ans1 - ans2 + 1 << "\n";
}
评价是没有 D 难，注意到 \(k\) 个特殊约束相当于把两个数捆绑在一起，判断矛盾使用带权并查集维护，权值越小表示这个数越靠后。打包好之后相当于进行了一个缩点，按照 \(a\) 的限制建图，最后跑拓扑排序即可。
三种无解的情况 ：
- 维护 \(k\) 个约束时出现矛盾，
- 建图时和已有约束矛盾，
- 拓扑排序时有环。
虽然写的很答辩，也调了很久，但很直观（个人而言）。
int n, k;
int a[N], in[N];
struct node {
int id, f, dep, siz; //dep 表示权值，dep越大，说明它在当前节点内应该越靠前
}b[N];
pii tmp[N];
int find(int x) {
if(b[x].f == x) return x;
int p = b[x].f;
b[x].f = find(b[x].f);
b[x].dep += b[p].dep;
return b[x].f;
}
bool mer(int x, int y) {
int xx = find(x), yy = find(y);
if(xx != yy) b[xx].f = yy, b[xx].dep = b[yy].siz, b[yy].siz += b[xx].siz;
xx = find(x), yy = find(y);
if(b[x].dep - b[y].dep != 1) return 0; //合并后权值差不为 1 说明出现矛盾，不满足相邻
return 1;
}
vector<int> ans, p[N], e[N];
void add(int u, int v) {e[u].emplace_back(v);}
void solve() {
cin >> n >> k;
rep(i, 1, n) b[i].f = i, b[i].dep = 0, b[i].id = i, b[i].siz = 1;
rep(i, 1, n) cin >> a[i];
rep(i, 1, k) {
int x, y; cin >> x >> y;
if(!mer(x, y)) {cout << "0\n"; return;}
}
rep(i, 1, n) {
if(!a[i]) continue;
if(find(a[i]) == find(i)) {
if(b[a[i]].dep <= b[i].dep) {cout << "0\n"; return;} // a[i] 已经排在 i 后面，说明无解
continue;
}
add(find(a[i]), find(i)), in[find(i)]++;
}
rep(i, 1, n) tmp[i].fi = b[i].dep, tmp[i].se = i;
sort(tmp + 1, tmp + n + 1, greater<pii>());
rep(i, 1, n) p[find(tmp[i].se)].push_back(tmp[i].se);
// 维护缩点后每个点内的排列顺序
queue<int> q;
rep(i, 1, n) {
if(!in[i] && find(i) == i) {
q.push(i);
}
}
while(q.size()) {
int x = q.front(); q.pop();
if(p[x].size()) ans.push_back(x);
for(int ed : e[x]) {
if(!--in[ed]) q.push(ed);
}
}
rep(i, 1, n) if(in[i]) {cout << "0\n"; return;} //成环无解
for(int i : ans) for(int j : p[i]) cout << j << " ";
}
3100 的神秘题，写不了一点，skip。