Theme NexT works best with JavaScript enabled

2019 牛客暑期多校训练营第十场题解

本文包括 2019 牛客暑期多校训练营第十场的题面与题解。

A - Blackjack

题目描述

As the saying goes, “if you are hesitant, you will lose the game; if you are decisive, you will die in vain.”

Calabash doesn’t want to lose the game, neither to die in vain. But, this is not important, because he doesn’t have enough money to buy the game.

Fortunately, Roundgod, the banker of a casino, gives him a chance to fulfill his dream. Roundgod promises to buy him the game if he could win in one round of Blackjack. The Blackjack involves a deck of playing cards, each has some points on it. It is carried out as follows: Roundgod gives a number aaa and tells Calabash the number of points on each of the cards. Then, Calabash begins to draw cards, according to the following procedure:

  1. the deck of all cards is shuffled uniformly at random;
  2. Calabash could repeatedly draw a card from the deck (he immediately knows the number of the points on the card after drawing the card), or declare to stop drawing at any moment;
  3. if, after drawing any card, the total number of points on cards Calabash drawn exceeds a limit bbb, he loses immediately;
  4. otherwise, after Calabash stops drawing, he wins if the total number of points on cards he drew is greater than a.

Calabash wants to know the probability to win if he plays optimally so that he can obtain his favorite game. Please help him to calculate the probability.

输入描述

There are two lines in the input. The first line consists of three integers $ n, a, b $ ( $ 1 \leq n \leq 500, 1 \leq a < b \leq 500 $ ), denoting the number of cards in the deck, the number given by Roundgod, and the limit to the total number of points, respectively.

The second line contains $ n $ integers $ x_1, x_2, \cdots, x_n $ ( $ 1 \leq x_i \leq 500 $ ), denoting the numbers of points of these cards. It is guaranteed that $ \sum_{i=1}^n x_i > b $ .

输出描述

Output the answer within an absolute error of no more than $ 10^{-6} $ .

示例1

输入

1
2
5 2 4
1 1 1 5 5

输出

1
0.100000000000

示例2

输入

1
2
5 2 4
1 1 1 3 5

输出

1
0.450000000000

B - Coffee Chicken

题目描述

Dr. JYY has just created the Coffee Chicken strings, denoted as S(n). They are quite similar to the Fibonacci soup —- today’s soup is made by mingling yesterday’s soup and the day before yesterday’s soup:

  • $ S(1) = \texttt{“COFFEE”} $
  • $ S(2) = \texttt{“CHICKEN”} $
  • $ S(n) = S(n-2) :: S(n-1) $ , where $ :: $ denotes string concatenation.

The length of $ S(n) $ quickly gets out of control as $ n $ increases, and there would be no enough memory in JYY’s game console to store the entire string. He wants you to find $ 10 $ contiguous characters in $ S(n) $ , starting from the $ k $ -th character.

输入描述

The first line of input is a single integer $ T $ ( $ 1 \leq T \leq 1000 $ ), denoting the number of test cases.

Each of the following T lines is a test case, which contains two integers $ n, k $ ( $ 1 \leq n \leq 500 $ , $ 1 \leq k \leq \min\{|S(n)|, 10^{12}\} $ ). $ |S| $ denotes the length of string $ S $ .

输出描述

For each test case, print the answer in one line. If there are no enough characters from the $ k $ -th character, output all characters until the end of the string.

示例1

输入

1
2
3
2
3 4
2 7

输出

1
2
FEECHICKEN
N

题解

题意

给定 $ S(1) $ 与 $ S(2) $ 两字符串, $ S(n) $ 为 $ S(n-1) $ 与 $ S(n-2) $ 两字符串连接而成 ,请输出 $ S(n) $ 中从第 $ k $ 个字符开始的 $ 10 $ 个字符。

解法

记 $ f(i) $ 表示 $ S(i) $ 的长度, $ f(i) = f(i-2)+f(i-1) $ .

递归调用 $ solve(n, k) $ 表示 $ S(n) $ 的第 $ k $ 个字符,

若 $ n \leq 2 $ 直接返回答案,

