2022.7.26 模拟赛

T1 tree

  考试的时候傻了，直接跑两边 $dfs$ 数连通块，然后输出个数少的。其实很容易就被 $hack$ 掉，比如如果把一个连通块染色之后就可以同时染多个原图的块，就比如这个图：

  这个图里面先改最中间的那个点然后再改中间的一圈，只用改两次。但是数连通块答案就是 $4$。所以我们不能直接数。

  受这个 $hack$ 的启发，我们可以考虑选取一个点为根，然后每次都改根节点所在的连通块以此向下扩展。但是这样应该仍然不是最优的，因为如果扩展到某一层只有一个点的时候：

  我们就可以花一步先把这个白的染成黑的，这样就直接把上下两层合并到一起了（再扩展的时候就可以当作是一层直接一步改完），花一步做了我们刚才的做法两步才能做到的事。所以要想让我们刚才的做法是最优的，要对我们选的根有要求。

  我们通过自己手画一些图可以发现，只要我们选的点是树的直径的中心点（路径长为奇数）的时候就肯定不会出现这种一层只有一个的情况，因为我们把直径分成了两半，左右两部分来说直径肯定是对称的（已经把之前的连通块缩成一个点了），所以不会出现那种情况。于是我们直接输出路径长的一般（向下取整）就好了（也就是层数）。

  对于偶数的情况，我们会发现答案也是直径长度的一半，所以可以统一处理。

#include
using namespace std;
#define in read()
#define MAXN 200200
#define MAXM MAXN << 2

inline int read(){
	int x = 0; char c = getchar();
	while(c < '0' or c > '9') c = getchar();
	while('0' <= c and c <= '9'){
		x = x * 10 + c - '0'; c = getchar();
	}
	return x;
}

int n = 0, cnt = 0;
int f[MAXN] = { 0 };
int b[MAXN] = { 0 };
int fa[MAXN] = { 0 };
struct Tree{
	int tot;
	int first[MAXN];
	int   nxt[MAXM];
	int    to[MAXM];
	int color[MAXN];
	inline void add(int x, int y){
		nxt[++tot] = first[x];
		first[x] = tot; to[tot] = y;
	}
}T1, T2;

int find(int x){
	if(x == fa[x]) return x;
	return fa[x] = find(fa[x]);
}

void merge(int x, int y){
	int fax = find(x), fay = find(y);
	fa[fax] = fay; 
}

int ans = 0, p = 1;
int dep[MAXN] = { 0 };
void dfs(int x, int fa){
	dep[x] = dep[fa] + 1;
	if(dep[x] > ans) ans = dep[x], p = x;
	for(int e = T2.first[x]; e; e = T2.nxt[e]){
		int y = T2.to[e];
		if(y == fa) continue;
		dfs(y, x);
	}
} 

int main(){
	n = in; T1.tot = 1;
	for(int i = 1; i <= n; i++) T1.color[i] = in, fa[i] = i;
	for(int i = 1; i < n; i++){
		int x = in, y = in;
		if(T1.color[x] == T1.color[y]) merge(x, y);
		T1.add(x, y), T1.add(y, x);
	}
	for(int i = 1; i <= n; i++){
		int x = find(i);
		if(!f[x]) b[x] = ++cnt, b[i] = cnt, f[x] = 1;
		else b[i] = b[x];
	}
	for(int i = 1; i <= T1.tot; i++){
		int x = T1.to[i], y = T1.to[i ^ 1];
		if(b[x] != b[y]) T2.add(b[x], b[y]);
	}
	dfs(1, 0);
	memset(dep, 0, sizeof dep), ans = 0;
	dfs(p, 0);
 	cout << (ans >> 1) << '\n';
	return 0;
} 
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

