Harbour.Space Scholarship Contest 2021-2022 (Div. 1 + Div. 2)
A. Digits Sum
题意
记 为 的十进制数位和。给定 ，问 里有多少个数满足 。
思路
末位不是 9，加一以后数位和也只会加一。末位是 9 就会进位，至少少掉一个 9，数位和一定变小。
所以数一下 9、19、29 这些数就行。先取 n / 10，末位正好是 9 时再加一个。
代码
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e6 + 17;
int T, n, m, ans;
int a[maxn];
string str;
int main() {
cin >> T;
while(T--) {
cin >> n;
ans = n / 10;
if(n % 10 == 9) ans++;
cout << ans << endl;
}
return 0;
}B. Reverse String
题意
在字符串 中任选一个位置出发，先向右走若干步，再向左走若干步，两个阶段都可以不走。每到一个位置就记下字符，问能不能得到 。
思路
枚举 在哪里掉头，再枚举在 中从哪里出发。掉头前是一段向右的子串；掉头后把目标串反过来，就也能用子串比较了。
注意掉头的那个字符只记一次。右半段从它左边开始取，最左端不能越过 0。这里直接用 substr 比较，数据范围够用。
代码
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e6 + 17;
int T, n, m, ans;
int a[maxn];
string s, t;
int main() {
cin >> T;
while(T--) {
cin >> s >> t;
int flg = 0;
int sl = s.length();
int len = t.length();
for(int i = 0; i < len; i++) {
string l = t.substr(0, i + 1);
string r = t.substr(i + 1, len - i - 1);
reverse(r.begin(), r.end());
int lenl = l.length(), lenr = r.length();
for(int j = 0; j + i < sl; j++) {
if(l == s.substr(j, i + 1) && j + i - lenr >= 0) {
if(r == s.substr(j + i - lenr, lenr)) flg = 1;
}
}
}
cout << (flg ? "YES" : "NO") << endl;
}
return 0;
}C. Penalty
题意
两队交替罚点球，各有五次机会。已知十脚球的结果，其中 ? 可以进也可以不进；一方已经不可能追平时就结束，问最早第几脚能结束。
思路
想让比赛早点结束，就尽量拉开比分。分别让第一队的 ? 全进、第二队全不进，再反过来算一次，取较早的结果。
每踢一脚就更新得分和剩余次数。如果领先的分数已经超过对面剩下的机会，就可以停了。
代码
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e6 + 17;
int T, n, m, ans;
int a[maxn], r[2], s[2];
string str;
int main() {
cin >> T;
while(T--) {
ans = 10;
cin >> str;
for(int i = 1; i <= 10; i++) {
if(str[i - 1] == '1') a[i] = 1;
else if(str[i - 1] == '0') a[i] = 0;
else a[i] = -1;
}
r[1] = 5, r[0] = 5, s[1] = 0, s[0] = 0;
for(int i = 1; i <= 10; i++) {
if(a[i] == 1) {
s[i & 1]++, r[i & 1]--;
}
else if(a[i] == 0) {
r[i & 1]--;
}
else{
if(i & 1) {
s[i & 1]++, r[i & 1]--;
}
else{
r[i & 1]--;
}
}
// cout << s[1] << r[1] << s[0] << r[0] << endl;
if(s[1] - s[0] > r[0] || s[0] - s[1] > r[1]) {
ans = min(ans, i);
break;
}
}
r[1] = 5, r[0] = 5, s[1] = 0, s[0] = 0;
for(int i = 1; i <= 10; i++) {
if(a[i] == 1) {
s[i & 1]++, r[i & 1]--;
}
else if(a[i] == 0) {
r[i & 1]--;
}
else{
if(i & 1) {
r[i & 1]--;
}
else{
s[i & 1]++, r[i & 1]--;
}
}
// cout << s[1] << r[1] << s[0] << r[0] << endl;
if(s[1] - s[0] > r[0] || s[0] - s[1] > r[1]) {
ans = min(ans, i);
break;
}
}
cout << ans << endl;
}
return 0;
}D. Backspace
题意
按顺序输入字符串 ，每个字符都可以改成按一次退格。退格会删掉当前最后一个字符，空串时没有效果，问最后能不能得到 。
思路
保留下来的字符之间，没用的字符必须两两消掉，所以跳过时一次跳两个。第一个保留字符前面可以全部按退格，奇偶两种起点都试一下。
从左往右匹配，当前字符相同就保留，否则跳两个。最后还要看剩下的后缀是不是偶数个，不能只匹配完 就算成功。读字符前先检查边界。
代码
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int T, n, m, ans;
string s, t;
int main() {
cin >> T;
while(T--) {
int flg = 0;
cin >> s >> t;
int ls = s.length(), lt = t.length();
int ps = 0, pt = 0;
while(ps < ls && s[ps] != t[0]) ps += 2;
for(; ps < ls && pt < lt; ) {
if(s[ps] == t[pt]) ps++, pt++;
else ps += 2;
}
if(pt == lt && (ls - ps) % 2 == 0) flg = 1;
ps = 1, pt = 0;
while(ps < ls && s[ps] != t[0]) ps += 2;
for(; ps < ls && pt < lt; ) {
if(s[ps] == t[pt]) ps++, pt++;
else ps += 2;
}
if(pt == lt && (ls - ps) % 2 == 0) flg = 1;
cout << (flg ? "YES" : "NO") << endl;
}
return 0;
}E. Permutation Shift
题意
把 先循环右移 位，再交换至多 对元素，得到了给定排列，其中 。求所有可能的 。
思路
一次交换最多动两个位置，所以平移后至少有 个位置原本就是对的。位置 上的数是 ，它对应的平移量就是 ，先按这个统计候选。
再对每个候选真正算交换次数。把当前值和它应该去的位置连起来，用并查集数环；一个长度为 的环需要 次交换，总共就是 。
所有平移量的计数加起来是 ，每个候选至少占 ，所以最多只剩三个候选，不会每种平移都扫一遍。
代码
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 3e5 + 17;
int T, n, m, ans;
vector<int> v;
int a[maxn], cnt[maxn], fa[maxn];
int getf(int x) {
return fa[x] == x ? x : (fa[x] = getf(fa[x]));
}
void merge(int x, int y) {
int fx = getf(x), fy = getf(y);
if(fx == fy) return;
fa[fy] = fx;
return;
}
int main() {
cin >> T;
while(T--) {
ans = 0;
v.clear();
cin >> n >> m;
for(int i = 0; i <= n; i++) cnt[i] = 0;
for(int i = 1; i <= n; i++) cin >> a[i];
for(int i = 1; i <= n; i++) {
cnt[(i - a[i] + n) % n]++;
}
for(int k = 0; k < n; k++) if(cnt[k] >= n - 2 * m) {
int tmp = 0;
for(int i = 1; i <= n; i++) fa[i] = i;
for(int i = 1; i <= n; i++) {
int to = ((i - k + n) % n);
if(!to) to = n;
// if(to == a[i]) fa[to] = 0;
merge(a[i], to);
}
// for(int i = 1; i <= n; i++) cout << getf(i) << " \n"[i == n];
for(int i = 1; i <= n; i++) {
if(getf(i) == i) tmp++;
}
if(n - tmp <= m) ans++, v.push_back(k);
}
cout << ans;
int len = v.size();
cout << (len ? " " : "\n");
for(int i = 0; i < len; i++) cout << v[i] << " \n"[i == len - 1];
}
return 0;
}