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)
题目大意
<++>
解题思路
<++>
神奇的代码
文章来源: 博客园
- 还没有人评论，欢迎说说您的想法！
客服
