A - Overall Winner (abc301 a)
题目大意
给定一个字符串表示高桥和青木每局的获胜情况。
如果高桥获胜局数多，或者两个胜局相等，但高桥率先取得那么多胜场，则高桥获胜，否则青木获胜。
问谁获胜。
解题思路
按照题意，统计两者的获胜局数比较即可。
如果两者局数相等，可以看最后一局谁胜，青木胜则意味着高桥率先取得那么多胜场，即高桥胜，反之青木胜。
神奇的代码
#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;
int t = count(s.begin(), s.end(), 'T'), a = n - t;
if (t > a || (t == a && s.back() == 'A'))
cout << "T" << '\n';
else
cout << "A" << '\n';
return 0;
}
B - Fill the Gaps (abc301 b)
题目大意
给定一个序列，对于两个相邻元素，若其值不是相邻的，则补充之间的值。
问最终的序列。
解题思路
按照题意模拟即可。
神奇的代码
#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, la;
cin >> n >> la;
cout << la;
for(int i = 1; i < n; ++ i){
int x;
cin >> x;
for(int d = (x - la) / abs(x - la), cur = la + d; cur != x; cur += d)
cout << ' ' << cur;
cout << ' ' << x;
la = x;
}
cout << '\n';
return 0;
}
C - AtCoder Cards (abc301 c)
题目大意
给定两个长度相等的字符串\(s_1, s_2\)，包含小写字母和@，问能否将@替换成atcoder中的一个字母，可以通过对其中一个字符串排序，使得两者相同。
解题思路
由于可以排序，我们只考虑两者的每个字母个数相同。
因为@只能替换成atcoder中的一个字母，因此这些字母之外的字母的数量必须相等。
然后考虑\(s_1\)相对于 \(s_2\)，缺少的 atcoder的字母，如果其数量\(cnt\)小于 \(s_1\)的@数量，则可以通过 @替换满足缺少的字母。反之也考虑\(s_2\)相对于\(s_1\)的情况。
如果两者都满足，那么两个就只剩下@了，这个肯定可以满足题意要求的。
神奇的代码
#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[2];
cin >> s[0] >> s[1];
map<char, int> cnt[2];
for(int j = 0; j <= 1; ++ j)
for(auto &i : s[j])
cnt[j][i] ++;
set<char> target{'a', 't', 'c', 'o', 'd', 'e', 'r'};
auto ok1 = [&](){
for(int i = 'a'; i <= 'z'; ++ i){
if (target.find(i) != target.end())
continue;
if (cnt[0][i] != cnt[1][i])
return false;
}
return true;
};
auto ok2 = [&](int x, int y){
int at = count(s[x].begin(), s[x].end(), '@'), tot = 0;
for(auto &i : target){
tot += max(cnt[y][i] - cnt[x][i], 0);
}
return at >= tot;
};
if (!ok1() || !ok2(0, 1) || !ok2(1, 0))
cout << "No" << '\n';
else
cout << "Yes" << '\n';
return 0;
}
D - Bitmask (abc301 d)
题目大意
给定一个包含\(01\)和 ?的字符串，将?替换成\(0\)或 \(1\)，使得其表示的二进制是最大的，且不大于\(t\)的。问这个的最大值。
解题思路
由于二进制下，任意个数的低位的\(1\)加起来都不如一个高位的 \(1\)。因此我们就从高位考虑每个 ?，如果替换成\(1\)之后不超过 \(t\)，就换成 \(1\)，否则就换成 \(0\)。
神奇的代码
#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;
LL n;
cin >> s >> n;
LL cur = 0;
for(auto &i : s){
cur <<= 1;
if (i != '?')
cur |= (i - '0');
}
LL ji = (1ll << (s.size() - 1));
for(auto &i : s){
if (i == '?' && cur + ji <= n)
cur += ji;
ji >>= 1;
}
if (cur > n)
cur = -1;
cout << cur << '\n';
return 0;
}
E - Pac-Takahashi (abc301 e)
题目大意
二维迷宫，有一个起点和一个终点，有墙，有最多\(18\)个糖果。问从起点到终点，移动距离不超过 \(t\)的情况下，能获得的糖果数量的最大值。
解题思路
考虑搜索，虽然可移动的范围挺大的，但是我们可以进行压缩，即可以只考虑从起点到糖果、糖果到糖果、糖果到终点，这三类关键操作。
首先通过多次\(BFS\)获得糖果之间的移动距离。
由于糖果只能获得一次，因此当我们抵达某个位置时，需要判断这个位置是否曾经抵达过，需要一个\(01\)状态 \(s\)表示我们获得了哪些糖果。
既然是搜索，肯定还有个状态是我们当前所在的位置，然后转移就是寻找下一个未获得的糖果位置或者终点。
发现状态数只有\(2^{18} \times 18=5e6\)，因此记忆化一下就可以了。
即设 \(dp[i][j]\)表示当前糖果的获得状态是 \(i\)，当前在第 \(j\)个糖果的位置时，移动距离的最小值。
取抵达终点的移动距离不大于 \(t\)的所有 \(i\)中二进制下 \(1\)的最大值即为答案。
总的时间复杂度是\(O(m^{2}2^m + hwm)\)， \(hw\)是迷宫大小，\(m\)是糖果数量。
其实从朴素搜索角度，维护的是一个糖果访问序列，其状态数是\(18!\)，但容易发现这个状态中， 顺序这个信息是多余的：无论访问的顺序如何，只要访问的点集是一样的，那么糖果数就是一样，只是所需要的步数不一样。既然糖果数是一样的，有那么多个状态都能达到同一个糖果数，肯定是想让其步数越小越好，这样，从这个状态继续搜索，得到的结果肯定会比其他步数时更优。因此我们就把顺序这个信息丢弃，改成维护一个糖果是否访问的状态，其值是对应原状态中步数的最小值，这样状态数就降到了\(2^{18}\)（压缩）。当然当前所在的位置这个状态还要保留。
即点集\(\{1,2,3,4\}\)，最终停在\(4\)号点。我有很多 种顺序访问这个点集（\(1 \to 2 \to 3 \to 4, 1 \to 3 \to 2 \to 4\)），但其中有一种所花费的步数是最小的。然后从这个状态出发（\(4 \to 6, 4 \to 5\)），所做出的决策与你之前以怎样的顺序访问点\(\{1,2,3,4\}\)无关，只与你是否访问了这些点有关，并且后继状态的贡献与先前决策无关（不会因为，先访问\(3\)号点再访问 \(2\)号点，而使得\(4 \to 6\)有额外的奖励） ，因此我们肯定是以抵达这个状态的最优决策（步数最小）继续出发，而以步数更大的状态出发，肯定是不优的（其实这类似于最优子结构）。所以这个顺序信息可以丢弃，状态可以进一步压缩，只储存步数最优的状态。
神奇的代码
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
const int inf = 1e9 + 7;
const array<int, 2> dir[4]{{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
int main(void) {
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
int h, w, t;
cin >> h >> w >> t;
vector<string> tu(h);
for(auto &i : tu)
cin >> i;
int candy = 0;
for(auto &i : tu)
candy += count(i.begin(), i.end(), 'o');
vector<vector<int>> dis(candy, vector<int>(candy, 0));
map<array<int, 2>, int> tr;
map<int, array<int, 2>> invtr;
vector<vector<int>> tmpdis(h, vector<int>(w));
int cnt = 0, sx, sy, ex, ey;
for(int i = 0; i < h; ++ i)
for(int j = 0; j < w; ++ j)
if (tu[i][j] == 'o'){
tr[{i, j}] = cnt;
invtr[cnt] = {i, j};
cnt ++;
}else if (tu[i][j] == 'S'){
sx = i;
sy = j;
}else if (tu[i][j] == 'G'){
ex = i;
ey = j;
}
auto BFS = [&](int x, int y){
for(auto &i : tmpdis)
fill(i.begin(), i.end(), inf);
tmpdis[x][y] = 0;
queue<array<int, 2>> team;
team.push({x, y});
while(!team.empty()){
auto [u, v] = team.front();
team.pop();
for(const auto& [dx, dy] : dir){
int nx = u + dx, ny = v + dy;
if (nx >= 0 && nx < h && ny >= 0 && ny < w && tu[nx][ny] != '#' && tmpdis[nx][ny] > tmpdis[u][v] + 1){
tmpdis[nx][ny] = tmpdis[u][v] + 1;
team.push({nx, ny});
}
}
}
};
for(auto &[key, value] : tr){
BFS(key[0], key[1]);
for(auto &[pos, id] : tr){
dis[value][id] = tmpdis[pos[0]][pos[1]];
}
}
vector<vector<int>> dp((1 << candy), vector<int>(candy, inf));
BFS(sx, sy);
if (tmpdis[ex][ey] > t)
cout << -1 << '\n';
else{
for(auto &[pos, id] : tr)
dp[(1 << id)][id] = tmpdis[pos[0]][pos[1]];
BFS(ex, ey);
int ans = 0;
for(int i = 1, up = (1 << candy); i < up; ++ i){
for(int j = 0; j < candy; ++ j){
if ((i >> j) & 1){
for(int k = 0; k < candy; ++ k){
if (((~i >> k) & 1) && dp[i][j] + dis[j][k] <= t){
dp[i | (1 << k)][k] = min(dp[i | (1 << k)][k], dp[i][j] + dis[j][k]);
}
}
if (dp[i][j] + tmpdis[invtr[j][0]][invtr[j][1]] <= t)
ans = max(ans, __builtin_popcount(i));
}
}
}
cout << ans << '\n';
}
return 0;
}
F - Anti-DDoS (abc301 f)
题目大意
给定一个包含大小写字母和?的字符串\(s\)，将 ?替换成大小写字母。问有多少种替换情况，使得替换后的字符串不包含DDoS类型的子序列。
DDoS类型的字符串满足，长度为\(4\)，第 \(1,2,4\)字母是大写，第 \(3\)字母是小写，且第 \(1,2\)字母相同。
解题思路
计数类问题，最朴素的做法自然就是枚举每个?的取值，然后判断该情况是否符合要求。如何加速统计，需要找到类似的状态，把它们压缩捆绑起来，通过乘法原理一并继续统计。问题就是如何找到所谓的类似的状态。
考虑朴素做法，枚举每个?的取值后，如何判断这个字符串不包含DDoS类型的子序列。
维护一个大写字母出现的次数数组cnt，从左到右遍历这个字符串，如果遇到一个大写字母出现了两次，那么就继续找小写字母，找到小写字母后，再寻找是否有大写字母。
观察这个判断过程，我们的状态有三种：
- 没有出现两个相同大写字母（记为状态
C） - 出现了两个相同的大写字母（记为状态
A） - 出现了两个相同的大写字母和一个小写字母（记为状态
B）
其中第一个状态可能需要细分，即有哪些大写字母出现了一次（即cnt数组）。
上述所说的状态就是所谓的可以捆绑起来的类似状态：无论之前的?取什么值，只要当前（长度为i的前缀）的状态是这个，我就可以继续往下统计答案（当前状态A，然后出现了小写字母，则变为状态B，而无需关心是哪个大写字母出现了两次，相当于将这些状态捆绑起来计算；或者出现了?，取值为大写字母，则有26种方式变为状态A，取值为小写字母，也有26种方式变为状态B）。
如果状态设计不当，就可能无法继续统计（缺少了必要的信息）。即如果当前状态是C，那么当遇到一个大写字母Z时，我们就不知道接下来是变成状态A还是状态C（因为我们不知道大写字母Z之前是否出现过，如果出现过则状态会变成A，没出现过则还是C），而如果遇到?，我们不知道?有多少种取值情况，使得接下来的状态变成A，或者是C（如果大写字母数量是\(x\)，则前者有\(x\)种方式，后者有\(26 - x + 26\)种方式，\(+26\)是小写字母情况）。因此状态C还要进一步细分。
思考上述提出的两个无法继续统计的情况，一个是缺少大写字母出现的信息，一个是缺少大写字母出现的个数的信息。
如果我们把状态C细分成一个二进制状态，即cnt数组的二进制压缩表示，以标识每个大写字母是否出现。拥有了这个信息，上述的转移问题就可以解决。
即设\(dp[i][j]\)表示前 \(i\)个字母，当前为状态 j（包括上述的状态A和B）的方案数，根据\(s[i+1]\)的取值更新\(dp[i+1][*]\)计数。
但这样的状态数是\(2^{26} \times n\)，而\(n \leq 10^5\)，这状态数高达\(10^{12}\)，完全不行。
细分太猛了，考虑将状态C细分成仅出现一次的大写字母个数，这样遇到?时还是可以转移的（上面提到了），而遇到大写字母得考虑能否转移。
对于一个长度为\(i\)的前缀，除去 ?，大写字母出现的个数为\(j\)个（均出现一次，如果出现两次及以上则变成状态 A或B，可以继续转移的），而如果当前的状态是\(k > j\)，意味着前面的有些 ?变成了没出现的大写字母。然后此时遇到了个大写字母Z，考虑能否转移。
如果前面也有大写字母Z，此时毫无疑问，状态会变成A。而如果前面没有大写字母Z，那就考虑前面的?是否变成大写字母Z，需要从状态\(k\)中，抽出没有Z的方案数，贡献给状态\(k+1\)，抽出有Z的方案，贡献给状态A。
幸运的是，由于每个字母都是等价的，这意味着这里的方案数存在着某种对称性，我们真的可以从状态\(dp[i][k]\)表示的方案数中，抽取出不包含 Z的方案数，累加到状态\(dp[i + 1][k + 1]\)，抽取包含 Z的方案数，累加到状态\(dp[i + 1][A]\)
设前 \(i\)个字母中，有 \(j\)个非?的大写字母，当前状态\(k\)，那么不包含 Z的方案数就是\(dp[i][k] \times \frac{\tbinom{25 - j}{k - j}}{\tbinom{26 - j}{k - j}} = dp[i][k] \times \frac{26 - k}{26 - j}\)，包含 Z的方案数就是\(dp[i][k] \times \frac{\tbinom{25 - j}{k - j - 1}}{\tbinom{26 - j}{k - j}} = dp[i][k] \times \frac{k - j}{26 - j}\)，前者就贡献给\(dp[i + 1][k + 1]\)，后者就贡献给 \(dp[i + 1][A]\)。
转移的问题解决了，状态数只有\(26n\)，可以通过本题了。
总的来说，设\(dp[i][j]\)表示前 \(i\)个字母，当前状态是 \(j\)的方案数。其中 \(j \in [0, 28]\) ，其中\([0,26]\)表示所有大写字母仅出现一次，且有 \(j\)个， \(j = 27\)表示存在大写字母出现两次及以上，即上述的状态 \(A\) ，\(j = 28\)表示存在出现两次的大写字母之后还有个小写字母，即状态 \(C\)。
然后根据当前状态和下一个字母的情况，转移计算 \(dp[i+1][*]\)数组。
转移规则细说的话太长了，简单来说状态关联如下所示，系数比较容易想，最难想的遇到大写字母的\(0-26\)的转移上述已说明的。
遇到小写字母：
- \(0-26 \to 0-26\)
- \(27 \to 28\)
- \(28 \to 28\)
遇到大写字母
- \(0-26 \to 1-27\)
- \(27 \to 27\)
-
\(28 \to\)出现
DDoS，寄
遇到?:
- \(0-26 \to 0-27\)
- \(27 \to 27-28\)
- \(28 \to 28\)
初始条件就是\(dp[0][0] = 1\)
神奇的代码
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
const int mo = 998244353;
int qpower(int a, int b){
int qwq = 1;
while(b){
if (b & 1)
qwq = 1ll * qwq * a % mo;
a = 1ll * a * a % mo;
b >>= 1;
}
return qwq;
}
int inv(int x){
return qpower(x, mo - 2);
}
int main(void) {
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
string s;
cin >> s;
vector<int> dp(29, 0);
dp[0] = 1;
int used = 0;
for(auto &c : s){
vector<int> dp2(29, 0);
if (islower(c)){
for(int i = 0; i <= 26; ++ i)
dp2[i] = dp[i];
dp2[28] = dp[27] + dp[28];
if (dp2[28] >= mo)
dp2[28] -= mo;
}else if (isupper(c)){
if ((used >> (c - 'A')) & 1){
dp2[27] = accumulate(dp.begin(), dp.begin() + 28, 0ll) % mo;
}else{
int cnt = __builtin_popcount(used);
for(int i = cnt; i <= 26; ++ i){
dp2[i + 1] = (dp2[i + 1] + 1ll * dp[i] * (26 - i) % mo * inv(26 - cnt)) % mo;
dp2[27] = (dp2[27] + 1ll * dp[i] * (i - cnt) % mo * inv(26 - cnt) % mo) % mo;
}
dp2[27] = dp2[27] + dp[27];
if (dp2[27] >= mo)
dp2[27] -= mo;
used |= (1 << (c - 'A'));
}
}else if (c == '?'){
for(int i = 0; i <= 26; ++ i){
dp2[i] = (dp2[i] + 1ll * dp[i] * 26) % mo;
dp2[i + 1] = (dp2[i + 1] + 1ll * dp[i] * (26 - i)) % mo;
dp2[27] = (dp2[27] + 1ll * dp[i] * i) % mo;
}
dp2[27] = (dp2[27] + 1ll * dp[27] * 26) % mo;
dp2[28] = (1ll * (dp[27] + dp[28]) * 26) % mo;
}else{
assert(1 == 0);
}
dp.swap(dp2);
}
cout << accumulate(dp.begin(), dp.end(), 0ll) % mo << '\n';
return 0;
}
其实状态从 排序\(\to\)01二进制\(\to\)个数这样的\(O(n!) \to O(2^n) \to O(n)\)的压缩挺常见的，像abc301 E就是经历了\(O(n!) \to O(2^n)\)的过程，至于为什么没有到 \(O(n)\)，即只记录访问了多少个有糖果的位置，在考虑转移的时候你会发现根本就无法转移，因为丢掉的信息太多了，单从访问数量来说，根本不知道接下来访问的糖果位置之前有没有访问过，转移无从下手，因此就不能继续压缩了。
G - Worst Picture (abc301 g)
题目大意
<++>文章来源地址https://www.toymoban.com/news/detail-442931.html
解题思路
<++>
神奇的代码
Ex - Difference of Distance (abc301 h)
题目大意
<++>文章来源：https://www.toymoban.com/news/detail-442931.html
解题思路
<++>
神奇的代码
到了这里，关于AtCoder Beginner Contest 301的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
