Educational Codeforces Round 139 (A-C)

A

题意：有t组测试数据，每组测试数据输入一个整数n，输出一个整数，表示[1, n]范围内满足以下条件的x的个数。其中x满足条件"只有一个非0的位数(比如5000, 4, 200)"。

解法/思路：举个例子，若n为四位数，则必然有9个一位数，9个二位数，9个三位数满足条件，而满足条件的四位数就等于n的首位数的值。

代码：

#include <iostream>
using namespace std;
int main(void) {
	int t, n, ans = 0;
	cin >> t;
	while(t--) {
		cin >> n;
		while (n >= 10) {
			n /= 10;
			ans += 9;
		}
		ans += n;
		cout << ans << endl;
		ans = 0;
	}
	return 0;
}

B

题意：t组测试数据，每组测试数据输入共两行，第一行输入整数n，第二行输入长度为n的字符串。输出共一行，若该字符串能在操作次数小于n的情况下打出来，则输出"YES"，否则输出"NO"。

所谓"操作"有两种：
1.在字符串末端打出一个字符。
2.复制一段前面已经打出来的部分追加到字符串末端。

显然，只要字符串当中出现两个长度为2，完全相同且位置不重合(比如"hhh"中，前面的"hh"和后面的"hh"就是重合了)的子串，就可以断定为"YES"。

解法/思路：本人采用unordered_map(STL大法好( •̀ ω •́ )y)，记录所有上述子串及其出现的位置，竟然意外地AC了。

代码：

#include <iostream>
#include <string>
#include <unordered_map>
using namespace std;
int main(void) {
	int t, len, k = 0;
	string str, tmp;
	cin >> t;
	while (t--) {
		unordered_map<string, int> mp;
		cin >> len;
		cin >> str;
		for (k = 0; k < len - 1; ++k) {
			tmp = str.substr(k, 2);
			if (mp.find(tmp) != mp.end() && k - mp[tmp] > 1) {        // 如果该子串出现过且不"重合"
				cout << "YES" << endl;
				break;
			} else {
				mp.insert(make_pair(tmp, k));
			}
		}
		if (k == len - 1) {
			cout << "NO" << endl;
		}
	}
	return 0;
}

C

题意：有两排砖块，它们组成一个矩形，原本所有砖块都是白色，现在要求用一只刷子刷上黑色油漆，使得每一列至少有一块是黑的，刷子只能上下左右地移动，且已经刷过的地方就不能再经过了，现在有t组测试数据，每组测试数据输入共三行，第一行是一个整数n，下面两行是两个长度为n，仅由'W'和'B'组成的字符串('B'即表示"Black")，输出共1行，若能够刷成这两个字符串所表示的样子，输出"YES"，否则输出"NO"。

解法/思路：找规律。当两个靠的最近的'W'相差的列数为偶数时，如果它们在同一列；或者如果相差的列数为奇数，且不在同一列，则为"NO"。

代码：

#include <iostream>
#include <cstdio>
#include <string>
#include <algorithm>
using namespace std;
char r1[200001];
char r2[200001];
int x, y = 0, x2, y2 = 0;                    // x, y, x2, y2用于记录'W'出现的位置，每次遇到'W'时，更新y小的那组数据
int main(void) {
	int t, n, k;
	cin >> t;
	while (t--) {
		cin >> n;
		scanf("%s", r1 + 1);
		scanf("%s", r2 + 1);
		for (k = 1; k <= n; ++k) {
			if (r1[k] == 'W') {
				if (y < y2) {
					y = k;
					x = 1;
				} else {
					y2 = k;
					x2 = 1;
				}
			}
			if (r2[k] == 'W') {
				if (y < y2) {
					y = k;
					x = 2;
				} else {
					y2 = k;
					x2 = 2;
				}
			}
			if (y && y2) {
				if (x != x2 && ((abs(y2 - y)) % 2 != 0)) {
					cout << "NO" << endl;
					break;
				}
				if (x == x2 && ((abs(y2 - y)) % 2 == 0)) {
					cout << "NO" << endl;
					break;
				}
			}
		}
		if (k == n + 1) {
			cout << "YES" << endl;
		}
		y = 0;
		y2 = 0;
	}
	return 0;
}