T1：Scoreboard
模拟
代码实现
n = int(input())
st, sa = 0, 0
for i in range(n):
x, y = map(int, input().split())
st += x;
sa += y
if st < sa:
print('Aoki')
if st == sa:
print('Draw')
if st > sa:
print('Takahashi')
T2：Extended ABC
正则表达式
代码实现
#include <bits/stdc++.h>
using namespace std;
int main() {
string s;
cin >> s;
regex re("A*B*C*");
if (regex_match(s, re)) puts("Yes");
else puts("No");
return 0;
}
T3：Lining Up 2
从排在第一的人开始往后遍历即可
代码实现
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
using namespace std;
int main() {
int n;
cin >> n;
vector<int> a(n);
rep(i, n) cin >> a[i];
rep(i, n) if (a[i] != -1) a[i]--;
vector<int> d(n);
rep(i, n) if (a[i] != -1) d[a[i]] = i;
int s = -1;
rep(i, n) if (a[i] == -1) s = i;
vector<int> ans{s};
rep(i, n-1) {
s = d[s];
ans.push_back(s);
}
rep(i, n) cout << ans[i]+1 << ' ';
return 0;
}
T4：Cheating Gomoku Narabe
其实就是对每行每列分别考虑以下的一维问题：
- 在一个长度为 \(n\) 的字符串中，通过将
.修改为o使得其中有长度为 \(k\) 个o的连续子串的最少修改次数
首先要判定长度为 \(k\) 的子串是否合法，也就是不能存在 X
其次每个长度为 \(k\) 的子串的贡献就是其中 . 的个数
简单的维护一下滑动窗口也就够了
代码实现
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
using namespace std;
const int INF = 1001001001;
int solve(string s, int k) {
int n = s.size();
int res = INF;
{
int xs = 0, es = 0, len = 0;
rep(i, n) {
xs += s[i] == 'x';
es += s[i] == '.';
len++;
if (len > k) {
xs -= s[i-k] == 'x';
es -= s[i-k] == '.';
len--;
}
if (len == k) {
if (xs == 0) res = min(res, es);
}
}
}
return res;
}
int main() {
int h, w, k;
cin >> h >> w >> k;
vector<string> s(h);
rep(i, h) cin >> s[i];
int ans = INF;
rep(ri, 2) {
rep(i, h) ans = min(ans, solve(s[i], k));
{
vector<string> t(w, string(h, '.'));
rep(i, h)rep(j, w) t[j][i] = s[i][j];
swap(h, w);
s = t;
}
}
if (ans == INF) ans = -1;
cout << ans << '\n';
return 0;
}