T2 multisets

  $wss$ 大佬的做法比 $TJ$ 时间复杂度还低 Orz orz orz orz。

  我们考虑从小到大枚举值域，然后从大到小枚举这个数字有多少个。这样我们枚举出来满足这个条件的集合显然是依次递增的。于是我们计算考虑包含 $k$ 个 $x$ 的集合一共有多少个，算出来就是这种集合对排名的贡献。

  我们假设一共有 $m$ 个 $x$，并且他们的下标为 $id{x}_1,id{x}_2,\cdots ,id{x}_m$，那么贡献就是：

$$\sum _{i=0}^{m-k+1}(id{x}_{i+1}-id{x}_i)(id{x}_{i+k}-id{x}_{i+k-1})$$

  但是这里用到的下标显然会超出 $m$，所以如果 $id{x}_i-id{x}_{i-1}<0$，我们就让它等于 $1$ 就好了。

#include
using namespace std;
#define in read()
#define MAXN 100100

inline int read(){
	int x = 0; char c = getchar();
	while(c < '0' or c > '9') c = getchar();
	while('0' <= c and c <= '9'){
		x = x * 10 + c - '0'; c = getchar();
	} 
	return x;
}

int s[MAXN] = { 0 };
int n = 0; int k = 0;
vector<int> pos[MAXN];                                                                        // pos[s[i]] : 为 s[i] 的下标集
int have[MAXN] = { 0 };                                                                       // have[s[i]] : s[i] 
int ans[MAXN] = { 0 };                                                                        // ans[i] : i 在答案中的个数
struct Tnode{
	int ll, lr;
	int rl, rr;
	Tnode() {}
	Tnode(int a, int b, int c, int d) { ll = a, lr = b, rl = c, rr = d; }
	bool operator < (const Tnode &rhs) const { return ll < rhs.ll; }
}; set<Tnode> st, temp;                                                                       // 答案集合

int query(int p, int num){                                                                    // 询问 st 里有多少个集合满足有 num 个 p
	int l = 1, r = l + num - 1;
	int ll = 0, lr = 0, rl = 0, rr = 0;
	int ans = 0;
	set<Tnode>::iterator z;
	while(r + 1 < pos[p].size()){
		ll = pos[p][l - 1] + 1, lr = pos[p][l];
		rl = pos[p][r], rr = pos[p][r + 1] - 1;
		z = st.upper_bound(Tnode(lr, 0, 0, 0));
		while(z != st.begin()){
			z--;
			if((*z).lr < ll) break;
			int LL = max((*z).ll, ll), LR = min((*z).lr, lr);
			int RL = max((*z).rl, rl), RR = min((*z).rr, rr);
			if(LL <= LR and RL <= RR) ans += (LR - LL + 1) * (RR - RL + 1);
		}
		l++, r++;
	}
	return ans;
}

void getnum(int p){                                                                           // 确定答案集合中 p 有多少个
	ans[p] = have[p];
	while(ans[p]){
		int temp = query(p, ans[p]);
		if(temp >= k) return;
		ans[p]--, k -= temp;
	}
}

void merge(int p, int num){                                                                   // 从初始的答案集合中选出含有 num 个 p 的集合
	int l = 1, r = l + num - 1;
	int ll = 0, lr = 0, rl = 0, rr = 0;
	set<Tnode>::iterator z;
	while(r + 1 < pos[p].size()){
		ll = pos[p][l - 1] + 1, lr = pos[p][l];
		rl = pos[p][r], rr = pos[p][r + 1] - 1;
		z = st.upper_bound(Tnode(lr, 0, 0, 0));
		while(z != st.begin()){
			z--;
			if((*z).lr < ll) break;
			int LL = max((*z).ll, ll), LR = min((*z).lr, lr);                                 // 取交集
			int RL = max((*z).rl, rl), RR = min((*z).rr, rr);
			if(LL <= LR and RL <= RR) temp.insert(Tnode(LL, LR, RL, RR));
		}
		l++, r++;
	}
	st.clear(), z = temp.begin();
	while(z != temp.end()) st.insert(*z), z++;
	temp.clear();
}

