「杂题乱写」AGC 004
点击查看目录
AGC 题目真挺小清新的。
一般来说只要有一个突破点就可以做出来，但是并不好想，感觉比较锻炼思维。
写题感觉思维上不去了可以来做做，挺愉悦身心的。
A | Divide a Cuboid
存在偶数可分成相等两块，不存在选两个乘积最小的。
B | Colorful Slimes
考虑枚举操作二次数。
WA 了一次，原因是 inf = 1ll << 40 不够大 ?
C | AND Grid
分别涂第一列和最后一列，奇数行和偶数行。
D | Teleporter
显然直接把 \(1\) 连向自己就可以。
然后把原图划分成多个子树连向 \(1\)，每个子树深度不超过 \(k\)。
点击查看代码
const ll N = 1e5 + 10;
namespace SOLVE {
ll n, k, dep[N], vis[N], ans;
std::vector <ll> tu[N];
inline ll rnt () {
ll x = 0, w = 1; char c = getchar ();
while (!isdigit (c)) { if (c == '-') w = -1; c = getchar (); }
while (isdigit (c)) x = (x << 3) + (x << 1) + (c ^ 48), c = getchar ();
return x * w;
}
inline void Dfs (ll u, ll fa) {
far (v, tu[u]) {
if (v == fa) continue;
Dfs (v, u), dep[u] = std::max (dep[u], dep[v] + 1);
}
if (dep[u] == k - 1 && u != 1 && fa != 1) ++ans, dep[u] = -1;
return;
}
inline void In () {
n = rnt (), k = rnt (), ans = (rnt () != 1);
_for (i, 2, n) tu[rnt ()].push_back (i);
return;
}
inline void Solve () {
Dfs (1, 0);
return;
}
inline void Out () {
printf ("%lld\n", ans);
return;
}
}
E | Salvage Robots
刚开始是觉得一个矩形只要不超过边界就都一定都可以到达出口。错的，有一个 Hack：
Hack 有乱劈的意思
5 5
.oo.o
..o.o
..oo.
E....
.o..o
正解是 DP。
设 \(f_{l, r, u, d}\) 表示清理过了左边 \(l\) 个方格，右边 \(r\) 个方格，上边 \(u\) 个方格，下边 \(d\) 个方格。
注意到移动后会有一些机器人被推出去（下图红框内的），转移时要判断一下。
设 \(s_{i1, j1, i2, j2}\) 表示左上角为 \((i1, j1)\)，右下角为 \((i2, j2)\) 的矩形中有多少个机器人。
转移就是：
用下图感性理解：
点击查看代码
const ll N = 110;
namespace SOLVE {
ll n, m, ex, ey, cnt[2][N][N], f[N][N][N][N], ans; char s[N][N];
inline ll rnt () {
ll x = 0, w = 1; char c = getchar ();
while (!isdigit (c)) { if (c == '-') w = -1; c = getchar (); }
while (isdigit (c)) x = (x << 3) + (x << 1) + (c ^ 48), c = getchar ();
return x * w;
}
inline void In () {
n = rnt (), m = rnt ();
_for (i, 1, n) scanf ("%s", s[i] + 1);
return;
}
inline void Solve () {
_for (i, 1, n) {
_for (j, 1, m) {
if (s[i][j] == 'E') ex = i, ey = j;
cnt[0][i][j] = cnt[0][i][j - 1] + (s[i][j] == 'o');
cnt[1][i][j] = cnt[1][i - 1][j] + (s[i][j] == 'o');
}
}
_for (l, 0, ey - 1) {
_for (r, 0, m - ey) {
_for (u, 0, ex - 1) {
_for (d, 0, n - ex) {
ans = std::max (ans, f[l][r][u][d]);
ll i1 = ex - u, i2 = ex + d, j1 = ey - l, j2 = ey + r;
if (l + r < ey - 1) f[l + 1][r][u][d] = std::max (f[l + 1][r][u][d], f[l][r][u][d] + cnt[1][std::min (i2, n - u)][j1 - 1] - cnt[1][std::max (i1 - 1, d)][j1 - 1]);
if (l + r < m - ey) f[l][r + 1][u][d] = std::max (f[l][r + 1][u][d], f[l][r][u][d] + cnt[1][std::min (i2, n - u)][j2 + 1] - cnt[1][std::max (i1 - 1, d)][j2 + 1]);
if (u + d < ex - 1) f[l][r][u + 1][d] = std::max (f[l][r][u + 1][d], f[l][r][u][d] + cnt[0][i1 - 1][std::min (j2, m - l)] - cnt[0][i1 - 1][std::max (j1 - 1, r)]);
if (u + d < n - ex) f[l][r][u][d + 1] = std::max (f[l][r][u][d + 1], f[l][r][u][d] + cnt[0][i2 + 1][std::min (j2, m - l)] - cnt[0][i2 + 1][std::max (j1 - 1, r)]);
}
}
}
}
return;
}
inline void Out () {
printf ("%lld\n", ans);
return;
}
}
F | Namori
好难啊。好难啊。好难啊。好难啊。好难啊。好难啊。好难啊。好难啊。好难啊。
看 gtm1514 老师题解看懂的 /bx /bx /bx
这里就口胡一下，你要真想看懂就别看我的。
数据范围 \(N - 1\le M\le N\)，所以图是一个树或基环树！
考虑转化题意，可以转化为把图黑白交替染色，于是操作就变成了交换黑白点，目标是黑白对调。
\(n\) 为奇数显然无解。
先从树入手。假设以 \(u\) 节点为根的子树有 \(x\) 个黑点，\(y\) 个白点，那么 \(u\) 通往父亲的边至少会被经过 \(a_u = \left|x - y\right|\) 次，求和即可。
然后考虑偶环基环树。我们断一条边，然后考虑环的贡献。操作 \(x\) 次这条边的话，环上会有一些边多向上跑 \(x\) 次，一些边多向下跑 \(x\) 次。维护一个 \(k\) 数组标记左右半环，断的边左端点标记 \(1\)，右端点标记 \(-1\)，环上答案应该是 \(\sum_{u\text{ on the ring}}\left|a_ik_i - x\right|\)。
现在问题是 \(x\) 取什么能让这个式子值最小，答案是中位数。
最后考虑奇环基环树。染色后一定会有一条边两端点颜色相同，操作这条边相当于加上/减少两个黑点，那么设树上共有 \(x\) 个黑点，\(y\) 个白点，那么操作 \(\frac{\left|x - y\right|}{2}\) 次即可平衡黑白点数量。
注意到只有奇环基环树可以平衡黑白点数量，所以如果普通树/偶环基环树黑白点数量不一样也无解。
点击查看代码
const ll N = 1e5 + 10;
namespace SOLVE {
ll n, m, c[N], zhiyin, e[2], k[N], ring[N], ans;
std::vector <ll> tu[N];
inline ll rnt () {
ll x = 0, w = 1; char c = getchar ();
while (!isdigit (c)) { if (c == '-') w = -1; c = getchar (); }
while (isdigit (c)) x = (x << 3) + (x << 1) + (c ^ 48), c = getchar ();
return x * w;
}
inline void Paint (ll u, ll fa, ll color) {
c[u] = color;
far (v, tu[u]) {
if (v == fa) continue;
if (!c[v]) Paint (v, u, -color);
else {
if (c[u] == c[v]) zhiyin = 1;
e[0] = u, e[1] = v;
}
}
return;
}
inline void GetAns (ll u, ll fa) {
far (v, tu[u]) {
if (v == fa || (u == e[0] && v == e[1]) || (u == e[1] && v == e[0])) continue;
GetAns (v, u), c[u] += c[v], k[u] += k[v];
}
return;
}
inline void In () {
n = rnt (), m = rnt ();
_for (i, 1, m) {
ll u = rnt (), v = rnt ();
tu[u].push_back (v);
tu[v].push_back (u);
}
return;
}
inline void Solve () {
if (n & 1) { ans = -1; return; }
Paint (1, 0, 1);
ll cnt = 0;
_for (i, 1, n) cnt += c[i];
if (m == n - 1 && cnt) { ans = -1; return; }
if (m == n) {
if (zhiyin) ans += std::abs (cnt / 2), c[e[0]] -= cnt / 2, c[e[1]] -= cnt / 2;
else {
if (cnt) { ans = -1; return; }
else k[e[0]] = 1, k[e[1]] = -1;
}
}
GetAns (1, 0);
_for (i, 1, n) {
if (k[i]) ring[++ring[0]] = c[i] * k[i];
else ans += std::abs (c[i]);
}
ring[++ring[0]] = 0;
std::sort (ring + 1, ring + ring[0] + 1);
ll mid = ring[(ring[0] + 1) >> 1];
_for (i, 1, ring[0]) ans += std::abs (ring[i] - mid);
return;
}
inline void Out () {
printf ("%lld\n", ans);
return;
}
}