Codeforces Round (2021-07-22)

Harbour.Space Scholarship Contest 2021-2022 (Div. 1 + Div. 2)

A. Digits Sum

题目链接

题意

记 $S(x)$ 为 $x$ 的十进制数位和。给定 $n$ ，问 $1\le x\le n$ 里有多少个数满足 $S(x+1)<S(x)$ 。

思路

末位不是 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

题目链接

题意

在字符串 $s$ 中任选一个位置出发，先向右走若干步，再向左走若干步，两个阶段都可以不走。每到一个位置就记下字符，问能不能得到 $t$ 。

思路

枚举 $t$ 在哪里掉头，再枚举在 $s$ 中从哪里出发。掉头前是一段向右的子串；掉头后把目标串反过来，就也能用子串比较了。

注意掉头的那个字符只记一次。右半段从它左边开始取，最左端不能越过 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

题目链接

题意

按顺序输入字符串 $s$ ，每个字符都可以改成按一次退格。退格会删掉当前最后一个字符，空串时没有效果，问最后能不能得到 $t$ 。

思路

保留下来的字符之间，没用的字符必须两两消掉，所以跳过时一次跳两个。第一个保留字符前面可以全部按退格，奇偶两种起点都试一下。

从左往右匹配，当前字符相同就保留，否则跳两个。最后还要看剩下的后缀是不是偶数个，不能只匹配完 $t$ 就算成功。读字符前先检查边界。

代码

#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

题目链接

题意

把 $1,2,\ldots,n$ 先循环右移 $k$ 位，再交换至多 $m$ 对元素，得到了给定排列，其中 $m\le n/3$ 。求所有可能的 $k$ 。

思路

一次交换最多动两个位置，所以平移后至少有 $n-2m$ 个位置原本就是对的。位置 $i$ 上的数是 $a_i$ ，它对应的平移量就是 $(i-a_i+n)\bmod n$ ，先按这个统计候选。

再对每个候选真正算交换次数。把当前值和它应该去的位置连起来，用并查集数环；一个长度为 $L$ 的环需要 $L-1$ 次交换，总共就是 $n-\text{环数}$ 。

所有平移量的计数加起来是 $n$ ，每个候选至少占 $n/3$ ，所以最多只剩三个候选，不会每种平移都扫一遍。

代码

#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;
}

A. Digits Sum

题意

思路

代码

B. Reverse String

题意

思路

代码

C. Penalty

题意

思路

代码

D. Backspace

题意

思路

代码

E. Permutation Shift

题意

思路

代码

랜덤 게시물