AtCoder Regular Contest 088

Chong Wang Lv6
  2018-01-26 18:19:04 2018-01-26 18:19:04 Created   2026-10-09 08:58:53 2026-10-09 08:58:53 Updated

Questions D, E, and F in this issue are very interesting. To sum up, I had no idea when doing question E. After thinking about the solution to question F for a long time, I changed the question and found that the DP of $O(nlog^2n)$ is still amazing. . .

D Wide Flip

The meaning of the question is to give a 01 string $S(|S|\leq10^5)$, find the largest $K$, so that each flipped interval is at least $K$, and flipped to a string of 0.

If two points are passed, they can all become 0 or both become 1. Check one side from left to right each time.

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
int n;
char val[maxn];
int num[maxn];
bool check(int x)
{
	int cnt = 0;
	memset(num, 0, sizeof(num));
	int end = -1;
	int st = -1;
	repp(i, 1, n)
	{
		if (val[i] == '1')
		{
			st = i;
			end = i + x - 1;
			break;
		}
	}
	if (end == -1)
	{
		return true;
	}
	repp(i, st, end)
	{
		int now = val[i] - '0';
		int op = now ^ (cnt & 1);
		if (op)
		{
			if (i + x - 1>n)
				return false;
			cnt++;
		}
	}
	return true;
}
 
bool check2(int x)
{
	int cnt = 0;
	memset(num, 0, sizeof(num));
	int end = -1;
	int st = -1;
	repp(i, 1, n)
	{
		if (val[i] == '0')
		{
			st = i;
			end = i + x - 1;
			break;
		}
	}
	if (end == -1)
	{
		return true;
	}
	repp(i, st, end)
	{
		int now = '1' - val[i];
		int op = now ^ (cnt & 1);
		if (op)
		{
			if (i + x - 1>n)
				return false;
			cnt++;
		}
	}
	return true;
}
void solve()
{
	scanf("%s", val + 1);
	n = strlen(val + 1);
	int le = 1;
	int ri = n;
	while (le<ri)
	{
		int mid = (le + ri + 1) / 2;
		if (check(mid) || check2(mid))
		{
			le = mid;
		}
		else
		{
			ri = mid - 1;
		}
	}
	cout << le;
}

E Papple Sort

There is a string $S(|S|\leq 2*10^5)$ with all lowercase characters. Every time the adjacent characters are exchanged, ask how many times at least the exchange is required, and the string becomes a palindrome string.

This kind of problem needs to be simplified, and only the relative positions and solutions of the two pairs of characters are considered.

Considering the relative positions of two pairs of characters, there are the following three situations:

1)A…A…..B…B

2)A…B……..A…B

3)A…B…..B…A

One thing you will find here is that in any of the three situations, A can be on the periphery. That is, (l1, r1) and (l2, r2) when l1 < l2, (l1, r1) must be the peripheral letters. So just swipe from left to right, moving each letter to the outermost position.

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
char val[maxn];
ll num[maxn];
int lowbit(int x)
{
	return x&(-x);
}
ll getsum(ll x)
{
	ll ans = 0;
	while (x>0)
	{
		ans += num[x];
		x -= lowbit(x);
	}
	return ans;
}
ll add(int x, int v)
{
	int up = maxn - 1;
	while (x <= up)
	{
		num[x] += v;
		x += lowbit(x);
	}
	return x;
}
 
int vis[maxn];
int num_char[30];
vector<int>pos[30];
 
void solve()
{
	scanf("%s", val + 1);
	int len = strlen(val + 1);
 
	repp(i, 1, len)
	{
		num_char[val[i] - 'a']++;
		pos[val[i] - 'a'].push_back(i);
	}
	int cnt = 0;
	repp(i, 0, 26)
	{
		if (num_char[i] & 1)
		{
			cnt++;
		}
	}
	if (cnt >= 2)
	{
		puts("-1");
		return;
	}
	repp(i, 1, len)
	{
		add(i, 1);
		vis[i] = 1;
	}
	ll ans = 0;
	repp(i, 1, len)
	{
		if (vis[i] == 0)continue;
		int p = pos[val[i] - 'a'].back();
		pos[val[i] - 'a'].pop_back();
		if (p == i)
		{
			ans += ((getsum(len) - getsum(i)) >> 1);
		}
		else
		{
			ans += (getsum(len) - getsum(p));
		}
		vis[i] = 0;
		vis[p] = 0;
		add(p, -1);
		add(i, -1);
	}
	printf("%lld\n", ans);
}

