CF686_Div3题解

Posted on In Comments: Views:

CF686_Div3题解

D

image-20201127165044327

解题思路

首先我们将$n$进行素因子分解，得到如下的表达式:

$$n = p_1^{\alpha_1}p_2^{\alpha_2}…p_l^{\alpha_l}$$

假设我们得到的$k$个数进行素因子分解，得到的结果是:

$$a_i = p_1^{b^i_1}p_2^{b^i_2}…p_l^{b^i_l}$$

由于后面的数都可以整数前面的数，所以有

$$b^i_{j} \le b_{j}^{i+1} \quad \forall i, j$$

$$\sum_{i=1}^{k}b^i_{j} = \alpha_j$$

所以可以看到，$K$的最大值取决于$\alpha$的最大值。

在构造的时候，我们令前$k - 1$个数都是指数最大的那个素因子，最后一个用整个除以前面的即可。

时间复杂度$O(\sqrt{n})$

C++代码

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
#include <iostream>
using namespace std;


int main() {
	
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	
	int t;
	cin >> t;
	while (t --) {
		long long n;
		cin >> n;
		long long n_bak = n;
		long long max_cnt = 0, max_prim = -1;
		for (long long i = 2; i * i <= n && n > 1; i++) {  // 进行素因子分解
			if ((n % i) == 0) { // 找到一个素因子，全部除尽
				long long cnt = 0;
				while ((n % i) == 0) {
					cnt ++;
					n /= i;
				}
				if (cnt > max_cnt) {  // 记录指数最大的素因子
					max_cnt = cnt;
					max_prim = i;
				}
			}
		}
		if (n) {
			if (max_cnt < 1) {
				max_cnt = 1;
				max_prim = n;
			}
		}
		cout << max_cnt << '\n';
		for (int i = 1; i < max_cnt; i ++) { 
			cout << max_prim << ' ';
			n_bak /= max_prim;
		}
		cout << n_bak << '\n';
	}
	return 0;
	
}

E

image-20201127165127935

解题思路

$n$个节点，$n$条边的连通图，是在一棵树的基础上增加一条边得到的结果。

得到的图也可以看做是一个环，然后换的每个节点上面挂了一棵树，就像下面的图一样。

image-20201127171129988

然后我们考虑每棵树内部节点的贡献。

对于蓝色所标的子树中的节点而言，其内部两个点之间只有一条路径，所以答案是$\frac{cnt_i * (cnt_i - 1)}{2}$

从蓝色节点到任何一个其他节点，都存在两条不同的路径，所以路径条数为$2 * cnt_i * (n - cnt_i)$

但是在统计每个子树的时候，第二种路径会被统计两次，所以最终的答案就是

$$\sum_{i} ( \frac{cnt_i * (cnt_i - 1)}{2} + cnt_i * (n - cnt_i) )$$

为了统计每棵子树的大小，可以使用tarjan算法。这里可以用一个简单的方法，模仿拓扑排序的思想。从叶子节点向里面扩展。具体方法参考下面的代码。

C++代码

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
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
#include <iostream>
using namespace std;

const int N = 2e5 + 5, M = N * 2;
int h[N], e[M], ne[M], idx;
int deg[N];
int stk[N], top = 0;
int cnt[N];
bool vis[N];

void add(int a, int b) {
	e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}

void solve() {
	
	int n;
	cin >> n;
	for (int i = 1; i <= n; i ++) {
		h[i] = -1;
		deg[i] = 0;
		cnt[i] = 1;
		vis[i] = false;
	}
	idx = 0;
	for (int i = 0; i < n; i ++) {
		int a, b;
		cin >> a >> b;
		add(a, b);
		add(b, a);
		deg[a] ++;
		deg[b] ++;
	}
	
	top = 0;
	for (int i = 1; i <= n; i ++) {
		if (deg[i] == 1) stk[++top] = i, vis[i] = true;
	}
	while (top) {
		int node = stk[top --];
		for (int i = h[node]; ~i; i = ne[i]) {
			int t = e[i];
			if (vis[t]) continue;
			deg[t] --;
			cnt[t] += cnt[node];
			if (deg[t] == 1) {
				stk[++ top] = t;
				vis[t] = true;
			}
		}
	}
	long long ans = 0;
	for (int i = 1; i <= n; i ++) {
		if (vis[i]) continue;
		ans += (long long)cnt[i] * (cnt[i] - 1) / 2 + (long long)cnt[i] * (n - cnt[i]);
		// cout << i << ' ' << cnt[i] << ' ' << ans << '\n';
	}
	
	cout << ans << '\n';
	return ;
}


int main() {
	
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	
	int t;
	cin >> t;
	while (t --) {
		solve();
	}
	
	return 0;
	
}

F

image-20201127165201241

解题思路

先使用ST表处理，便于在$O(1)$的时间内得到任意一个区间的最大最小值。然后首先枚举第一个分界点。

利用单调性，两次二分找到使得第二个区间满足的左右边界。在利用单调性二分找到第三个区间满足的点即可。

时间复杂度$O(n \log n)$

C++代码

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
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
#include <iostream>
#include <cmath>

using namespace std;

const int N = 2e5 + 5;

int st1[N][20], st2[N][20];
int q[N];

void build(int n) {
	for (int i = 1; i <= n; i ++) st1[i][0] = st2[i][0] =  q[i];
	for (int j = 1;  (1 << j) <= n; j ++) {
		for (int i = 1; i + (1 << j) - 1 <= n; i ++) {
			st1[i][j] = min(st1[i][j - 1], st1[i + (1 << (j - 1))][j - 1]);
			st2[i][j] = max(st2[i][j - 1], st2[i + (1 << (j - 1))][j - 1]);
		}
	}
}

int query_max(int l, int r) {
	int j = log(r - l + 1) / log(2);
	return max(st2[l][j], st2[r - (1 << j) + 1][j]);
}

int query_min(int l, int r) {
	int j = log(r - l + 1) / log(2);
	return min(st1[l][j], st1[r - (1 << j) + 1][j]);
}

void solve() {
	int n;
	cin >> n;
	for (int i = 1; i <= n; i ++) cin >> q[i];
	build(n);
	
	for (int i = 1; i <= n - 2; i ++) {
		int target = query_max(1, i);
		int l = i + 1, r = n - 1;
		while (l < r) {
			int mid = l + r >> 1;
			if (query_min(i + 1, mid) > target) l = mid + 1;
			else r = mid;
		}
		if (query_min(i + 1, l) != target) continue;
		int ll = l;
		l = i + 1, r = n - 1;
		while (l < r) {
			int mid = l + r + 1 >> 1;
			if (query_min(i + 1, mid) < target) r = mid - 1;
			else l = mid;
		}
		int rr = l;
		l = ll + 1, r = rr + 1;
		while (l < r) {
			int mid = l + r + 1 >> 1;
			if (query_max(mid, n) < target) r = mid -  1;
			else l = mid;
		}
		if (query_max(l, n) == target) {
			cout << "YES" << '\n';
			cout << i << ' ' << l - i - 1 << ' ' << n - l + 1 << '\n';
			return ;
		}
	}
	cout << "NO" << '\n';
	
}


int main() {
	
	int t;
	cin >> t;
	while (t --){
		solve();
	}
	return 0;
	
}