2021 Spring Discussion 1
春季学期第一次讨论班，王博士讲了许多 AtCoder 上的思维题。
Slides: https://drive.google.com/file/d/10EVj_812TJNb4OlgBYxoEG-hdldre9X-/view?usp=sharing
Task 1: Pay to win
Source: AtCoder Grand Contest 044, Problem A
Link: https://atcoder.jp/contests/agc044/tasks/agc044_a
Code:
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll a, b, c, d, n;
map<ll, ll> f;
ll dfs(ll num) {
if (f.find(num) != f.end()) {
return f[num];
}
ll res = 1e18;
if (num < res / d) res = num * d;
res = min(res, (num % 2) * d + dfs(num / 2) + a);
res = min(res, (2 - num % 2) * d + dfs((num + 1) / 2) + a);
res = min(res, (num % 3) * d + dfs(num / 3) + b);
res = min(res, (3 - num % 3) * d + dfs((num + 2) / 3) + b);
res = min(res, (num % 5) * d + dfs(num / 5) + c);
res = min(res, (5 - num % 5) * d + dfs((num + 4) / 5) + c);
return f[num] = res;
}
int main() {
int T;
cin >> T;
while(T--) {
cin >> n >> a >> b >> c >> d;
f[0] = 0, f[1] = d;
cout << dfs(n) << endl;
f.clear();
}
return 0;
}
这题还是比较可做的，要注意一下 14 行那个特判。虽然样例足够强，但是太大了，还是很难直接查到这个错的。
Task 2 Jumper
Source: AtCoder Grand Contest 050, Problem A
Link: https://atcoder.jp/contests/agc050/tasks/agc050_a
Code:
#include <bits/stdc++.h>
using namespace std;
int main() {
int n;
cin >> n;
for (int i = 1; i <= n; ++i) {
cout << (2 * i) % n + 1 << " " << (2 * i + 1) % n + 1 << endl;
}
return 0;
}
这题也挺可做的。由 (N=1000) 和 (10) 条边数量级也能想到 (log) 关系，不过到二叉树还是稍有困难。
Task 3: Median Sum
Source: AtCoder Grand Contest 020, Problem C
Link: https://atcoder.jp/contests/agc020/tasks/agc020_c
Code:
#include <bits/stdc++.h>
using namespace std;
const int N = 4000005;
bitset<N> bst;
int a[N], cnt;
int main() {
int n, x;
cin >> n;
bst[0] = 1;
for (int i = 0; i != n; ++i) {
cin >> x;
bst |= (bst << x);
}
for (int i = 1; i != N; ++i) {
if (bst[i]) {
a[++cnt] = i;
}
}
cout << a[(cnt + 1) / 2] << endl;
return 0;
}
其实我不太会用 std::bitset 。
Task 4: Tree Edges XOR
Source: AtCoder Grand Contest 052, Problem B
Link: https://atcoder.jp/contests/agc052/tasks/agc052_b
Code:
#include <bits/stdc++.h>
using namespace std;
template<typename T>
inline void read(T &x) {
char c = getchar(); x = 0;
while (c < '0' || '9' < c) c = getchar();
while ('0' <= c && c <= '9') {
x = (x << 1) + (x << 3) + c - 48;
c = getchar();
}
}
struct Edge {
int v, w1, w2;
};
const int N = 131072;
vector<Edge> gra[N];
int n, ori[N], goa[N], fix1, fix2;
void dfs(int u, int pa) {
ori[1] ^= ori[u], goa[1] ^= goa[u];
for (auto nex: gra[u]) {
if (nex.v == pa) continue;
ori[nex.v] = ori[u] ^ nex.w1;
goa[nex.v] = goa[u] ^ nex.w2;
dfs(nex.v, u);
}
}
int main() {
read(n);
for (int i = 1; i != n; ++i) {
int u, v, w1, w2;
read(u), read(v), read(w1), read(w2);
gra[u].push_back(Edge{v, w1, w2});
gra[v].push_back(Edge{u, w1, w2});
}
dfs(1, 0);
dfs(1, 0);
sort(ori + 1, ori + n + 1);
sort(goa + 1, goa + n + 1);
for (int i = 1; i <= n; ++i) {
if (ori[i] != goa[i]) {
return puts("NO"), 0;
}
}
return puts("YES"), 0;
}
这题实在巧妙。用嘴做的时候就很困难，用手做问题就更多。这里我多说一点 Slides 上没写的实现细节。
Slides 上提到，需要附加条件： (igoplus_{i=1}^n f(i) = 0 ~~~~~~~~ (*))
具体地，我设置根节点权为 (0) ，做一遍 dfs 得到其他点权。为了保证 ((*)) 式成立，可以考虑将 (f(1)) 赋值为 (igoplus_{i=2}^n f(i)) ，重做一次 dfs。
这样做似乎非常地丑，也似乎有很好的做法，但是我没想到。
Task 5: Rotation Sort
Source: AtCode Grand Contest 032, Problem D
Link: https://atcoder.jp/contests/agc032/tasks/agc032_d
Code:
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 5005;
int n, arr[N];
ll a, b, suf, f[N];
int main() {
scanf("%d%lld%lld", &n, &a, &b);
for (int i = 1; i <= n; ++i) {
scanf("%d", &arr[i]);
}
arr[++n] = 1e9, f[0] = 0;
for(int i = 1; i <= n; i++) {
f[i] = 1e16, suf = 0;
for(int j = i - 1, mos = -1; j >= 0; j--) {
if(arr[j] < arr[i] && mos < arr[j]) {
f[i] = min(f[i], f[j] + suf);
}
if (arr[i] > arr[j]) {
mos = max(mos, arr[j]);
suf += b;
}
else suf += a;
}
}
cout << f[n] << endl;
return 0;
}
这里顺带提一下动态规划的状态转移方程：
我们记 (f_i) 表示固定 (a_i) 为所选定上升子序列中的一个元素，改变前 (i) 个元素的位置，维护其相对升序所需的最小花费。
那么显然有：
其中，
计算 (c_i(k)) 时，我们对于每个 (i) 维护其后缀和，这样就可以做到 (O(n^2)) 的复杂度。
Task 6: Increasing Numbers
Source: AtCoder Grand Conteset 011, Problem E
Link: https://atcoder.jp/contests/agc011/tasks/agc011_e
Code:
#include <bits/stdc++.h>
using namespace std;
const int N = 524288;
int len = 0;
short a[N];
int main() {
char c = getchar();
while ('0' <= c && c <= '9') {
a[len++] = (c - 48) * 9;
c = getchar();
}
reverse(a, a + len);
for (int i = 0; i <= len; ++i) {
a[i + 1] += a[i] / 10;
a[i] %= 10;
}
int k = 0, sum = 0;
for (int i = 0; i <= len; sum += a[i++]);
while (true) {
a[0] += 9, sum += 9, ++k;
for (int i = 0; a[i] >= 10 && i <= len; ++i) {
sum -= a[i] + a[i + 1];
a[i] -= 10, ++a[i + 1];
sum += a[i] + a[i + 1];
}
if (sum <= 9 * k)
return printf("%d
", k), 0;
}
return 0;
}
我的常数实在太大了，再带上 STL 的 Buff 更大得不行， AtCoder 的测评姬跑得上气不接下气（
这题是真的很厉害，一些 basic ideas 组装起来，就变得神乎其神了。
Task 7: BBQ Hard
Source: AtCoder Grand Contest 001, Problem E
Link: https://atcoder.jp/contests/agc001/tasks/agc001_e
Code:
#include <bits/stdc++.h>
using namespace std;
template<typename T>
inline void read(T &x) {
char c = getchar(); x = 0;
while (c < '0' || '9' < c) c = getchar();
while ('0' <= c && c <= '9') {
x = (x << 1) + (x << 3) + c - 48;
c = getchar();
}
}
typedef long long ll;
const ll P = 1e9 + 7;
const int N = 262144, H = 2005, F = 4010;
int n, a[N], b[N];
ll fac[N], f[F][F];
ll quick_pow(ll x, ll n) {
ll ret = 1;
while (n) {
if (n & 1) (ret *= x) %= P;
(x *= x) %= P, n >>= 1;
}
return ret;
}
#define inv(x) quick_pow(x, P - 2)
inline ll cob(int n, int m) {
ll ret = 1;
(ret *= fac[n]) %= P;
(ret *= inv(fac[m])) %= P;
(ret *= inv(fac[n - m])) %= P;
return ret;
}
int main() {
read(n);
for (int i = 1; i <= n; ++i) {
read(a[i]), read(b[i]);
f[H - a[i]][H - b[i]]++;
}
for (int i = 1; i != F; ++i) {
for (int j = 1; j != F; ++j) {
(f[i][j] += f[i - 1][j]) %= P;
(f[i][j] += f[i][j - 1]) %= P;
}
}
fac[0] = 1;
for (int i = 1; i != (F << 1); ++i) {
fac[i] = (fac[i - 1] * i) % P;
}
ll ans = 0;
for (int i = 1; i <= n; ++i) {
(ans += f[a[i] + H][b[i] + H]) %= P;
(ans += P - cob(2 * (a[i] + b[i]), 2 * a[i])) %= P;
}
printf("%lld
", (ans * inv(2)) % P);
return 0;
}
这题的设计实在天才，刷新了我对组合数求和的认知。
Task 8: Candy Piles
Source: AtCoder Grand Contest 002, Problem E
Link: https://atcoder.jp/contests/agc002/tasks/agc002_e
Code:
#include <bits/stdc++.h>
using namespace std;
template<typename T>
inline void read(T & x) {
char c = getchar(); x = 0;
while (c < '0' || '9' < c) c = getchar();
while ('0' <= c && c <= '9') {
x = (x << 1) + (x << 3) + c - 48;
c = getchar();
}
}
const int N = 131072;
int n, a[N];
int main() {
read(n);
for (int i = 1; i <= n; read(a[i++]));
sort(a + 1, a + n + 1, greater<int>());
int x = 1;
while (a[x + 1] >= x + 1) ++x;
int x_len = upper_bound(a + 1, a + n + 1, x, greater<int>()) - a - 1 - x,
y_len = a[x] - x;
if ((x_len & 1) || (y_len & 1)) puts("First");
else puts("Second");
return 0;
}
本题具有很强的观赏性。出题人炫技一样变出来一些博弈论、组合数学的魔术。我也不是没看过魔术，但还是吓傻了。
Task 9: Two Permutation
Source: AtCodre Grand Contest 038, Problem F
Link: https://atcoder.jp/contests/agc038/tasks/agc038_f
Code:
#include <bits/stdc++.h>
using namespace std;
template<const int N, const int M>
class Graph {
private:
int beg[N], nex[M], tar[M], cap[M], len;
int lev[N], ite[N], goa;
queue<int> que;
inline void add_edge(int a, int b, int c) {
++len, tar[len] = b, cap[len] = c;
nex[len] = beg[a], beg[a] = len;
}
void bfs(int s) {
memset(lev, -1, sizeof(lev));
lev[s] = 0, que.push(s);
while (!que.empty()) {
int cur = que.front(); que.pop();
for (int i = beg[cur]; i; i = nex[i]) {
if (cap[i] > 0 && lev[tar[i]] == -1) {
lev[tar[i]] = lev[cur] + 1;
que.push(tar[i]);
}
}
}
}
int dfs(int cur, int flo) {
if (cur == goa) return flo;
for (int &i = ite[cur]; i; i = nex[i]) {
if (cap[i] > 0 && lev[cur] < lev[tar[i]]) {
int res = dfs(tar[i], min(flo, cap[i]));
if (res) {
cap[i] -= res;
cap[i ^ 1] += res;
return res;
}
}
}
return 0;
}
public:
Graph() {
memset(beg, 0, sizeof(beg));
memset(nex, 0, sizeof(nex));
len = 1;
}
inline void add_pipe(int a, int b) {
add_edge(a, b, 1);
add_edge(b, a, 0);
}
int dinic(int s, int t) {
int res, ans = 0;
const int INF = 0x7f7f7f7f;
goa = t;
while (true) {
bfs(s);
if (lev[t] == -1) return ans;
memcpy(ite, beg, sizeof(beg));
while ((res = dfs(s, INF)) > 0) {
ans += res;
}
}
}
};
template<typename T>
inline void read(T &x) {
char c = getchar(); x = 0;
while (c < '0' || '9' < c) c = getchar();
while ('0' <= c && c <= '9') {
x = (x << 1) + (x << 3) + c - 48;
c = getchar();
}
}
const int N = 131072;
Graph<N << 1, N << 2> G;
int p[N], q[N], x[N], y[N];
bool vis[N];
int n, cnt = 1;
void find_circle(int a[], int b[]) {
memset(vis, 0, sizeof(vis));
for (int i = 0; i != n; ++i) {
if (vis[i]) continue;
int x = a[i];
do {
vis[x] = true;
b[x] = cnt;
x = a[x];
} while (x != a[i]);
cnt++;
}
}
int main() {
read(n);
for (int i = 0; i != n; read(p[i++]));
for (int i = 0; i != n; read(q[i++]));
find_circle(p, x);
find_circle(q, y);
int ans = n, s = cnt + 1, t = cnt + 2;
for (int i = 0; i != n; ++i) {
if (p[i] == q[i]) {
if (p[i] == i) {
--ans;
} else {
G.add_pipe(x[i], y[i]);
G.add_pipe(y[i], x[i]);
}
} else {
if (p[i] == i) G.add_pipe(y[i], t);
else if (q[i] == i) G.add_pipe(s, x[i]);
else G.add_pipe(y[i], x[i]);
}
}
cout << ans - G.dinic(s, t) << endl;
return 0;
}
按照那个 众所周知的 技巧，我们把给出的两个排列拆成许多环。为了方便说话，我们记 (P_i) 属于的环名字叫 (x(i)) ，(Q_i) 属于的环名字叫 (y(i)) 。
为了保证我们通过题设的方法生成的序列仍然是排列，容易发现，对于同一个环上的所有元素 (P_i) ，要么有 (A_i = P_i) 恒成立，要么有 (A_i = i) 恒成立。换言之，每个环都只可能保持原样或拆成许多自环。
那么，考虑每个 (x(i),y(i)) 是否要拆开，我们建立一个最小割模型：
考虑将要拆的 (x(i)) 与 (S) 联通，要拆的 (y(i)) 与 (T) 联通，分情况讨论：
(1^circ~~P_i = Q_i = i)，此时，无论如何有 (A_i = B_i)，不连，答案天然减一。
(2^circ~~P_i=i,Q_i ot = i) ，此时，拆 (y(i)) 才有 (A_i = B_i)，我们连一条 (y(i) o T) 的边。
(3^circ~~P_i ot = i, Q_i = i) ，此时，拆 (x(i)) 才有 (A_i = B_i)，我们连一条 (S o x(i)) 的边。
(4^circ~~P_i ot = i, Q_i ot = i)，此时，两个环都不拆时有 (A_i=B_i)，我们连一条 (y(i) o x(i)) 的边。
(5^circ~~P_i = Q_i ot = i)，此时 (x(i),y(i)) 应同时拆或同时不拆才有 (A_i=B_i)，我们连 (x(i) leftrightarrow y(i)) ，这个处理也是很经典的文理分科模型。
发现这是一个所有边权都是 (1) 的二分图，在这样的图上跑 Dinic 的时间复杂度将是 (O(nsqrt{n})) 的。