$ n > 2 $ 时,若 $ k > f(i-2) $ ,调用 $ solve(n-1, k-f(n-2)) $ ;否则调用 $ solve(n-2, k) $ .

注意特判 $ k > f(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
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define INF 1000000000010LL
#define N 200010
ll s[N], n, k;
string ans[2] = {"COFFEE", "CHICKEN"};
char solve(ll n, ll k) {
if (n < 3) return ans[n - 1][k - 1];
return k > s[n - 2] ? solve(n - 1, k - s[n - 2]) : solve(n - 2, k);
}
void Prepare() {
s[1] = 6, s[2] = 7;
for (int i = 3; i <= 500; i++) s[i] = min(s[i - 2] + s[i - 1], INF);
}
int main() {
Prepare();
int T;
scanf("%d", &T);
while (T--) {
scanf("%lld%lld", &n, &k);
for (ll i = k; i < k + 10 && i <= s[n]; i++) putchar(solve(n, i));
putchar('\n');
}
return 0;
}

C - Gifted Composer

题目描述

Acesrc is a gifted composer. He likes writing tuneful and melodic songs. Every song he writes can be viewed as a sequence of musical notes, and each musical note represents the pitch and the duration of the sound. In this problem, we consider only the following seven primary pitches do re mi fa sol la si and the duration of each note is one unit time. Hence, there are only seven types of notes, and we may use the pitch name to represent a note.

Acesrc composes a song in the following way. Initially, the sequence of notes is empty. Every day, he inserts a new note at the beginning or at the end of the sequence, until the song is done.

Acesrc particularly likes songs with repetitions. For a song with n musical notes, we say the song has a repetition of length $ k $ ( $ 1 \leq k \leq n $ ), if the song can be partitioned into one or more identical sections with $ k $ notes, optionally followed by an incomplete section, which is an initial part of a complete section. For example, do re do re do be partitioned into do re | do re | do, so it has a repetition of length $ 2 $ ; similarly, do re mi do re mi has a repetition of length $ 3 $ , and do re do re mi has a repetition of length $ 5 $ .

Acesrc wants to know, after he adds a note each day, the number of different lengths of repetitions the song has. Can you help him?

输入描述

The first line of input consists of a single line $ n $ ( $ 1 \leq n \leq 10^6) $ , the number of days Acesrc uses to compose the song. The ith of the remaining $ n $ lines contains a character $ a $ ( $ a \in \{\texttt{p}, \texttt{a}\} $ )(where $ \texttt{p} $ denotes prepend, i.e., inserting at the beginning, and $ \texttt{a} $ denotes append, i.e., inserting at the end) and a string $ s $ ( $ s \in \{\texttt{do}, \texttt{re}, \texttt{mi}, \texttt{fa}, \texttt{sol}, \texttt{la}, \texttt{si}\} $ ), representing the action Acesrc takes in the $ i $ -th day.

输出描述

Output n lines. The ith line should be a single integer, denoting the answer for the $ i $ -th day.

示例1

输入

1
2
3
4
5
6
5
a do
p re
a re
a do
p do

输出

1
2
3
4
5
1
1
2
2
3

示例2

输入

1
2
3
4
5
6
5
a re
a do
a re
p do
a mi

输出

1
2
3
4
5
1
1
2
2
1

D - Han Xin and His Troops

题目描述

His majesty chatted with Han Xin about the capabilities of the generals. Each had their shortcomings. His majesty asked, How many troops could I lead?" Han Xin replied,Your highness should not lead more than 100000.” His majesty said, And what about you?"For your humble servant, the more the merrier!” said Han Xin.

—Records of the Grand Historian

Han Xin was a military general who served Liu Bang during the Chu-Han contention and contributed greatly to the founding of the Han dynasty. Your friend, in a strange coincidence, also named Han Xin, is a military general as well.

One day you asked him how many troops he led. He was reluctant to tell you the exact number, but he told you some clues in certain form, for example:

  • if we count the troops by threes, we have two left over;
  • if we count by fives, we have three left over;
  • if we count by sevens, two are left over;

You wonder the number of his troops, or he was simply lying. More specifically, you would like to know the minimum possible number of troops he leads, and if the minimum number is too large, then you suspect he was lying.

输入描述

The first line of input contains two integers $ n, m $ ( $ 1 \leq n \leq 100, 1 \leq m \leq 10^{18}) $ , the number of clues he told you and the threshold that you think he was probably lying.

The remaining part of the input are $ n $ lines, specifying the clues, Each line consists of two integers $ a, b $ ( $ 0 \leq b < a < 10^5 $ ), representing a clue that b troops are left over if we count them by a’s.

输出描述

If there does not exist a non-negative number of troops satisfying all clues, print $ \texttt{he was definitely lying} $ ;otherwise, if the minimum non-negative possible number of troops is greater than m, print $ \texttt{he was probably lying} $ ; otherwise, print the minimum non-negative number.

示例1

输入

1
2
3
4
3 100
3 2
5 3
7 2

输出

1
23

示例2

输入

1
2
3
4
5
4 10000
12 7
15 2
30 5
8 6

输出

1
he was definitely lying

示例3

输入

1
2
3
2 10
11 3
19 7

输出

1
he was probably lying

题解

题意

韩信点兵,给定 $ 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
def mymul(a, b, mod):
sum = 0
while b:
if b & 1:
sum = (sum + a) % mod
a = (a + a) % mod
b >>= 1
return sum


def exgcd(a, b):
if b == 0:
return a, 1, 0
gcd, y, x = exgcd(b, a % b)
y -= (a / b) * x
return gcd, x, y


n, k = map(int, raw_input().split())
m = [0] * n
a = [0] * n


def kaven():
global n, m, a
M = m[0]
ans = (a[0] % M + M) % M
for i in range(1, n):
gcd, x, y = exgcd(M, m[i])
c = ((a[i] - ans) % m[i] + m[i]) % m[i]
if c % gcd:
return -1
x = mymul(x, c / gcd, m[i] / gcd)
ans += x * M
M *= m[i] / gcd
ans = (ans % M + M) % M
return ans


for i in range(n):
m[i], a[i] = map(int, raw_input().split())
ans = kaven()
if ans == -1:
print 'he was definitely lying'
else:
if ans > k:
print 'he was probably lying'
else:
print ans

E - Hilbert Sort

题目描述

The Hilbert curve, invented by the German mathematician David Hilbert, is one of the most famous fractal curves. The i-th Hilbert curve gives a sequential ordering of the cells in a $ 2^i \times 2^i $ grid.

The formal definition of Hilbert curves is recursive. The $ i $ -th Hilbert curve can be formed by connecting four $ (i-1) $ -th Hilbert curves, in the following way:

  1. partition the $ 2^i \times 2^i $ grid into four $ 2^{i-1} \times 2^{i-1} $ quadrants;
  2. reflect an $ (i-1) $ -th Hilbert curve across the main diagonal (from top left to bottom right), and place it in the upper left quadrant;
  3. place two copies of the $ (i-1) $ -th Hilbert curve in the lower left and lower right quadrants, respectively;
  4. reflect an $ (i-1) $ -th Hilbert curve across the secondary diagonal (from top right to bottom left), and place it in the upper right quadrant.

The first three Hilbert curves are shown below.

The Hilbert sort, just as the name implies, is to sort a set of the cells according to the Hilbert curve. A cell is ranked before another if it is encountered earlier when walking along the Hilbert curve. The Hilbert sort is widely used in many areas, because such sort maps a set of $ 2 $ -dimensional data points into $ 1 $ -dimensional space, with spatial locality preserved fairly well.

Give you an integer $ k $ and a set of cells in the $ 2^k \times 2^k $ grid, please sort them in the order induced from the $ k $ -th Hilbert curve.

输入描述

The first line contains two integers $ n, k $ ( $ 1 \leq n \leq 10^6, 1 \leq k \leq 30 $ ), the number of cells to sort and the order of the Hilbert curve.

The next $ n $ lines, each containing two integers $ x_i, y_i $ ( $ 1 \leq x_i, y_i \leq 2^k $ ), denoting the cell in the $ x_i $ -th row and the $ y_i $ -th column. All cells in the input are distinct.

输出描述

Output the coordinates of the sorted cells in n lines.

示例1

输入

1
2
3
4
5
6
5 2
2 4
2 3
1 1
3 1
4 3

输出

1
2
3
4
5
1 1
3 1
4 3
2 4
2 3

示例2

输入

1
2
3
4
5
4 1
1 1
1 2
2 1
2 2

输出

1
2
3
4
1 1
2 1
2 2
1 2

题解

题意

给定方阵的一些点,按照希尔伯特曲线经过的先后顺序为这些点排序。

解法

希尔伯特曲线是一种典型的分形,因此具备递归的条件。

观察规律后发现将左上区域逆时针旋转 $ 90 $ 度,右上区域顺时针旋转 $ 90 $ 度,下方区域转移可以实现希尔伯特曲线的构造,于是递归。

代码

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
#include <bits/stdc++.h>
using namespace std;
struct Point {
int x, y;
long long pos;
bool operator<(const Point &a) const { return pos < a.pos; }
} a[1000005];
long long solve(int x, int y, int depth) {
if (depth == 0) return (y * 3) ^ x;
const int dshift = 1 << depth;
if (x >= dshift)
return 1LL << 2 * depth + (y >= dshift) |
solve(x ^ dshift, y & ~dshift, depth - 1);
if (y < dshift) return solve(y, x, depth - 1);
return 3LL << 2 * depth |
solve((dshift << 1) - y - 1, dshift - x - 1, depth - 1);
}

int main() {
int n, k;
scanf("%d%d", &n, &k);
for (int i = 0; i < n; i++) {
scanf("%d%d", &a[i].x, &a[i].y);
a[i].pos = solve(a[i].x - 1, a[i].y - 1, k - 1);
}
sort(a, a + n);
for (int i = 0; i < n; i++) printf("%d %d\n", a[i].x, a[i].y);
return 0;
}

F - Popping Balloons

题目描述

Recently, an interesting balloon-popping game can be commonly found near the streets. The rule of this game is quite simple: some balloons are tied to cells of a lattice, and you are allowed to throw some darts to prick the balloons. The more balloons you pierce, the more incredible prize you will get.

Probably because too many people have got bored with this childish game, a new variation of the game has appeared. In this variation, you should prick the balloons by shooting an air rifle instead of throwing darts. You can make six shots in total, three horizontally and three vertically. If you shoot horizontally (vertically, resp.), all balloons in the row (column, resp.) are popped. In order to increase the difficulty, there is one restriction imposed on your shots: the distances between any two adjacent horizontal shots and any two adjacent vertical shots must all equal to a given number $ r $ . The problem is, what is the maximum number of balloons you can pop by making three horizontal and three vertical shots, under the aforementioned restriction.

输入描述

The first line of input is two integers $ n, r $ ( $ 1 \leq n, r \leq 10^5 $ ), the number of balloons and the distance between any two adjacent horizontal or vertical shots.

The remaining part of the input is n lines, specifying the positions of the balloons. Each of these lines contains two integers $ x, y $ ( $ 0 \leq x, y \leq 10^5 $ ), denoting a balloon positioned at $ (x, y) $ . Note that multiple balloons may lie in the same position.

输出描述

Output the answer as a single integer in one line.

示例1

输入

1
2
3
4
5
6
7
8
7 1
0 0
1 1
2 2
3 3
4 4
5 5
7 8

输出

1
6

示例2

输入

1
2
3
4
5
6
5 2
0 10
2 3
5 7
9 6
2 3

输出

1
4

题解

题意

给定平面中的 $ n $ 个点,三条平行于 $ x $ 轴的线和三条平行于 $ y $ 轴的线(要求且相邻线间隔为 $ r $ )问最多能覆盖多少点。

解法

考虑对列建一棵线段树,每个结点存放 $ num[j] + num[j + d] + num[j + 2d] $ 的值。然后枚举行的同时删除选中的点并使用线段树查询最大值即可。删除点的时候只会对自己 $ x,x-d,x-2d $ 的位置产生影响,删除过查询后要重新加上。

代码

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 <bits/stdc++.h>
using namespace std;
#define ll long long
#define ls rt << 1
#define rs rt << 1 | 1
#define lson l, mid, rt << 1
#define rson mid + 1, r, rt << 1 | 1
#define N 100005
#define M 200010
#define INF 0x3f3f3f3f3f3f3f3f
vector<int> v[M];
int num[M], n, d;
ll tree[M << 2];
void push_up(int rt) { tree[rt] = max(tree[ls], tree[rs]); }
void build(int l, int r, int rt) {
if (l == r) {
for (int i = 0; i < 3; ++i)
if (l + i * d <= N) tree[rt] += num[l + i * d];
return;
}
int mid = (l + r) >> 1;
build(lson), build(rson), push_up(rt);
}
void update(int pos, int val, int l, int r, int rt) {
if (l < 0 || r > N || pos < 0 || pos > N) return;
if (l == r) {
tree[rt] += val;
return;
}
int mid = (l + r) >> 1;
if (pos <= mid)
update(pos, val, lson);
else
update(pos, val, rson);
push_up(rt);
}
ll query(int ql, int qr, int l, int r, int rt) {
if (ql <= l && r <= qr) return tree[rt];
int mid = (l + r) >> 1;
ll ret = -INF;
if (ql <= mid) ret = max(ret, query(ql, qr, lson));
if (qr > mid) ret = max(ret, query(ql, qr, rson));
return ret;
}

int main() {
scanf("%d%d", &n, &d);
for (int i = 1, x, y; i <= n; ++i) {
scanf("%d%d", &x, &y);
v[y].push_back(x);
num[x]++;
}
build(0, N, 1);
ll ans = 1;
for (int i = 0; i <= N; ++i) {
ll tmp = 0;
for (int j = 0; j < 3; ++j)
if ((ll)(i + j * d) <= N) {
tmp += v[i + j * d].size();
for (auto x : v[i + j * d]) {
update(x, -1, 0, N, 1);
update(x - d, -1, 0, N, 1);
update(x - 2 * d, -1, 0, N, 1);
}
}
tmp += query(0, N, 0, N, 1);
ans = max(ans, tmp);
for (int j = 0; j < 3; ++j)
if ((ll)(i + j * d) <= N)
for (auto x : v[i + j * d]) {
update(x, 1, 0, N, 1);
update(x - d, 1, 0, N, 1);
update(x - 2 * d, 1, 0, N, 1);
}
}
printf("%lld\n", ans);
return 0;
}

G - Road Construction

题目描述

The mayor of Byteland is planning to build a new road across the town. Constructing new roads may facilitate transportation and stimulate economic development; the negative aspects include, the noise that may affect the residents nearby, and the nonnegligible impacts on the local ecological environment.

You have been required to draft a road construction plan. In your plan, you can model the residents of the town as points, and the road as a straight line of infinite length. Your plan should satisfy the following conditions:

  • The road should not pass through any resident of the city;
  • The numbers of residents on both sides of the road are equal;
  • The minimum of the distances of the residents to the road is maximized.

The following figure depicts the optimal road construction plan for the first sample test data.

Since there are too many residents in Byteland, you believe it is impossible to find such a construction plan manually. It’s your time to write a program and find the optimal plan.

输入描述

The input starts with a line containing an even integer $ n $ ( $ 1 \leq n \leq 300 $ )indicating the number of residents in Byteland. It is then followed by $ n $ lines, each containing two integers $ x, y $ ( $ |x|, |y| \leq 10^6 $ ), the Cartesian coordinates of a resident. No two residents share the same coordinates.

输出描述

Print the minimum of the distances of the residents to the road you plan to build. Your answer should have an absolute or relative error of no more than $ 10^{-6} $ .

示例1

输入

1
2
3
4
5
6
7
6
0 0
3 0
1 2
4 3
-1 4
5 -3

输出

1
1.264911064067

示例2

输入

1
2
3
2
1 3
2 5

输出

1
1.118033988750

题解

题意

给定平面上的 $ n $ 个点,要求你用一条直线分成数量相等的两部分。已知任意分法都有一个点到直线的最短距离 $ d $ ,求 $ d $ 最大值。

解法

首先有结论:该直线必然与某两点的连线平行或垂直。

于是枚举任意两点构成的直线的斜率,每次找出最中间两点,取两点所连线段的中点为一定点,确定该直线。

代码

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
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define N 305
#define INF 0x3f3f3f3f
using namespace std;
struct Node {
double x, y, b;
bool operator<(const Node &c) const { return b < c.b; }
} p[N];
double x[N], y[N];
double dis(double k, double b, double x, double y) {
return fabs(k * x + b - y) / sqrt(k * k + 1.0);
}
int main() {
int n;
scanf("%d", &n);
for (int i = 1; i <= n; i++) {
scanf("%lf%lf", &x[i], &y[i]);
p[i].x = x[i], p[i].y = y[i];
}
double ans = 0;
for (int i = 1; i <= n; i++) {
for (int j = i + 1; j <= n; j++) {
double k = (y[i] - y[j]) / (x[i] - x[j]);
for (int h = 1; h <= n; h++) {
p[h].b = p[h].y - k * p[h].x;
}
sort(p + 1, p + n + 1);
double b = (p[n / 2].b + p[n / 2 + 1].b) / 2.0;
ans = max(ans, dis(k, b, p[n / 2].x, p[n / 2].y));
k = -1.0 / k;
for (int h = 1; h <= n; h++) {
p[h].b = p[h].y - k * p[h].x;
}
sort(p + 1, p + n + 1);
b = (p[n / 2].b + p[n / 2 + 1].b) / 2.0;
ans = max(ans, dis(k, b, p[n / 2].x, p[n / 2].y));
}
}
printf("%.10f\n", ans);
return 0;
}

H - Stammering Chemists

题目描述

Like many other organic chemists, you are busy in synthesizing, separating, purifying and identifying new chemical compounds all year round. Getting bored with traditional substance isolation and identification methods, such as column chromatography, a bold idea comes to your mind: Computer Assisted Molecule Identification (CAMI). With this technology, millions of chemists can be freed from arduous manual labor. How promising!

Currently, you are developing a simplified version of CAMI that works for hydrocarbons (organic compounds consisting of hydrogen and carbon only). All hardware-side technologies are done, and you are just going to write the program. The sensor reports all carbon atoms as well as the chemical bonds between them. This naturally forms a graph, where carbon atoms are vertices, and the bonds are edges. Each connected component of this graph corresponds to a molecule, and the component itself is called hydrogen-depleted molecular graph (HDMG) of the molecule, since we generally do not care about hydrogen atoms.

The sensor has just detected some hexane molecules, which is a specific kind of hydrocarbons, consisting of $ 6 $ carbon atoms and $ 14 $ hydrogen atoms per molecule. There are five essentially different hexanes, also known as isomers:

Your task is to identify, for each hexane molecule detected, which specific type of hexane isomer it is. A molecule should be identified as any of the above isomers if its hydrogen-depleted molecular graph is isomorphic to the HDMG presented in the above table.

输入描述

The first line of input consists of only a single integer $ T $ ( $ 1 \leq T \leq 200000 $ ), denoting the number of hexane molecules detected.

Every five lines of the remaining part of the input specify a molecule detected. Each of the five lines contains two integers $ a, b $ ( $ 1 \leq a, b \leq 6 $ , $ a \neq b $ ), denoting a bond between carbon atoms $ a $ and $ b $ . In each molecule, the carbon atoms are numbered $ 1 $ through $ 6 $ .

It is guaranteed that, for each molecule in the input, it is exactly one type of the hexane isomers listed above.

输出描述

For each molecule in the input, display the name of the isomer in one line.

示例1

输入

1
2
3
4
5
6
7
8
9
10
11
2
1 2
2 3
3 4
4 5
5 6
1 4
2 3
3 4
4 5
5 6

输出

1
2
n-hexane
3-methylpentane

题解

题意

给定一棵树,对应该树的构型输出它的类型。

解法

求出每个点所连点的个数,排好序以后即可排除大多树情况。对于相同的情况。从某个点出发,深搜寻找特点即可。

代码

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
#include <bits/stdc++.h>
using namespace std;
struct faner {
int x, id;
} s[7];
bool cmp(faner a, faner b) { return a.x > b.x; }
int g[7][7];
int main() {
int t;
scanf("%d", &t);
while (t--) {
for (int i = 1; i <= 6; i++) s[i].x = g[i][0] = 0, s[i].id = i;
for (int i = 1, x, y; i <= 5; i++) {
scanf("%d%d", &x, &y);
g[x][++g[x][0]] = y, g[y][++g[y][0]] = x;
++s[x].x, ++s[y].x;
}
sort(s + 1, s + 7, cmp);
if (s[1].x == 4)
puts("2,2-dimethylbutane");
else if (s[1].x == 3) {
if (s[2].x == 3)
puts("2,3-dimethylbutane");
else {
int num = 0, c = s[1].id;
for (int i = 1; i <= 3; i++)
if (g[g[c][i]][0] == 1) num++;
if (num == 1)
puts("3-methylpentane");
else
puts("2-methylpentane");
}
} else
puts("n-hexane");
}
return 0;
}

I - Travel Dream

题目描述

Andy is an ordinary student at Nanjing University. One day, he found himself transmitted to a wonderland when he was dreaming. The wonderland consisted of several spots, with some bidirectional roads of various travel times connecting some pairs of them.

Attracted by the fascinating scenery, Andy wanted to visit some spots in the wonderland. He would like to select exactly $ k $ distinct spots and visit them one by one. After visiting the last spot, he must turn back to the first spot, because that was where his dream started. There must be a road between any two adjacent spots he selected, including the last one and the first one. Moreover, he wanted to maximize the total time spent in moving between the spots, so that he could better enjoy the beauties.

For example, in the first sample data, you may choose to start from spot $ 1 $ , visit spots $ 3, 5, 2 $ , and return to spot $ 1 $ . The total time spent was $ 21 $ minutes, which turns out to be optimal.

However, finding such a traveling plan was too hard for Andy, so he wanted your help. Could you help him to find such an optimal plan?

输入描述

The first line of input consists of three integers $ n, m, k $ ( $ 2 \leq n \leq 300 $ , $ 1 \leq m \leq 300 $ , $ 3 \leq k \leq 10 $ ), denoting the number of spots and the number of roads in the wonderland, and the number of spots Andy would like to visit, respectively. The spots are numbered $ 1 $ through $ n $ .

The remaining m lines specify the roads between the spots. Each of these lines contains three integers $ u, v, t $ ( $ 1 \leq u, v \leq n $ , $ u \neq v $ , $ 1 \leq t \leq 10^8 $ ), representing a bidirectional road between spots $ u $ and $ v $ , and it took $ t $ minutes to travel along the road in either direction. It is guaranteed that there was at most one road between any pair of spots in the wonderland.

输出描述

Print the maximum total travel time in minutes as an integer in one line. If it is impossible to find any valid travel plan, output $ \texttt{impossible} $ instead.

示例1

输入

1
2
3
4
5
6
7
8
5 7 4
1 2 2
1 3 3
2 3 4
4 3 1
5 3 7
4 5 6
2 5 9

输出

1
21

示例2

输入

1
2
3
4
5
5 4 5
1 2 1
2 3 6
3 1 5
4 5 2

输出

1
impossible

J - Wood Processing

题目描述

In the wood industry, it is very common to make big wood boards by combining planks. To combine several planks into boards, the carpenter may cut some of the planks horizontally and discard one of the two parts, such that the heights of all planks are equal. Then, the planks are joined together, forming a big wood board. The height of the board is the common height of the planks, and the width of the board is the sum of the widths of the planks.

However, cutting planks may result in huge wastes. The problem is, given $ n $ planks, determine the minimum total wasted area of planks to make $ k $ boards from these planks. You may freely reorder and combine these planks. Note that the mechanical properties of a plank are anisotropic, so you can’t rotate the planks. Also, all planks must be used; you cannot discard any whole plank.

输入描述

The first line of the input contains two integers $ n, k $ ( $ 1 \leq n \leq 5000 $ , $ 1 \leq k \leq 2000 $ , $ k \leq n $ ), denoting the number of planks given and the number of boards to make.

Each of the remaining $ n $ lines contains two integers $ w, h $ ( $ 1 \leq w, h \leq 10^7 $ ), denote the width and the height of a given plank.

输出描述

Output the minimum wasted area as an integer.

示例1

输入

1
2
3
4
3 2
3 3
4 7
2 5

输出

1
4

示例2

输入

1
2
3
4
5
6
7
6 3
1 1
1 2
1 3
1 4
1 5
1 6

输出

1
3

题解

题意

给定 $ n $ 块木头,每块木头有一个高 $ h $ 和宽 $ w $ 。现在可以把多块木头联合成一块,但需要削去一部分,使得他们高度相同。询问你把这 $ n $ 块木头连接成 $ k $ 块最少需要削去多少木头。

解法

把木头从高到低排序,令 $ dp(i,j) $ 表示将前 $ i $ 块木头合并成为 $ j $ 块木头所需的最小花费。那么合并后最后一块木头的高度一定是合并前的第 $ i $ 块木头的高度。

容易得出 $ dp $ 转移方程: $ dp[i][j] = min(dp(k, j - 1) + cal(k, i)) $ ,其中 $ cal(k, i) $ 为把第 $ k + 1 $ 块木头到第 $ i $ 块木头的高度变成一样的花费。

直接转移 $ O(n ^ 2 \times k) $ ,时间复杂度糟糕,考虑斜率优化。列出 $ cal(k, i) $ 公式,单调队列维护下凸包。需要注意到斜率乘积会爆long long,所以需要用到__int128

代码

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
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define lll __int128
#define Pll pair<ll, ll>
#define N 5010
#define M 2010
Pll a[N];
int n, m;
ll f[N][N], w[N], sum[N];
int q[N][M], l[M], r[M];
ll cal(ll x, ll y) { return f[x][y] - sum[x]; }
void update(int x, int y) {
ll h = -a[x].first;
while (l[y] < r[y]) {
int p1 = q[y][l[y]], p2 = q[y][l[y] + 1];
lll t = (lll)cal(p2, y) - cal(p1, y);
lll t1 = (lll)h * (w[p2] - w[p1]);
if (t <= t1)
l[y]++;
else
break;
}
int k = q[y][l[y]];
f[x][y + 1] = f[k][y] + sum[x] - sum[k] + h * (w[x] - w[k]);
while (l[y] < r[y]) {
int p1 = q[y][r[y] - 1], p2 = q[y][r[y]];
lll t = (lll)(cal(p2, y) - cal(p1, y)) * (w[x] - w[p2]);
lll t1 = (lll)(cal(x, y) - cal(p2, y)) * (w[p2] - w[p1]);
if (t >= t1)
r[y]--;
else
break;
}
q[y][++r[y]] = x;
}
int main() {
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++) scanf("%d%d", &a[i].second, &a[i].first);
sort(a + 1, a + 1 + n);
reverse(a + 1, a + 1 + n);
for (int i = 1; i <= m; i++) l[i] = r[i] = 1, q[i][1] = 0;
for (int i = 1; i <= n; i++) {
w[i] = w[i - 1] + a[i].second;
sum[i] = sum[i - 1] + a[i].second * a[i].first;
}
for (int i = 1; i <= n; i++) {
f[i][1] = sum[i] - a[i].first * w[i];
for (int j = 2; j <= m; j++) update(i, j - 1);
}
printf("%lld\n", f[n][m]);
return 0;
}

结语

至此, 2019 牛客暑期多校训练营全部补完。补题花了很多时间,但也学到了许多。感谢关注我的各位, 0xfaner 将会继续前行。