AtCoder Beginner Contest 345
A - Leftrightarrow (abc345 A)
题目大意
给定一个字符串，问是不是形如<======...====>的字符串。
解题思路
根据长度构造出期望的字符串，再判断是否相等即可。
神奇的代码
s = input()
print("Yes" if s == "<" + "=" * (len(s) - 2) + ">" else "No")
B - Integer Division Returns (abc345 B)
题目大意
给定\(a\)，输出 \(\lceil \frac{a}{10} \rceil\)
解题思路
上下取整的转换，\(\lceil \frac{a}{10} \rceil = \lfloor \frac{a + 9}{10} \rfloor\)。用下取整即可。
Python的//是下取证，C++的 /是向\(0\)取整，即正数时是下取整，负数时是上取整。
神奇的代码
a = int(input())
print((a + 9) // 10)
C - One Time Swap (abc345 C)
题目大意
给定一个字符串\(s\)，长度为\(n\)，问交换任意两个字符，可以得到的不同字符串个数。
解题思路
注意到交换的两个字符\(s_i \neq s_j\)不相同的话，得到的一定是个新的字符串，并且没有其他交换方式得到这个字符串。
而\(s_i == s_j\)时，则字符串不变。
因此， 可以 总情况数-字符串不变数，总情况数即为\(\frac{n(n-1)}{2}\)，字符串不变数则是\((i,j)\)满足 \(s_i==s_j, i < j\)的个数，这是一个经典计数问题，维护\(s_i\)的出现次数即可\(O(n)\)求得。
最后特别注意一下原字符串\(s\)是否会出现，即有两个字母相同就会出现。
当然也可以正向统计。
神奇的代码
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
int main(void) {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
string s;
cin >> s;
array<int, 26> cnt = {0};
LL n = 1ll * s.size() * (s.size() - 1) / 2;
for (auto c : s) {
n -= cnt[c - 'a'];
cnt[c - 'a']++;
}
if (ranges::max(cnt) > 1)
++n;
cout << n << '\n';
return 0;
}
D - Tiling (abc345 D)
题目大意
给定一个网格，有\(k\)块矩形板，问是否能选若干块板，恰好铺满网格，板可旋转。
解题思路
只有\(7\)块板，网格大小只有 \(10 \times 10\)，范围比较小，可以直接搜索。
如何搜索呢？起初考虑每块板放在何处，这个复杂度比较大。
从左上考虑，没被覆盖的第一个格子一定是某块板的左上角，因此从左到右，从上到下，找到没被覆盖的第一个格子，枚举其被哪块板覆盖即可。
复杂度感性理解下不会很大
神奇的代码
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
int main(void) {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int n, h, w;
cin >> n >> h >> w;
vector<array<int, 2>> a(n);
for (auto& i : a) {
cin >> i[0] >> i[1];
}
vector<vector<int>> full(h, vector<int>(w, 0));
auto set_full = [&](int i, int j, int k, int v) {
for (int x = 0; x < a[k][0]; x++) {
for (int y = 0; y < a[k][1]; y++) {
full[i + x][j + y] = v;
}
}
};
auto ok = [&](int i, int j, int k) -> bool {
if (i + a[k][0] > h || j + a[k][1] > w)
return false;
for (int x = 0; x < a[k][0]; x++) {
for (int y = 0; y < a[k][1]; y++) {
if (full[i + x][j + y])
return false;
}
}
return true;
};
auto find_unfull = [&]() -> pair<int, int> {
for (int i = 0; i < h; ++i) {
for (int j = 0; j < w; ++j) {
if (!full[i][j])
return {i, j};
}
}
return {-1, -1};
};
vector<int> used(n, 0);
auto dfs = [&](auto self, int x, int y) -> bool {
if (x == -1 && y == -1)
return true;
for (int i = 0; i < n; ++i) {
if (used[i])
continue;
if (ok(x, y, i)) {
set_full(x, y, i, 1);
auto [nx, ny] = find_unfull();
used[i] = 1;
if (self(self, nx, ny))
return true;
used[i] = 0;
set_full(x, y, i, 0);
}
swap(a[i][0], a[i][1]);
if (ok(x, y, i)) {
set_full(x, y, i, 1);
auto [nx, ny] = find_unfull();
used[i] = 1;
if (self(self, nx, ny))
return true;
used[i] = 0;
set_full(x, y, i, 0);
}
swap(a[i][0], a[i][1]);
}
return false;
};
if (dfs(dfs, 0, 0))
cout << "Yes" << endl;
else
cout << "No" << endl;
return 0;
}
E - Colorful Subsequence (abc345 E)
题目大意
\(n\)个球排成一排，球有颜色\(c_i\)，有价值\(v_i\)。
现需恰好移除 \(l\)个球，使得俩俩球颜色不同，且剩下的球的价值和最大。问最大值。
解题思路
按顺序考虑每个球，我们的决策就是是否移除这个球。考虑我们需要哪些状态。
首先肯定是前\(i\)个球这个基本状态。由于要恰好移除 \(l\)个球，因此当前已经移除的球数也必须知道。
除此之外，对于当前球移除或不移除，还取决于上一个球的颜色，因为不能有相邻两个相同的颜色的球。
据此可以有两种 \(dp\)方式，一种朴素的是 \(dp[i][j][k]\)表示前 \(i\)个球，已经移除了 \(j\)个，且最后一个球的颜色是 \(k\)时的剩余球最大价值和。这样对于当前球移除与否都能转移。初见这个\(dp\)感觉时间复杂度是\(O(n^3k)\)，但细想转移的话可见是 \(O(n^2k)\)。
还有一种方式为 \(dp[i][j]\) 表示前\(i\)个球，且我保留第 \(i\)个球，并且已经移除了 \(j\)个球的最大价值和，转移就枚举上一个保留的球的下标，其时间复杂度是 \(O(nk^2)\)。
由于 \(n\)有 \(10^5\), \(k\)有 \(500\)，两者的时间复杂度都太高了。思考如何优化，事实上最后这两种方式都可以优化到 \(O(nk)\)。
先考虑第一种 \(dp\)方式的转移式子：
其中\(1 \leq k_1, k \leq n\)表示颜色，且 \(k_1 \neq k\)。虽然这里是\(O(n^3k)\)，但考虑到，如果保留球，实际上只有一个\(dp[i][j][k]\)会改动，需要遍历\(dp[i-1][j][k_1]\)，如果不保留球，则直接 \(dp[i][j][k] = dp[i - 1][j - 1][k]\) ，转移是\(O(1)\)，只有一个状态转移是 \(O(n)\)。所以总的是\(O(n^2k)\)。
两大项的最大值分别对应着保留球和移除球这两种决策。其中保留球的决策中，需额外条件\(k_1 \neq k\)，即上一个球颜色不与当前球颜色相同。而 移除球的决策中，就一个值而已。
考虑如何优化转移，初看其实感觉很难优化，因为状态数就已经是\(O(n^2k)\)，优化转移的同时刚好可以把状态数优化到\(O(nk)\)。
对于后者转移，其就一项，转移就\(O(1)\)，无需过多考虑。
对于前者转移，如果没有\(k \neq k_1\)的条件，我维护\(dp[i-1][j][...]\)的最值，那转移就不需要遍历 \(k_1\)，通过维护的最值可以\(O(1)\)转移，就是在求 \(dp[i-1][j][...]\)的每一项时，就可以维护 \(mx[i-1][j] = \max(dp[i-1][j][...])\)。
棘手的就是\(k_1 \neq k\)这个条件，就是要求\(dp[i-1][j][...]\)除 \(dp[i-1][j][k]\)这一项的最值。
如何处理这个条件呢？事实上我们除了维护最大值，再维护一个次大值，这两个的颜色一定是不同的，那转移时，一定就是从这两个选一个出来转移。
即维护\(mx[i-1][j] = [[MAX1, color], [MAX2, color]]\)，这样，我每个\(dp[i][j][k]\)从可以从 \(mx[i-1][j]\)中\(O(1)\)找到原转移式里的 \(\max(dp[i-1][j][k_1])\)这一项 ，得以转移。
转移式变为\(dp[i][j][k] = \max(mx[i - 1][j][0] + v_i, mx[i - 1][j][1] + v_i, dp[i - 1][j - 1][k])\) ，其中\(mx\)那部分要判断颜色是否不同\((c_i \neq color)\)。最后的答案即为\(\max(dp[n][l][...])\)，或者说是 \(mx[n][l][0]\)。
但至此，只是将一个转移从\(O(n)\)降到了 \(O(1)\)，但状态数还是\(O(n^2k)\)，降不下来 ，怎么办呢？
注意到状态里的\(k\)，当初之所以定义\(k\)这个状态，是因为转移时要避免出现相邻球颜色相同（即能够转移），事实上这个状态非常冗余，它的用途只是为了转移，最后求解答案时不需要该状态（即对该状态的所有取值取个最值，而不关心具体是什么），观察上述的转移式，会发现这个\(k\)已经没有用了， 保留球的话转移从\(mx\)来就可以了，移除球的话，最终能成为\(mx[i][j]\)里的情况，也必定是 \(mx[i-1][j-1]\)里的最大值或次大值。
换句话说，这个 \(k\)的状态其实可以砍掉（就变成了 \(mx\)了），即 \(mx[i][j]\)表示前 \(i\)个球，移除 \(j\)个球后的两个两元组，分别表示(最大价值和，最后一个球的颜色)和 (次大价值和，最后一个球的颜色)。转移时同样考虑当前球保留或移除，保留的话，则从\(mx[i-1][j][0] + v \to mx[i][j]\)或 \(mx[i-1][j][1] + v \to mx[i][j]\) （看哪个颜色不同），移除的话就\(mx[i-1][j-1][0] \to mx[i][j]\)和 \(mx[i-1][j-1][1] \to mx[i][j]\)，这样就维护出 \(mx[i][j]\)的最大值和次大值，可以转移了。
由于每个\(mx[i][j]\)的转移都是依赖上一个\(mx[i-1]\)，这里也可以滚动数组优化下。
最后的时间复杂度是 \(O(nk)\)。
神奇的代码
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
const LL inf = 1e18;
int main(void) {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int n, k;
cin >> n >> k;
vector<array<pair<LL, int>, 2>> dp(k + 1, {{{-inf, -1}, {-inf, -1}}});
dp[0][0] = {0, 0};
auto update = [&](array<pair<LL, int>, 2>& a, pair<LL, int> b) {
if (b.first > a[0].first) {
swap(a[0], b);
}
if (b.second != a[0].second && b.first > a[1].first) {
swap(a[1], b);
}
};
for (int i = 0; i < n; ++i) {
int c, v;
cin >> c >> v;
vector<array<pair<LL, int>, 2>> dp2(k + 1, {{{-inf, -1}, {-inf, -1}}});
for (int j = 0; j <= k; ++j) {
if (dp[j][0].second != c) {
update(dp2[j], {dp[j][0].first + v, c});
}
if (dp[j][1].second != c) {
update(dp2[j], {dp[j][1].first + v, c});
}
if (j > 0) {
update(dp2[j], dp[j - 1][0]);
update(dp2[j], dp[j - 1][1]);
}
}
dp.swap(dp2);
}
cout << max(-1ll, dp[k][0].first) << '\n';
return 0;
}
还有另一种方式为 \(dp[i][j]\) 表示前\(i\)个球，且我保留第 \(i\)个球，并且已经移除了 \(j\)个球的最大价值和，转移就枚举上一个保留的球的下标，期间的球就被移除掉。其时间复杂度是 \(O(nk^2)\)，其中状态数\(O(nk)\)，转移耗时 \(O(k)\)。
即转移式\(dp[i][j] = \max(dp[i - k - 1][j - k]) + v_i, c_i \neq c_{i - k - 1}\)
考虑如何优化转移。观察转移式，转移枚举的是\(0 \leq k \leq l\)，将 \(dp[i][j]\)看作是一个二元函数的话，那一系列 \((i-k-1, j - k)\)点构成的是一条斜线，注意到这条斜线的特征是\(i-k-1-(j-k)=i-j-1\)是个定值。也就是说转移实际上就是在一条斜线取最值，但仍有 \(c_i \neq c_{i-k-1}\)这一棘手的条件。
对于这一棘手条件，处理的方法同上述一样，我们维护一条斜线的最大值和次大值。即\(mx[o]\)表示当前状态下， 满足\(i-j-1=o\)的这条斜线的\(dp[i][j]\)的最大值和次大值及其颜色，每个 \(dp[i][j]\)都从 \(mx[i-j-1]\)中得到颜色不相同的最值即可。这样转移就变为 \(O(1)\)了。
代码里是将\(mx[o]\)压成一个数，即我们的枚举顺序不是朴素的\(dp[i][0],dp[i][1],dp[i][2]...\)，而是一条条斜线，即 \(dp[i][0],dp[i+1][1],dp[i+2][2],...,dp[i+1][0],dp[i+2][1]...\)，当求完一条斜线的所有值时，再求下一条斜线。这样的话就不用保留其他斜线的最值信息，当需要的时候才算。朴素枚举顺序实际上是依次求每条斜线的每个点，所以需要保留历史信息，而当依次求完每条斜线时，就不需要保留其他斜线的信息了。
神奇的代码
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
const LL inf = 1e18 + 7;
int main(void) {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int n, k;
cin >> n >> k;
vector<int> c(n + 2), v(n + 2);
for (int i = 1; i <= n; ++i) {
cin >> c[i] >> v[i];
}
c[n + 1] = n + 1;
n += 2;
vector<vector<LL>> dp(n, vector<LL>(k + 1, -1));
dp[0][0] = 0;
for (int i = 1; i < n - k; i++) {
array<pair<LL, int>, 2> mx{{{-inf, -1}, {-inf, -1}}};
for (int j = 0; j <= k; ++j) {
pair<LL, int> la = {dp[i + j - 1][j], c[i + j - 1]};
if (la.first > mx[0].first)
swap(la, mx[0]);
if (la.second != mx[0].second && la.first > mx[1].first)
swap(la, mx[1]);
dp[i + j][j] = mx[c[i + j] == mx[0].second].first + v[i + j];
}
}
cout << max(-1ll, dp.back().back()) << '\n';
return 0;
}
F - Many Lamps (abc345 F)
题目大意
给定一张图，点上有灯，初始灯灭。
选择一条边，边上的两点的灯的状态会反转。
给出一种边的选择方案，使得恰好有\(k\)盏灯亮。
解题思路
是个构造题。初看这张图感觉无从下手，因为构造题一般要按照某种顺序执行，但图基本没有什么顺序可言。
可以在更简化的图考虑，比如图的\(DFS\)树，或者是生成树。
考虑在图的一棵生成树上，会发现有一种构造方法，可以使得根之外，其他点上的灯都能控制亮或灭。
从下往上，叶子到根考虑每个点，如果该点灯灭，则可以选择其父亲边，使其灯亮，或者灯亮变灯灭。
即每个点，都可以通过其父亲边使得它亮或灭，除了根节点之外，这个灯能亮能灭，全凭其点的度数是奇是偶。即一个连通块，除了个点之外，我能保证让其余点都灯亮。
注意到每选择一条边，要么两灯亮，要么两灯灭，要么一亮一灭，即亮灯数量始终是偶数。因此\(k\)是奇数的情况无解。
否则，注意原图不一定连通，则对于每个连通块，通过\(DFS\)从叶子考虑，尽量开满所有的灯，直到达到\(k\)盏灯为止，多开了就灭。
神奇的代码
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
int main(void) {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int n, m, k;
cin >> n >> m >> k;
vector<vector<array<int, 2>>> edge(n);
vector<int> du(n, 0);
for (int i = 0; i < m; i++) {
int u, v;
cin >> u >> v;
--u, --v;
edge[u].push_back({v, i + 1});
edge[v].push_back({u, i + 1});
}
if (k & 1) {
cout << "No" << endl;
return 0;
}
int up = 0;
vector<int> vis(n, 0);
vector<int> ans;
function<void(int, int, int)> dfs = [&](int u, int fa, int fa_id) {
debug(u, fa, fa_id);
int cnt = 0;
vis[u] = 1;
for (auto& [v, id] : edge[u]) {
if (vis[v] == 0) {
dfs(v, u, id);
}
}
if (du[u] & 1) {
--k;
}
if (u != fa) {
if (k > 0 && (~du[u] & 1)) {
ans.push_back(fa_id);
--k;
du[u]++;
du[fa]++;
} else if (k < 0 && (du[u] & 1)) {
ans.push_back(fa_id);
++k;
du[u]++;
du[fa]++;
}
}
};
for (int i = 0; i < n; i++) {
if (k != 0 && vis[i] == 0) {
dfs(i, i, -1);
}
}
if (k != 0)
cout << "No" << '\n';
else {
cout << "Yes" << '\n';
cout << ans.size() << '\n';
for (auto& i : ans)
cout << i << ' ';
cout << '\n';
}
return 0;
}
G - Sugoroku 5 (abc345 G)
题目大意
扔骰子，\([1,k]\)等概率出现。
对于每个 \(i \in [1,n]\)，问扔\(i\)次骰子后，其和 \(\geq n\)的概率。
解题思路
<++>
神奇的代码