int main(){
	n = in; k = in;
	for(int i = 1; i <= n; i++) pos[i].push_back(0);                                          // 等会儿方便查前驱后继
	for(int i = 1; i <= n; i++) s[i] = in, have[s[i]]++, pos[s[i]].push_back(i);
	st.insert(Tnode(1, n, 1, n));
	for(int i = 1; i <= n; i++) pos[i].push_back(n + 1);
	for(int i = 1; i <= n; i++)
		if(have[i]){
			getnum(i);
			merge(i, ans[i]);
		}
	for(int i = 1; i <= n; i++)
		for(int j = 1; j <= ans[i]; j++) cout << i << ' ';
	return 0;
} 
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
81
82
83
84
85
86
87
88
89
90
91
92
93
94

  这样的做法看上去非常暴力但实际上是很高效的，我们来分析一下复杂度。我们发现，调用 $getnum()$ 这个函数的次数就是 $s$ 中数的种数，而在每次 $getnum()$ 时调用的 $query()$ 的次数就是这种数的数量，所以总共调用 $query()$ 的次数也就是 $O(n)$ 的。

  在一次 $query()$ 种，对于每一个集合都会有一个 $O(\log n)$ 的查询，所以 $query()$ 的复杂度就是 $O(st.size()\times \log n)$。又因为这个题目描述中保证数据随机生成 （虽然题目描述中说这个对解题没用但是这里还是用到了 qwq)，所以我们可以知道在 $s$ 中，一个数 $s_i$ 出现的期望次数就是 $1$。而每次我们会增加集合个数的情况也只有某个数字把 $s$ 分成若干部分，所以 $st.size()$ 会一直维持在常数范围内，所以 $query()$ 的复杂度可以看成是 $O(\log n)$ 的。所以总的复杂度就是 $O(n\log n)$ 的了 比 TJ 的 O(nlog^2 n) 还要优秀。

T3 maximize

  我们考虑 $a_i$ 对答案长生贡献的条件，我们可以发现每删去一个数，就相当于把这个数右边的所有数往前挪一格。很显然如果删过后的数组中满足 $a_i=i$ 那么就说明 $a_i$ 会对答案有贡献，但是这可能是往左挪过之后的结果，所以要满足 $a_i\ge i$ 才有可能对答案有贡献。

  并且如果要产生贡献，我们要在前 $i$ 个数中删掉 $i-a_i$ 个数才能让 $a_i$ 最后落到下标为 $a_i$ 的地方。题目中又要求最多删 $k$ 个数，所以又要满足 $i-a_i\le k$。

  同理，如果 $a_i>n-k$ 那么就它的数值就已经不属于删 $k$ 个过后 $[1,n-k]$ 下标的这个范围了，所以不可能产生贡献，所以要满足 $a_i\le n-k$。

  所以现在我们得到三个条件：

a i ≥ i a i ≥ i − k a i ≤ n − k

ai​≥ai​≥ai​≤​ii−kn−k​

  我们考虑一个 $j>i$ 并且 $j$ 也能产生贡献需要们组什么条件。他们两个要回到自己的位置上分别需要删 $a_i-i$ 个数和 $a_j-j$ 个数。又因为 $j>i$，所以$j$ 之前删的数大于等于 $i$ 的。就是说：

$$a_i-i\le a_j-j$$

  于是：

i < j a i < a j a i − i ≤ a j − j

i<ai​<ai​−i≤​jaj​aj​−j​

  我们发现这三个条件是可以互相推到的（知二推一），所以我们选出两个：

a i < a j a i − i ≤ a j − j

ai​<ai​−i≤​aj​aj​−j​

  这就显然是一个二维偏序了（就相当于最长上升子序列）。

  现在来解决一下这个做法的正确性问题，对于 $i<j$ 显然满足：

$$(a_j-j)-(a_i-i)\le j-i$$

  我们还要满足删去 $j$ 后删除的数大于 $k$：

$$(a_i-j)-(n-j)\ge k$$

  这个显然成立，所以这样构造出来的数列是没有问题的。

#include
using namespace std;
#define in read()
#define MAXN 500500

