春季学期第一次讨论班，王博士讲了许多 AtCoder 上的思维题。
Slides: https://drive.google.com/file/d/10EVj_812TJNb4OlgBYxoEG-hdldre9X-/view?usp=sharing
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 行那个特判。虽然样例足够强，但是太大了，还是很难直接查到这个错的。
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\) 关系，不过到二叉树还是稍有困难。
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 。
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 上提到，需要附加条件： \(\bigoplus_{i=1}^n f(i) = 0 ~~~~~~~~ (*)\)
具体地，我设置根节点权为 \(0\) ，做一遍 dfs 得到其他点权。为了保证 \((*)\) 式成立，可以考虑将 \(f(1)\) 赋值为 \(\bigoplus_{i=2}^n f(i)\) ，重做一次 dfs。
这样做似乎非常地丑，也似乎有很好的做法，但是我没想到。
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)\) 的复杂度。
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\n", k), 0;
}
return 0;
}
我的常数实在太大了，再带上 STL 的 Buff 更大得不行， AtCoder 的测评姬跑得上气不接下气（
这题是真的很厉害，一些 basic ideas 组装起来，就变得神乎其神了。
原文：https://www.cnblogs.com/Shimarin/p/14534359.html