https://codeforces.com/contest/1243

B2. Character Swap (Hard Version)

 

题意：给定两个字符串s，t，每次可以在两个字符串中各选一个位置，再字符串间交换，最终要使两个字符串相同。操作数不要求最少，但要小于2n。

贪心构造

挨个遍历过去，如果两个字符串当前位置i不同，则先在s串中找到和s[i]相同的j，交换s[j],t[i]；若找不到，则在t中找和s[i]相同的j，先交换s[j],t[j]，再交换s[j],t[i]。

在每个位置最多交换2次，总共不超过2n。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 2e5 + 10;
const int INF = 0x3f3f3f3f;
const ll mod = 1e9 + 7;
const ll inf = 1e18;
int T;
int n;
char s[N], t[N];
int a[N], c[N];
typedef pair<int, int>pii;
vector<pii>vc;
int main() {
	cin >> T;
	while (T--) {
		scanf("%d", &n);
		scanf("%s", s);
		scanf("%s", t);
		fill(c, c + 26, 0);
		for (int i = 0; i < n; i++)c[s[i] - 'a']++, c[t[i] - 'a']++;
		for (int i = 0; i < 26; i++)if (c[i] & 1) n = 0;
		if (!n)puts("No");
		else {
			vc.clear();
			for (int i = 0; i < n; i++) {
				if (s[i] == t[i])continue;
				bool flg = 0;
				for (int j = i + 1; j < n; j++)if (s[i] == s[j]) {
					vc.push_back(pii(j, i));
					swap(t[i], s[j]);
					flg = 1;
					break;
				}
				if (!flg) {
					for (int j = i + 1; j < n; j++)if (s[i] == t[j]) {
						vc.push_back(pii(j, j));
						swap(s[j], t[j]);
						vc.push_back(pii(j, i));
						swap(s[j], t[i]);
						break;
					}
				}
			}
			puts("Yes"); printf("%d\n", (int)vc.size());
			for (pii p : vc) {
				printf("%d %d\n", p.first+1, p.second+1);
			}
		}
	}
	return 0;
}

 

C. Tile Painting

 

题意：给定n，要求构造出一个长度为n的数列，每个位置和与他间隔为n的因数的位置上的数必须相同，问最多有多少个不同的数。

画几个图直接猜结论，如果n只含有一个质因数，则答案就为这个质因数，否则就是1.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 1e6 + 10;
const int INF = 0x3f3f3f3f;
ll n;
int vis[N];
vector<int>pr;
void init(int n) {
	for (int i = 2; i <= n; i++) {
		if (vis[i])continue;
		pr.push_back(i);
		for (int j = i; j <= n; j += i)vis[j] = 1;
	}
}
vector<ll>ans;
int main() {
	cin >> n;
	if (n == 1) { puts("1"); return 0; }
	init(1000000);
	int t = (int)pr.size(), cnt = 0;
	for (int i = 0; i < t&&pr[i] <= n; i++) {
		if (n%pr[i] == 0) {
			cnt++; ans.push_back(pr[i]);
			while (n%pr[i] == 0)n /= pr[i];
		}
	}
	if (n != 1)cnt++, ans.push_back(n);
	if (cnt > 1)puts("1");
	else printf("%lld\n", ans[0]);
	return 0;
}