inline int read(){
	int x = 0; char c = getchar();
	while(c < '0' or c > '9') c = getchar();
	while('0' <= c and c <= '9'){
		x = x * 10 + c - '0'; c = getchar();
	}
	return x;
}

int n = 0; int k = 0;
int mx = 0; int cnt = 0;
int c[MAXN << 2] = { 0 };
struct Tnode{
	int idx, val;
	bool operator < (const Tnode &rhs) const {
		if(idx - val == rhs.idx - rhs.val)
			return val < rhs.val;
		return idx - val < rhs.idx - rhs.val;
	}
}a[MAXN];

inline int lowbit(int x) { return x & -x; }
void add(int x, int y) { for(; x <= mx; x += lowbit(x)) c[x] = max(c[x], y); }
int query(int x){
	int ans = 0;
	for(; x; x -= lowbit(x)) ans = max(ans, c[x]);
	return ans;
}

int main(){
	n = in; k = in;
	for(int i = 1; i <= n; i++){
		int w = in;
		if(w >= i - k and w <= n - k and w <= i)
			a[++cnt] = (Tnode){ i, w }, mx = max(mx, w);
	} sort(a + 1, a + cnt + 1);
	int ans = 0;
	for(int i = 1; i <= cnt; i++){
		int temp = query(a[i].val - 1) + 1;
		if(n - a[i].val >= k) ans = max(ans, temp);
		add(a[i].val, temp);
	}
	cout << ans << '\n';
	return 0;
} 
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

T4 journey

  $20pts$ 很简答，就是枚举 $x,y$，注意到贡献只可能在 $lca$ 处，所以直接计算即可，时间复杂度：$O(n^2\log n)$。

#include
using namespace std;
#define in read()
#define MAXN 100100
#define MAXM MAXN << 2

inline int read(){
	int x = 0; char c = getchar();
	while(c < '0' or c > '9') c = getchar();
	while('0' <= c and c <= '9'){
		x = x * 10 + c - '0'; c = getchar();
	}
	return x;
}

int n = 0;
int tot = 0;
int first[MAXN] = { 0 };
int   nxt[MAXM] = { 0 };
int    to[MAXM] = { 0 };
int   ans[MAXN] = { 0 };
int   can[MAXN] = { 0 };
inline void add(int x, int y){
	nxt[++tot] = first[x];
	first[x] = tot; to[tot] = y;
}

int dep[MAXN] = { 0 };
int val[MAXN] = { 0 };
int f[MAXN][50] = { 0 };
void prework(int x, int fa){
	dep[x] = dep[fa] + 1, val[x] += val[fa];
	for(int i = 0; i <= 30; i++) f[x][i + 1] = f[f[x][i]][i];
	for(int e = first[x]; e; e = nxt[e]){
		int y = to[e];
		if(y == fa) continue;
		f[y][0] = x; prework(y, x);
	}
}

int Lca(int x, int y){
	if(dep[x] < dep[y]) swap(x, y);
	for(int i = 30; i >= 0; i--){
		if(dep[f[x][i]] >= dep[y]) x = f[x][i];
		if(x == y) return x;
	}
	for(int i = 30; i >= 0; i--)
		if(f[x][i] != f[y][i])
			x = f[x][i], y = f[y][i];
	return f[x][0]; 
}

int main(){
//	freopen("a.in", "r", stdin); 
	n = in;
	for(int i = 1; i < n; i++){
		int y = in; add(i + 1, y), add(y, i + 1); }
	for(int i = 1; i <= n; i++) val[i] = in;
	prework(1, 0);
	for(int x = 1; x <= n; x++)
		for(int y = 1; y <= n; y++){
			if(x == y) continue;
			int lca = Lca(x, y);
			if(x == lca or y == lca) continue;
			int p = val[x] - val[f[lca][0]];
			int q = val[y] - val[f[lca][0]];
			ans[lca] = max(ans[lca], p ^ q), can[lca] = 1;
		}
	for(int i = 1; i <= n; i++)
		if(can[i]) cout << ans[i] << ' ';
		else cout << -1 << ' ';
	puts("");
	return 0;
}
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

  第三个点就是一个菊花图，很容易发现只有根节点有答案，这样问题就变成了在 $n-1$ 个数中选出两个数使得他们的异或值最大，非常简单的 $trie$ 树板子题。这样就能拿到 $30pts$ 啦。

