https://codeforces.com/contest/1305

B. Kuroni and Simple Strings

 

题意：括号序列，每次操作可以删去一个任意层的正确的括号序列，要求最终不存在正确的括号对，求最少操作。

大胆猜测答案只有0或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
33
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 2e5 + 10;
const int INF = 0x3f3f3f3f;
int vis[N];
char s[N];
vector<int>vc;
int main() {
	scanf("%s", s);
	int n = strlen(s);
	for (int i = 0; s[i]; i++) {
		if (s[i] == ')')continue;
		for (int j = n-1; j>i; j--) {
			if (s[j] == ')'&&!vis[j]) {
				vis[j] = 1;
				vc.push_back(i);
				vc.push_back(j);
				break;
			}
		}
	}
	sort(vc.begin(), vc.end());
	if (vc.empty()) {
		puts("0");
		return 0;
	}
	puts("1");
	printf("%d\n", (int)vc.size());
	for (int p : vc)printf("%d ", p+1);
	puts("");
	return 0;
}

 

C. Kuroni and Impossible Calculation

 

题意：给定数组，求 ∏1≤i<j≤n∣ai−aj∣ mod m\prod_{1\le i<j\le n} |a_i - a_j| \bmod m，(1≤m≤1000)(1\le m \le 1000)

不能直接求，但发现m很小。

鸽巢原理

当数组中存在两个数对m同余时，结果一定为0，那么先判断是否存在同余，不存在的话，n一定小于等于m，那再暴力算就好了。

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 = 2e5 + 10;
const int INF = 0x3f3f3f3f;
int n, m;
int a[N];
int vis[N];
vector<int>vc;
int main() {
	scanf("%d%d", &n, &m);
	bool flg = 0;
	for (int i = 0; i < n; i++) {
		scanf("%d", &a[i]);
		if (vis[a[i]%m])flg = 1;
		vis[a[i]%m] = 1;
		vc.push_back(a[i]);
	}
	if (flg) {
		puts("0");
		return 0;
	}
	ll ans = 1;
	n = (int)vc.size();
	for (int i = 0; i < n; i++) {
		for (int j = i + 1; j < n; j++) {
			ans = (ans*abs(vc[j] - vc[i])) % m;
		}
	}
	cout << ans << endl;
	return 0;
}

 

D. Kuroni and the Celebration

 

题意：交互题。给定一棵树，每次可以询问两个点的LCA，要确定树的根。

每次选两个叶子，问出LCA后把LCA到这两个叶子的方向的所有点都删掉。

不断重复，直到只剩一个点，就是根。

可以直接删掉是因为删掉的点不可能是根，否则LCA就不是现在的LCA了，画几个图就能猜到。

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
53
54
55
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 2e5 + 10;
const int INF = 0x3f3f3f3f;
int n;
int to[N], nx[N], st[N], tot, d[N];
inline void add(int u, int v) { to[++tot] = v, nx[tot] = st[u], st[u] = tot; }
void dfs2(int u, int _fa) {
	d[u] = -1;
	for (int i = st[u]; i; i = nx[i]) {
		if (to[i] == _fa || d[to[i]] == -1)continue;
		dfs2(to[i], u);
	}
}
bool dfs(int s, int t, int u, int _fa) {
	bool flg = 0;
	if (u == t)flg = 1;
	if (!flg) {
		for (int i = st[u]; i; i = nx[i]) {
			if (to[i] == _fa || d[to[i]] == -1)continue;
			if (dfs(s, t, to[i], u)) {
				flg = 1;
			}
		}
	}
	if (flg&&u != s)dfs2(u, _fa);
	return flg;
}
int main() {
	cin >> n;
	for (int i = 1; i < n; i++) {
		int u, v;
		scanf("%d%d", &u, &v);
		add(u, v); d[u]++;
		add(v, u); d[v]++;
	}
	while (1) {
		int u = -1, v = -1, lca;
		for (int i = 1; i <= n; i++)if (d[i] == 1) { u = i; break; }
		for (int i = n; i >= 1; i--)if (d[i] == 1) { v = i; break; }
		if (u == -1) {
			for (int i = 1; i <= n; i++)if (d[i] == 0) {
				cout << "! " << i << endl;
				return 0;
			}
		}
		cout << "? " << u << ' ' << v << endl;
		cin >> lca;
		dfs(lca, u, lca, 0);
		dfs(lca, v, lca, 0);
		d[lca] -= 2; d[lca] += (u == lca || v == lca);
	}
	return 0;
}

 

E. Kuroni and the Score Distribution

 

