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)
题目大意
<++>
解题思路
<++>
神奇的代码
- Beginner AtCoder Contest 307beginner atcoder contest 307 contest programming beginner atcoder beginner atcoder contest 296 beginner atcoder contest 295 beginner atcoder contest abcde beginner atcoder contest 335 beginner atcoder contest 328 beginner atcoder contest 334 beginner atcoder contest 332 beginner atcoder contest 315