#include
using namespace std;
#define in read()
#define MAXN 100100
#define MAXM MAXN << 2

inline int read(){
	int x = 0; char c = getchar();
	while(c < '0' or c > '9') c = getchar();
	while('0' <= c and c <= '9'){
		x = x * 10 + c - '0'; c = getchar();
	}
	return x;
}

int n = 0;
bool f1 = 1;
int tot = 0;
int first[MAXN] = { 0 };
int   nxt[MAXM] = { 0 };
int    to[MAXM] = { 0 };
int   ans[MAXN] = { 0 };
int   can[MAXN] = { 0 };
inline void add(int x, int y){
	nxt[++tot] = first[x];
	first[x] = tot; to[tot] = y;
}

int dep[MAXN] = { 0 };
int val[MAXN] = { 0 };
int f[MAXN][50] = { 0 };
void prework(int x, int fa){
	dep[x] = dep[fa] + 1, val[x] += val[fa];
	for(int i = 0; i <= 30; i++) f[x][i + 1] = f[f[x][i]][i];
	for(int e = first[x]; e; e = nxt[e]){
		int y = to[e];
		if(y == fa) continue;
		f[y][0] = x; prework(y, x);
	}
}

int Lca(int x, int y){
	if(dep[x] < dep[y]) swap(x, y);
	for(int i = 30; i >= 0; i--){
		if(dep[f[x][i]] >= dep[y]) x = f[x][i];
		if(x == y) return x;
	}
	for(int i = 30; i >= 0; i--)
		if(f[x][i] != f[y][i])
			x = f[x][i], y = f[y][i];
	return f[x][0]; 
}

int cnt = 0;
int trie[MAXN << 2][2] = { 0 };

void add(int x){
	int p = 0;
	for(int i = 20; i >= 0; i--){
		int t = (x >> i) & 1;
		if(!trie[p][t])
			trie[p][t] = ++cnt;
		p = trie[p][t];
	}
}

int query(int x){
	int p = 0, ans = 0;
	for(int i = 20; i >= 0; i--){
		int t = (x >> i) & 1;
		if(trie[p][t ^ 1])
			p = trie[p][t ^ 1], ans += (1 << i);
		else p = trie[p][t];
	}
	return ans;
}

int main(){
//	freopen("a.in", "r", stdin); 
	n = in;
	for(int i = 1; i < n; i++){
		int y = in;
		if(y != 1) f1 = 0;
		add(i + 1, y), add(y, i + 1);
	}
	for(int i = 1; i <= n; i++) val[i] = in;
	if(f1){                                                    // ?栈?图 trie ???? 
		for(int i = 2; i <= n; i++) add(val[i] + val[1]);
		for(int i = 2; i <= n; i++) ans[1] = max(ans[1], query(val[i] + val[1]));
		cout << ans[1] << ' ';
		for(int i = 1; i < n; i++) cout << -1 << ' '; puts("");
	}
	else{
		prework(1, 0);
		for(int x = 1; x <= n; x++)
			for(int y = 1; y <= n; y++){
				if(x == y) continue;
				int lca = Lca(x, y);
				if(x == lca or y == lca) continue;
				int p = val[x] - val[f[lca][0]];
				int q = val[y] - val[f[lca][0]];
				ans[lca] = max(ans[lca], p ^ q), can[lca] = 1;
			}
		for(int i = 1; i <= n; i++)
			if(can[i]) cout << ans[i] << ' ';
			else cout << -1 << ' ';
		puts("");
	}
	return 0;
}
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
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110

  第四个点也就是一个延长了的菊花图，我们发现贡献必须在两个不同的子树，所以我们考虑更换加入的方式。具体来说，对于一棵子树