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\)的概率。
解题思路
<++>
神奇的代码