CS academy Round 29

Chong Wang Lv6
  2017-05-30 22:27:46 2017-05-30 22:27:46 Created   2026-10-09 08:58:54 2026-10-09 08:58:54 Updated

Finally I figured out the tree DP of E.

Title link

A.Missing Number

Find the smallest positive number that does not appear in the array. Simple questions are not clear.

B.Positive Xors

Given an array of numbers, find the largest subarray whose XOR is not 0.

Scan from front to back and scan from back to front.

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
int n;
int val[maxn];
int pre[maxn],suf[maxn];

void solve()
{
	sa(n);
	repp(i,1,n)
	{
		sa(val[i]);
	}
	int res=0;
	int cur=0;
	repp(i,1,n)
	{
		cur^=val[i];
		if(cur)res=max(res,i);
	}
	cur=0;
	for(int i=n;i>=1;i--)
	{
		cur^=val[i];
		if(cur)
		{
			res=max(res,n-i+1);
		}
	}
	cout<<res<<endl;
}

C.Equality

The meaning of the question is to give a set of numbers. There is an operation that can select two numbers $A[i]，A[j]$. For one of them $+1$ and the other $-1$, ask the minimum number of operations to make these numbers $Max-Min<=K$.

Violence. . . Record the maximum value and the number and position of the minimum value.

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
int n,k;
int val[maxn];
int hax[maxn];
void solve()
{
	sa(n),sa(k);
	int maxx=0,minn=1e5;
	repp(i,1,n)
	{
		sa(val[i]);
		hax[val[i]]++;
		minn=min(minn,val[i]);
		maxx=max(maxx,val[i]);
	}
	int cnt=0;
	while(true)
	{
		if(abs(maxx-minn)<=k)break;
		int num=min(hax[minn],hax[maxx]);
		cnt+=num;
		//DE(maxx)
		//DE(minn)
		hax[minn]-=num;
		hax[maxx]-=num;
		if(hax[minn]==0)
		{
			minn++;
			hax[minn]+=num;
		}
		else
		{
			hax[minn+1]+=num;
		}
		if(hax[maxx]==0)
		{
			maxx--;
			hax[maxx]+=num;
		}
		else
		{
			hax[maxx-1]+=num;
		}
	}
	cout<<cnt<<endl;
}

D.Odd Palindromes

A string is odd palindromic, which means that all its odd substrings are palindromes. Now given a string that can be modified $K$ times at most, ask what is the longest odd palindromic length that can be achieved.

I found that odd palindromic is ABABA… in this form.

Then modify ZZZPROTECT 11ZZZ times at most. You can record the values ​​of odd positions and even positions respectively, using double pointers. $O(n)$.

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
int k;
char val[maxn];
int num[2][30];

bool check()
{
	int sum1 = 0, sum2 = 0;
	int maxx1 = 0, maxx2 = 0;

	for (int i = 0; i<26; i++)
	{
		sum1 += num[0][i];
		maxx1 = max(maxx1, num[0][i]);
	}

	int sur = k - (sum1 - maxx1);


	for (int i = 0; i<26; i++)
	{
		sum2 += num[1][i];
		maxx2 = max(maxx2, num[1][i]);
	}
	sur = sur - (sum2 - maxx2);

	if (sur<0)return false;
	else return true;
}

void solve()
{
	sa(k);
	scanf("%s", val + 1);
	int len = strlen(val + 1);

	int en = 0;
	int res = 1;
	int flag = 0;
	for (int i = 1; i <= len; i++)
	{
		int flag = 0;
		while (true)
		{
			if (!check())
			{
				flag = 1;
				break;
			}
			if (en >= len)
			{
				flag = 2;
				break;
			}
			num[(en+1) & 1][val[en+1] - 'a']++;
			en++;
		}
		if (flag == 1)
			res = max(res, en - i);
		else
			res = max(res, en - i + 1);
		num[i&1][val[i] - 'a']--;
	}
	printf("%d\n", res);
}

E.Root Change

There is a tree with $N(N<10^5)$ nodes. Now the $i$th query is how many edges can be deleted without affecting the depth of the tree when the $i$th point becomes the root of the tree.

First, if the root node is determined, then the LCA chain from the root to the deepest leaf node needs to be maintained, and the depth of the tree and the number on the link node need to be recorded.

Now each node is required to be the root. Considering transfer, a node can know the chain of its down through dfs, and the up value can be obtained by recording the suffix and prefix values of its parent node on the child node.

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
int n;
int vis[maxn];
int ans[maxn];
vector<int>edge[maxn];

struct Hei
{
	int h;
	int num;
	Hei() {};
	Hei(int x, int y)
	{
		h = x;
		num = y;
	}
	void merge(const Hei &b)
	{
		if (b.h>h)
		{
			h = b.h;
			num = b.num;
		}
		else if (b.h == h)
		{
			num = 0;
		}
	}
	Hei Go_up()
	{
		return Hei(h + 1, num + 1);
	}
};

Hei up[maxn], down[maxn];

void cal(int x)
{
	vis[x] = 1;
	down[x] = Hei(0, 0);
	for (int i = 0; i<edge[x].size(); i++)
	{
		int nxt = edge[x][i];
		if (vis[nxt])continue;
		cal(nxt);
		down[x].merge(down[nxt].Go_up());
	}
	vis[x] = 0;
}

void calDown(int x)
{
	Hei suf(0, 0);
	vis[x] = 1;
	for (int i = edge[x].size() - 1; i >= 0; i--)
	{
		int nxt = edge[x][i];
		if (vis[nxt])continue;
		up[nxt] = suf;
		suf.merge(down[nxt].Go_up());
	}
	Hei pre(0, 0);
	for (int i = 0; i<edge[x].size(); i++)
	{
		int nxt = edge[x][i];
		if (vis[nxt])continue;
		Hei h = up[x];
		h.merge(pre);
		h.merge(up[nxt]);
		up[nxt] = h.Go_up();
		pre.merge(down[nxt].Go_up());
		calDown(nxt);
	}
	pre.merge(up[x]);
	ans[x] = pre.num;
	vis[x] = 0;
}

void solve()
{
	memset(up, 0, sizeof(up));
	memset(down, 0, sizeof(down));
	sa(n);
	repp(i, 1, n - 1)
	{
		int x, y;
		sa(x), sa(y);
		edge[x].push_back(y);
		edge[y].push_back(x);
	}
	cal(1);
	calDown(1);
	repp(i, 1, n)
	{
		//DE(ans[i])
		printf("%d\n", n - 1 - ans[i]);
	}
}
On this page
CS academy Round 29
  1. A.Missing Number
  2. B.Positive Xors
  3. C.Equality
  4. D.Odd Palindromes
  5. E.Root Change