AtCoder Beginner Contest 370 Solution

本文主要是介绍AtCoder Beginner Contest 370 Solution，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

A

void solve() {int a, b;qr(a, b);if(a + b != 1) cout << "Invalid\n";else Yes(a);
}

B

模拟

void solve() {qr(n);int x = 1;FOR(i, n) FOR(j, i) qr(a[i][j]);FOR(i, n) x = x >= i ? a[x][i]: a[i][x];pr2(x);
}

C

首先先考虑能变小的位置, 此时选择更前面的位置对字典序的改变更优. 反之, 先选后面的位置更优.

void solve() {string s, t;qr(s, t);n = SZ(s);VT<int> v[2];m = 0;rep(i, 0, n - 1) if(s[i] != t[i])v[s[i] < t[i]].pb(i);pr2(SZ(v[0]) + SZ(v[1]));reverse(v[1]);rep(i, 0, 1) {for(int j: v[i]) s[j] = t[j], pr2(s);}
}

D

维护 $n + m$ 个set,用内置函数查找. 需要注意的时,先删除 prev(it), 再删除 it. 否则迭代器可能异常.

void solve() {qr(n, m, q);VT r(n + 1, set<int>()), c(m + 1, set<int>());FOR(i, n) FOR(j, m) r[i].insert(j), c[j].insert(i);int x, y;auto del = [&](int x, int y) {r[x].erase(y); c[y].erase(x);};while(q--) {qr(x, y);if(r[x].contains(y)) {del(x, y);continue;}if(SZ(c[y])) {auto jt = c[y].upper_bound(x);if(jt != c[y].begin()) del(*prev(jt), y);if(jt != c[y].end()) del(*jt, y);}if(SZ(r[x])) {auto jt = r[x].upper_bound(y);if(jt != r[x].begin()) del(x, *prev(jt));if(jt != r[x].end()) del(x, *jt);}}int ans = 0;FOR(i, n) ans += SZ(r[i]);pr2(ans);
}

E

简单容斥+dp, 每次把以 $i$ 末尾段中和为 $k$ 的段去掉即可.

const int N = 2e5 + 10, inf = 0x3f3f3f3f;
const ll INF = 4E18;
int n;
ll s[N], m, f[N];void solve() {qr(n, m);FOR(i, n) qr(s[i]), s[i] += s[i - 1];ll sum = f[0] = 1;map<ll, int> g;g[0] = 1;FOR(i, n) {f[i] = sum;dl(f[i], g[s[i] - m]);ad(g[s[i]], f[i]);ad(sum, f[i]);}pr2(f[n]);
}

F

看到最小值最大,显然二分 $x$ ,判断是否可以每段都 $\ge x$ .
然后环的处理就是断环为链(复制一次在后面).
然后每个位置求一下最大的前驱,满足对应区间和 $\ge x$ .
然后就是倍增选择跳 $m$ 次前驱, 如果跳完坐标差 $\le n$ , 则合法.

考虑第二个输出, 不被砍,说明不能以它结尾, 所以统计不合法的 $e n d p o in t$ 数量即可. 复杂度 $O(n\log m \log (\sum a[i] / n))$ .

当然把倍增去掉,改成 $df s$ 即可省去一个 $\log m$ .

const int N = 4e5 + 10, inf = 0x3f3f3f3f;
const ll INF = 4E18;
int n, m, a[N], sum;int p[N], f[N][20], out;
bool check(int x, int o = 1) {int st = 1, s = 0;int lg = __lg(m);out = 0;FOR(i, 2 * n) {s += a[i];while(st < i && s - a[st] >= x) s -= a[st++];p[i] = st - 1;f[i][0] = p[i];rep(j, 1, lg) f[i][j] = f[f[i][j - 1]][j - 1];if(i > n) {int j = i;rep(k, 0, lg) if(m >> k & 1) j = f[j][k];if(i - j <= n) {if(o) return 1;}else out++;}}return 0;
}void solve() {qr(n, m);FOR(i, n) qr(a[i]), a[i + n] = a[i], sum += a[i];int l = *min_element(a + 1, a + n + 1), r = sum / m, mid;while(l < r) {mid = (l + r + 1) >> 1;if(check(mid)) l = mid;else r = mid - 1;}check(l, 0);pr1(l, out);
}