题意：要求构造一个长度为 nn 的严格递增序列，且满足 1≤i<j<k≤n1 \leq i < j < k \leq n，ai+aj=aka_i + a_j = a_k 的 (i,j,k)(i, j, k) 个数恰好为 mm 。

首先猜测 1,2,3,⋯ ,n1,2,3,\cdots ,n 的序列是 (i,j,k)(i,j,k) 最多的，并验证。

然后想到先找到一个大于m的以上序列，再删数，使得结果为m，如果长度不够，再加上几个绝对不满足 (i,j,k)(i,j,k) 的数来凑数。

打表发现n个数的连续数列删掉一个数，减少的 (i,j,k)(i,j,k) 对数恰好是连续的，且刚好接上n-1。那么以上的方法就是可行的了。

还要考虑用来凑数的数，我是从最大的倒着取等差数列，间隔是之前的最大的数+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
33
34
35
36
37
38
39
40
41
42
43
44
45
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 2e5 + 10;
const int INF = 0x3f3f3f3f;
int n, m;
ll p[N];
void pre() {
	for (int n = 2; n <= 5001; n++) {
		for (int i = 1; i + i + 1 <= n; i++)p[n] += n - 2 * i;
	}
}
int cal(int k,int n) {
	int ans = (k - 1) / 2 + max(n - 2 * k, 0) + min(n - k, k - 1);
	return ans;
}
int ans[N];
int main() {
	pre();
	cin >> n >> m;
	if (m >= p[n]) {
		if (m > p[n])puts("-1");
		else for (int i = 1; i <= n; i++)printf("%d%s", i, i == n ? "\n" : " ");
	}
	else {
		int k = lower_bound(p + 1, p + n + 1, m) - p;
		if (p[k] != m) {
			int t;
			for (t = 1; t <= k && cal(t, k + 1) != p[k + 1] - m; t++);
			for (int i = 1, cnt = 0; i <= k + 1; i++)if (i != t)ans[++cnt] = i;
		}
		else for (int i = 1; i <= k; i++)ans[i] = i;
		int t = 1000000000;
		for (int i = n; i > k; i--) {
			ans[i] = t;
			t -= (ans[k] + 1);
			if (i<n&&ans[i] + ans[i + 1] <= 1e9) {
				puts("-1");
				return 0;
			}
		}
		for (int i = 1; i <= n; i++)printf("%d%s", ans[i], i == n ? "\n" : " ");
	}
	return 0;
}

 

F. Kuroni and the Punishment

 

题意：给定一个正整数数列，每次操作选一个数+1或-1，且要保证操作后仍是正整数，最终要使所有数的gcd大于1，求最少操作。

如果gcd是2的话，只要使所有数都是偶数就好了，每个数最多被操作1次，那么操作数一定不会超过n。

假设如果时间够的话，可以枚举最终的gcd，然后每个数贪心地成为它的倍数。

但这里时间不够，那么就随机枚举，由于已经知道答案上限是n，那么操作次数大于1的位置个数一定小于等于 n/2n/2，那么对一个数+1或者-1，它就成为最终的数的几率是 1/21/2，那么最终的gcd是它+1或-1后的数的因数的几率就是 1/21/2，多随机几次，多找几个数，几率更大。

cf的rand()最大只到32767，这里n太大，不能用，要用mt19973.

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
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 2e5 + 10;
const int INF = 0x3f3f3f3f;
const int MX = 1e6;
int n;
ll a[N];
vector<ll>pr;
int vis[MX];
mt19937_64 mt(chrono::steady_clock::now().time_since_epoch().count());
void init() {
	for (int i = 2; i < MX; i++) {
		if (!vis[i]) {
			pr.push_back(1ll*i);
			for (int j = i; j < MX; j += i)vis[j] = 1;
		}
	}
}
set<ll>st;
void addPrime(ll x) {
	for (ll& v : pr) {
		if (x%v == 0) {
			st.insert(v);
			while (x%v == 0)x /= v;
		}
	}
	if (x > 1)st.insert(x);
}
ll solve(ll x) {
	ll res = 0;
	for (int i = 1; i <= n; i++)
		res += (a[i] < x ? x - a[i] : min(a[i] % x, x - a[i] % x));
	return res;
}
int main() {
	cin >> n;
	for (int i = 1; i <= n; i++)scanf("%lld", &a[i]);
	shuffle(a + 1, a + n + 1, mt);
	init();
	for (int i = 1; i <= min(50, n); i++) {
		addPrime(a[i]);
		addPrime(a[i] + 1);
		if (a[i] > 1)addPrime(a[i] - 1);
	}
	ll ans = n;
	for (ll v : st)ans = min(ans, solve(v));
	cout << ans << endl;
	return 0;
}