1.3 vp Educational Codeforces Round 139 (Rated for Div. 2)

A - Extremely Round

题意：给出n，找出从1到n中，只出现过一次非0数字的数
思路：一开始以为是暴力，wa了一发老老实实找规律。就是找最高位，最高位是几，就有几个，再加上，每多一位要加9个

void solve() {
	int n;
	cin >> n;
	int sum = 0, cnt = 0;
	
	while (n > 10) {
		cnt ++;
		n /= 10;
	}
	
	sum = n + cnt * 9;
	
	cout << sum << endl;
}

B - Notepad#

题意：你有两种操作，第一种是往字符串后面加入一个字符，第二种是加入一个前面输入过的子串。给出一个长度为n的字符串，问是否能通过少于n次操作变成这个字符串
思路：其实就是在字符串中找到两个相同的子串，最少长度为2。一开始以为是模拟，wa2了想了半天发现用map就可以轻松解决

void solve() {
	int n;
	cin >> n;
	string s;
	cin >> s;
	map<string , int> mp;
	for (int i = 0; i < n - 1; i ++) {
		string t = s.substr(i, 2);
		if (mp[t]) {
			if (i + 1 - mp[t] > 1) {
				cout << "YES" << endl;
				return ;
			}else continue;
		}else mp[t] = i + 1;
	}
	
	cout << "NO" << endl;
}

C - Hamiltonian Wall

题意:给出两行m列的字符矩阵。有W，B两种字符。问是否能用一笔将矩阵中的B全部画到
思路：模拟没模拟出来。看的dalao代码用的dp。即统计矩阵中B的个数，然后用动归推出到最后B的路径终点是否等于B的个数

int f[2][N];
 
//注意观察N的大小
void solve() {
	int n;
	cin >> n;
	string s[2];
	cin >> s[0] >> s[1];
	memset(f, 0, sizeof (f));
	int cnt = count(s[0].begin(), s[0].end(), 'B') + count(s[1].begin(), s[1].end(), 'B');
	for (int j = 0; j < n; j ++) {
		for (int i = 0; i < 2; i ++) {
			if (s[i][j] == 'W') continue;
			if (j == 0) f[i][j] = 1;
			else if (s[i][j - 1] == 'B') f[i][j] = f[i][j - 1] + 1;
		}
		
		if (s[0][j] == 'B' && s[1][j] == 'B') {
			int t = f[0][j];
			f[0][j] = max(f[0][j], f[1][j] + 1);
			f[1][j] = max(f[1][j], t + 1);
		}
		
		if (f[0][j] == cnt || f[1][j] == cnt) {
			cout << "YES" << endl;
			return ;
		}
	}
	
	cout << "NO" << endl;
}

D - Lucky Chains

题意：给出a,b。求满足gcd(a+x,b+x)=1的最大x
思路：由于gcd(a,b)=gcd(a,b-a)(b>a),故而所给等式可以转化为gcd(a+x,b-a)=1。找出b-a的质因数p，ans = x - x % p

const int N = 1e7 + 10, M = 5010, INF = 2e9, MOD = 1e9 + 7;
int p[N];
 
//注意观察N的大小
void solve() {
	int x, y;
	cin >> x >> y;
	if (y - x == 1) {
		cout << -1 << endl;
		return ;
	}
	
	int ans = 1e9, now = y - x;
	while (now != 1) {
		int tmp = p[now];
		ans = min(ans, (tmp - x % tmp) % tmp);
		now /= tmp;
	}
	
	cout << ans << endl;
}
 
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int t = 1;
	cin >> t;
	
	for (int i = 1; i <= N; i ++) p[i] = i;
	for (int i = 2; i <= N; i ++) {                    //找到最大质因数
		if (p[i] == i) {
			for (int j = 2 * i; j <= N; j += i) {
				p[j] = i;
			}
		}
	}
	
	while (t--) {
		solve();
	}
	
	return 0;
}

总结：思路还有局限性，对于显而易见的东西需要很长时间才能想到。dp，数论所掌握知识都很薄弱，应有待加强