Codeforces 375 Div2

Chong Wang Lv6
  2016-10-06 20:25:18 2016-10-06 20:25:18 Created   2026-10-09 08:52:27 2026-10-09 08:52:27 Updated  

Title link and Code link

A, B, and D are all very simple. The interpretation of question C is a little off + the range of the array is not judged, GG. I dare not even think about the two structures E and F. . . . Question E has been considering the network flow solution, but I can’t figure out how to build a graph.

A The New Year: Meeting Friends

The shortest distance between three points to the same point.

minus the sum of the absolute values ​​of the median.

B Text Document Analysis

Given a sequence of strings, ask the number of words inside the brackets and the maximum length of the words outside the brackets.

Maintain the current status, within the brackets or outside the brackets, and record the corresponding results for each status.

C Polycarp at the Radio

The question is very convoluted and annoying. . .

The meaning of the question is to give the number of $n$. $a_i$ means that the i-th song is played by the band $a_i$. Now the person wants to redistribute the tracks so that in all cases, the band that plays the least tracks, $1$ to $m$, plays the most.

The final minimum value must be $n/m$.

The scope is not determined well, it is the rewrite allocation written by xjb. For each type of $m$, when the quantity is greater than $n/m+n%m$, give the smaller quantity. If the current number of bands from 1 to m is not enough, take it from the value greater than m or the one with a larger number. Complexity$O(mn)$.

D Lakes in Berland

The meaning of the question is to give the grid of $n*m$, ‘*’ represents land and ‘.’ represents water. A lake refers to a grid connected block surrounded by land. Water that is not bounded by land or connected to a convenient connection belongs to the ocean. Now it is required to change the number of lakes to $k$. Ask how many cells are the minimum changes.

It is purely a deep search of xjb, find the $n-k$ with the smallest area, and calculate the sum.

*E One-Way Reform

Given $n$ points and $m$ edges, these edges now have no direction. You are required to set a direction for each edge so that the number of points with outgoing edge = incoming edge is the largest.

For each oddity point, connect it to the point $n+1$. Then run the Euler circuit and continuously delete edges.

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
int n, m;
set<int>ed[maxn];
int out[maxn], in[maxn];
vector<pair<int, int>>res;

void dfs(int x)
{
	while (ed[x].size())
	{
		auto it = ed[x].begin();
		int p = *it;
		res.push_back(mp(x, *it));
		ed[x].erase(it);
		ed[p].erase(x);
		dfs(p);
	}
}

void solve()
{
	scanf("%d%d", &n, &m);
	memset(in, 0, sizeof(in));
	memset(out, 0, sizeof(out));
	for (int i = 1; i <= n + 1; i++)
	{
		ed[i].clear();
	}
	for (int i = 1; i <= m; i++)
	{
		int x, y;
		scanf("%d%d", &x, &y);
		out[x]++;
		in[y]++;
		ed[x].insert(y);
		ed[y].insert(x);
	}
	int ans = 0;
	for (int i = 1; i <= n; i++)
	{
		if ((out[i] + in[i]) % 2)
		{
			ed[i].insert(n + 1);
			ed[n + 1].insert(i);
		}
		else
		{
			ans++;
		}
	}
	res.clear();
	for (int i = 1; i <= n; i++)
	{
		dfs(i);
	}
	printf("%d\n", ans);
	for (int i = 0; i < res.size(); i++)
	{
		if (res[i].first == n + 1 || res[i].second == n + 1)continue;		
		printf("%d %d\n", res[i].first, res[i].second);		
	}
}

It is also possible to build a network flow. I always vaguely felt that I had encountered this problem. After reading [this blog] (http://blog.csdn.net/snowy_smile/article/details/52732805), I was even more convinced that I had done it (this kind of network flow problem is still very common. I will try to figure it out next time I encounter a similar one~).

*F st-Spanning Tree

Given $n$ points and $m$ edges, it is required to construct a tree so that the degree of the given two points $s$, $t$ does not exceed $d_s$, $d_t$.

First, put in the edges that do not contain $s$ and $t$ without thinking.

After that, you will find that there are connected blocks one by one. First, look for whether there is a connected block connecting $s$ and $t$. If not, then there must be $s$ and $t$. Connect them. Then connect $s$ to $s$, and connect $t$ to $t$.

If there is a connected block connecting $s$ and $t$, after connecting, $s$ can be connected to $s$, and $t$ can be connected to $t$.

On this page
Codeforces 375 Div2
  1. A The New Year: Meeting Friends
  2. B Text Document Analysis
  3. C Polycarp at the Radio
  4. D Lakes in Berland
  5. *E One-Way Reform
  6. *F st-Spanning Tree