F Christmas Tree

A chains with a length of at most B are combined into a tree of a specific shape through the method in the figure. The lexicographic order of (A,B) is required to be minimum. Find A and B.

According to the explanation of the problem, it can be regarded as a path that can dye a tree into A color at most, and the length of each path is at most B.

It can be found that only points with odd degrees can be made as endpoints. Therefore, the minimum A is the odd point S/2. In this case, see what the maximum degree of each path can be. Dichotomous B value. Every time you check x, you need to do a tree-shaped DP, because the odd points need to be used as endpoints, so the edge between the fa and x points needs to be put into son for matching. dp[x] represents the length of the upward path from this point. If there are an even number of points in son, then just scan once to the left and right, dp[x]=-1. If there are an odd number of sons, a point needs to be raised, and then another two points are made.

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
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
int n;
vector<int>edge[maxn];
int dp[maxn];
 
bool dfs(int x, int fa, int up)
{
	vector<int>son;
	if (edge[x].size() & 1)son.push_back(0);
	for (int i = 0; i<edge[x].size(); i++)
	{
		int to = edge[x][i];
		if (to == fa)continue;
		if (!dfs(to, x, up))return false;
		if(dp[to] != -1)son.push_back(dp[to] + 1);
	}
 
	sort(son.begin(), son.end());
 
	if (son.size() % 2 == 0)
	{
		int st = 0;
		int en = son.size() - 1;
		while (st < en)
		{
			if (son[st] + son[en] > up)
			{
				return false;
			}
			st++;
			en--;
		}
		dp[x] = -1;
	}
	else
	{
		int le = 0;
		int ri = son.size() - 1;
		int flag = 1;
		while (le < ri)
		{
			int mid = (le + ri) / 2;
 
			int i = 0;
			int j = son.size() - 1;
			flag = 1;
			while (i < j)
			{
				if (i == mid)i++;
				if (j == mid)j--;
				if (i<j)
				{
					if (son[i] + son[j] > up)
					{
						flag = 0;
						break;
					}
					else
					{
						i++;
						j--;
					}
				}
			}
			if (flag)
			{
				ri = mid;
			}
			else
			{
				le = mid + 1;
			}
		}
		if (son[le] > up)return false;
		int i = 0;
		int j = son.size() - 1;
		while (i < j)
		{
			if (i == le)i++;
			if (j == le)j--;
			if (i<j)
			{
				if (son[i] + son[j] > up)
				{
					return false;
				}
				else
				{
					i++;
					j--;
				}
			}
		}
		dp[x] = son[le];
	}
	return true;
}
 
void solve()
{
	sa(n);
	repp(i, 1, n - 1)
	{
		int x, y;
		sa(x), sa(y);
		edge[x].push_back(y);
		edge[y].push_back(x);
	}
	int cnt = 0;
	int p = 1;
	repp(i, 1, n)
	{
		if (edge[i].size() & 1)
		{
			cnt++;
		}
		if (edge[i].size() == 1)
		{
			p = i;
		}
	}
	int ans = cnt / 2;
	int le = 1;
	int ri = n;
	while (le < ri)
	{
		int mid = (le + ri) / 2;
		memset(dp, 0, sizeof(dp));
		if (dfs(p, -1, mid))
		{
			ri = mid;
		}
		else
		{
			le = mid + 1;
		}
	}
	cout << ans << " " << le << endl;
}
On this page
AtCoder Regular Contest 088
  1. D Wide Flip
  2. E Papple Sort
  3. F Christmas Tree