AtCoder Beginner Contest 307
A - Weekly Records (abc307 A)
题目大意
给定\(n\)周每天的散步量，求每周七天的散步量的和。
解题思路
累计求和即可。
神奇的代码
#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;
cin >> n;
while(n--){
int sum = 0;
for(int i = 0; i < 7; ++ i){
int a;
cin >> a;
sum += a;
}
cout << sum << ' ';
}
return 0;
}
B - racecar (abc307 B)
题目大意
给定\(n\)个字符串 \(s\)，问能否选择两个 \(i,j\)，满足 \(i \neq j\)，且 \(s_i + s_j\)是个回文串。
解题思路
只有\(100\)个串，直接 \(O(n^2)\)枚举判断即可。
判断回文可以将串反转后与原先的串比较是否相同。
神奇的代码
#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;
cin >> n;
vector<string> s(n);
for(auto &i : s)
cin >> i;
auto palind = [&](int x, int y){
string l = s[x] + s[y];
string r = l;
reverse(r.begin(), r.end());
return l == r;
};
auto ok = [&](){
for(int i = 0; i < n; ++ i)
for(int j = 0; j < n; ++ j){
if (i != j && palind(i, j))
return true;
}
return false;
};
if (ok())
cout << "Yes" << '\n';
else
cout << "No" << '\n';
return 0;
}
C - Ideal Sheet (abc307 C)
题目大意
给定两个二维网格的模式图，有一些格子是黑的，有一些格子是透明的。
问能否通过这两个模式图得到一个期望的模式图，要求格子的属性（黑或透明）相同。
操作是将这两个模式图分别盖印到一个无穷大的二维网格上，仅能盖一次，然后通过裁剪得到期望模式图。
注意盖印的黑色格子都必须保留，不得裁剪掉。
解题思路
因为模式图大小只有\(10 \times 10\)，因此直接 \(O(10^4)\)枚举两个模式图的盖印位置，然后判断盖印后的结果是否与期望模式图相同。
注意盖印后的黑色格子都必须在期望模式图范围内，所以还需统计期望模式图范围内的两个模式图的黑色格子数，不能有超出期望模式图范围的黑色格子。
神奇的代码
#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);
array<int, 3> h, w;
array<vector<string>, 3> d;
array<int, 3> blk{};
for(int i = 0; i < 3; ++ i){
cin >> h[i] >> w[i];
d[i].resize(h[i]);
for(int j = 0; j < h[i]; ++ j){
cin >> d[i][j];
blk[i] += count(d[i][j].begin(), d[i][j].end(), '#');
}
}
auto check = [&](int x1, int y1, int x2, int y2){
int tot = 0;
for(int i = 0; i < h[2]; ++ i)
for(int j = 0; j < w[2]; ++ j){
int target = (d[2][i][j] == '#');
int blk1 = (i >= x1 && j >= y1 && i - x1 < h[0] && j - y1 < w[0] && d[0][i - x1][j - y1] == '#');
int blk2 = (i >= x2 && j >= y2 && i - x2 < h[1] && j - y2 < w[1] && d[1][i - x2][j - y2] == '#');
tot += blk1 + blk2;
if (target != (blk1 || blk2))
return false;
}
return (tot == blk[0] + blk[1]);
};
auto ok = [&](){
for(int i = -10; i <= 10; ++ i)
for(int j = -10; j <= 10; ++ j)
for(int k = -10; k <= 10; ++ k)
for(int l = -10; l <= 10; ++ l){
if (check(i, j, k, l))
return true;
}
return false;
};
if (ok())
cout << "Yes" << '\n';
else
cout << "No" << '\n';
return 0;
}
D - Mismatched Parentheses (abc307 D)
题目大意
给定一个包含小写字母、(、)的字符串。每次选择一个开头是(，结尾是)，且中间不包含这两个字符的子串，移除该子串。
问最终剩余的字符串是怎样的。
解题思路
每次移除的其实是一个最里面的合法的()，假设有(()())，每次移除的都是最里端的一对()，因此反复这么操作，合法的括号序列都会被移除掉。
因此我们对原字符串的每个(统计与之对应的)，这样每个()之间的内容都会被移除。
根据这个对应关系就会跳过一些字符串（被移除了），剩下的就是没被移除的了。
神奇的代码
#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;
string s;
cin >> n >> s;
vector<int> r(n, -1);
stack<int> pos;
for(int i = 0; i < n; ++ i){
if (s[i] == '(')
pos.push(i);
else if (s[i] == ')' && !pos.empty()){
r[pos.top()] = i;
pos.pop();
}
}
for(int i = 0; i < n; ++ i){
if (r[i] != -1){
i = r[i];
}else {
cout << s[i];
}
}
cout << '\n';
return 0;
}
E - Distinct Adjacent (abc307 E)
题目大意
给定一个\(n\)个数的环形数组，每个数的取值为\([1, m]\)。
问有多少种取值情况，满足任意相邻两个数不相同。
解题思路
如果不是环形，答案很明显是\(m \times (m - 1)^(n - 1)\)。但由于环形，最后一位的取值难以确定是\(n - 1\)还是 \(n - 2\)，这取决于倒数第二位是否和第一位相同。
如何解决呢？其实问题的核心上面已经指明了：倒数第二位是否和第一位相同。
- 如果相同，则最后一位可取\(n - 1\)种情况。
- 如果不相同，则最后一位可取 \(n - 2\)种情况。
由于每个数都是对称的，我们假设第一位填的数是 \(1\)。然后设 \(dp[i][0/1]\)表示前 \(i\)位，相邻两数不同（不考虑首尾），且最后一位与首位数字不同/相同的方案数。转移就看当前位是否与首位相同。
因为上述我们假定了首位取\(1\)，事实上首位取什么值情况都一样，而它有 \(m\)种取法，因此最终答案就是\(m \times dp[n][0]\)。
神奇的代码
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
const int mo = 998244353;
int main(void) {
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
int n, m;
cin >> n >> m;
array<int, 2> dp{0, 1};
for(int i = 1; i < n; ++ i){
array<int, 2> dp2{};
dp2[0] = 1ll * dp[0] * (m - 2) % mo + 1ll * dp[1] * (m - 1) % mo;
if (dp2[0] >= mo)
dp2[0] -= mo;
dp2[1] = dp[0];
dp.swap(dp2);
}
cout << 1ll * dp[0] * m % mo << '\n';
return 0;
}
F - Virus 2 (abc307 F)
题目大意
给定一张无向图，边有边权。
初始有\(a\)个点感染病毒。
持续 \(d\)天。对于第 \(i\)天，所有与已感染病毒的点距离不超过\(x_i\)的点都会被感染病毒。
问每个点第一次被感染病毒的天数。
解题思路
<++>
神奇的代码
G - Approximate Equalization (abc307 G)
题目大意
给定一个有\(n\)个数的数组，可进行两种操作：
- 选定一个\(i\)，令 \(a_i = a_i - 1, a_{i + 1} = a_{i + 1} + 1\)
- 选定一个\(i\)，令 \(a_i = a_i + 1, a_{i + 1} = a_{i + 1} - 1\)
问最少进行的操作次数，使得数组的极差不超过\(1\)。
解题思路
观察操作，可以发现每次操作后，这个数组的总和\(sum\)是不变的。（其实可以看成有\(sum\)个小球， \(n - 1\)个隔板，每次操作其实就是移动一个隔板到相邻位置）
由于极差不超过\(1\)，那么最终每个数要么是 \(div = \lfloor \frac{sum}{n} \rfloor\)，要么是 \(div + 1\)，且至多有\(sum \% n\)个数是后者。问题就是让哪些数是后者，哪些数是前者。
首先明确一点，如果给定最终的数组，求将该数组变成最终数组的操作次数，其最优方案是可以在\(O(n)\)内求出来。就是依次对每个数\(a_i\)，将其变为目标值\(t_i\)，需要从后一个数 \(a_{i + 1}\)借多少次（操作二），还是给多少次（操作一），然后这个借和给的影响是持续的。
现在问题变成了让哪些数是\(div\)，哪些是\(div+1\)，这是个分配问题，设 \(dp[i][j]\)表示前 \(i\)个数，还有 \(j\)个 \(div+1\)的未分配的最小操作数。需要第二维状态一方面是要确保有\(mod\)个 \(div + 1\)，另一方面是需要知道由于前面的数的操作，当前数变成了多少。
对于当前数\(a_i\)，知道了 \(j\)，我们就知道前面有多少个数是 \(div+1\)，多少个数是\(div\)，进而知道，在上述求解操作的影响下， \(a_i\)变成了多少，然后就可以进一步求解 \(a_i\)变成目标数所需要的操作次数了。
注意如果\(mod = sum \% n\)是负数，则可以让\(div = div - 1, mod = n - mod\)，这样就变回正数了。
神奇的代码
#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;
cin >> n;
vector<LL> a(n);
for(auto &i : a)
cin >> i;
LL sum = accumulate(a.begin(), a.end(), 0ll);
LL div = sum / n, mod = sum % n;
if (mod < 0){
mod = n + mod;
div --;
}
vector<LL> dp(mod + 1, inf);
dp[mod] = 0;
LL presum = 0;
LL tot = 0;
for(auto &x : a){
vector<LL> dp2(mod + 1, inf);
for(int i = 0; i <= mod; ++ i){
LL cur = x - (tot + mod - i - presum);
dp2[i] = min(dp2[i], dp[i] + abs(cur - div));
if (i)
dp2[i - 1] = min(dp2[i - 1], dp[i] + abs(cur - div - 1));
}
presum += x;
tot += div;
dp.swap(dp2);
}
cout << dp[0] << '\n';
return 0;
}
Ex - Marquee (abc307 Ex)
题目大意
<++>
解题思路
<++>
神奇的代码