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

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

A - Garbage Classification

题目描述

On the CVBB planet, garbage classification has been gradually executed to help save resources and protect the environment. Nowadays people have to be equipped with knowledge of distinguishing different types of garbage. Now, given the waste compositions of a discarded product, you are asked to determine which category it belongs to.

The waste compositions are represented as a string s consisting of only lowercase letters, where each letter represents a waste composition and has an equal proportion. Each waste composition in that product is in one of the three situations, dry, wet or harmful.

The product can be classified by the following rules:

  • In case that at least 25% of its compositions is harmful, it is harmful garbage.
  • In case that at most 10% of its compositions is harmful, it is recyclable garbage.
  • In other cases, if the proportion of dry compositions in it is at least twice that of wet compositions, it is dry garbage, or otherwise, it is wet garbage.

输入描述

There are multiple test cases. The first line contains an integer T ( $ 1 \leq T \leq 50 $ ), indicating the number of test cases. Test cases are given in the following.

For each test case, the first line contains a non-empty string $ s $ ( $ 1 \le |s| \le 2000 $ ) consisting of only lowercase letters.

The second line contains a string t of length 26, consisting of only characters in $ \lbrace d, w, h \rbrace $ . The i-th character of t represents the situation of the waste composition denoted by the i-th lowercase letter, where d, w and h mean dry, wet or harmful respectively.

输出描述

For each test case, output Case #x: y in one line (without quotes), where $ x $ indicates the case number starting from $ 1 $ , and $ y $ ( $ y \in \lbrace \text{Harmful}, \text{Recyclable}, \text{Dry}, \text{Wet} \rbrace $ ) denotes the garbage type of the product in this test case.

示例1

输入

1
2
3
4
5
6
7
8
9
4
dqxxjefgctjgdbqxphff
hddhddhhhdhdhwwddhhdwwdhhw
iqdvfzzdqsbdevzebego
wdhddwwhwhdhhhwwdwdhwdwhhd
erkjqzsmchcmbqeasadf
dwddddwdwdwhdwhhdhhwwhhwdh
mcxkwmxxlhbrymwawhio
ddhwhddhwwwdddwdwhwwwhdwdw

输出

1
2
3
4
Case #1: Harmful
Case #2: Recyclable
Case #3: Dry
Case #4: Wet

题解

题意

第一行给出了由小写字母组成的字符串,第二行给出了每个小写字母所代表的垃圾属性(有害,湿,干),根据第二行对第一行的字符串进行判断:

  • 如果其中至少25%的成分是有害的,那就是有害垃圾。
  • 如果它的成分中有10%以上是有害的,那么它就是可回收垃圾。
  • 在其他情况下,如果干成分的比例至少是湿成分的两倍,则为干垃圾,否则为湿垃圾。

解法

统计一下即可。

代码

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;
char a[2001], b[2001];
int main() {
int T;
scanf("%d", &T);
for (int Case = 1; Case <= T; Case++) {
scanf("%s", a + 1);
scanf("%s", b);
int n = strlen(a + 1), num1 = 0, num2 = 0, num3 = 0;
for (int i = 1; i <= n; i++)
if (b[a[i] - 'a'] == 'd')
num1++;
else if (b[a[i] - 'a'] == 'w')
num2++;
else if (b[a[i] - 'a'] == 'h')
num3++;
printf("Case #%d: ", Case);
if (10 * num3 <= n)
puts("Recyclable");
else if (4 * num3 >= n)
puts("Harmful");
else if (num1 >= 2 * num2)
puts("Dry");
else
puts("Wet");
}
return 0;
}

B - Shorten IPv6 Address

题目描述

You are given an IPv6 address which is a 128-bit binary string. Please determine its shortest representation according to the following rules :

Express the address in hexadecimal representation and use a colon ‘:’ to split every four hex digits. Every four digits are called a field. For example, 0000:0000:0123:4567:89ab:0000:0000:0000.

Leading zeros in a field can be omitted. For example, the above IPv6 address can be shortened to 0:0:123:4567:89ab:0:0:0.

Consecutive zero fields (with colons near them) consisting of at least two fields can be replaced by a double colon ‘::’. Besides, no more than one double colon can be used in an address. For example, the above IPv6 address can be shortened to 0:0:123:4567:89ab:: or ::123:4567:89ab:0:0:0, but not ::123:4567:89ab::.

If there are multiple shortest forms of the same length, use the lexicographically (regard the shorten IPv6 address as string) smallest one.

If the above rules conflict with rules in the real world, please refer to the rules mentioned in this problem.

输入描述

There are multiple test cases. The first line contains an integer $ T $ ( $ 1 \leq T \leq 1000 $ ), indicating the number of test cases. Test cases are given in the following.

Each test case consists of only one line, containing a 128-bit binary string.

输出描述

For each test case, output Case #x: y in one line (without quotes), where x indicates the case number starting from 1, and y denotes the answer to this test case.

示例1

输入

1
2
3
4
3
00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000010010001101000101011001111000100110101011000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000010010001100000000000000000000000000000000000000000000000001000101011001111000100110101011

输出

1
2
3
Case #1: ::
Case #2: 0:0:123:4567:89ab::
Case #3: 0:0:123::4567:89ab

题解

题意

将以128位二进制表示的ipv6地址转换格式

解法

模拟即可。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
T=int(input())
for t in range(T):
b=input()
a=[]
for i in range(8):
a.append(hex(int(b[i*16:i*16+16],2))[2:])
s=[]
s.append(':'.join(a))
for i in range(8):
for j in range(i+1,8):
if all(map(lambda x:x=='0',a[i:j+1])):
s.append(':'.join(a[:i])+'::'+':'.join(a[j+1:]))
s.sort(key=lambda x:(len(x),x))
print('Case #%d:'%(t+1),s[0])

C - Palindrome Mouse

题目描述

Doctor has a string s consisting of only lowercase letters. Doctor has got the set of all palindromic substrings of a string s, denoted by the set S. Now, he wants to choose two distinct strings a and b from the set S which satisfy that the string a is a substring of the string b. How many different pairs (a, b) can Doctor choose?

输入描述

There are multiple test cases. The first line contains an integer T ( $ 1 \leq T \leq 5 $ ), indicating the number of test cases. Test cases are given in the following.

Each test case consists of only one line, containing a non-empty string s ( $ 1 \leq |s| \leq 100000 $ ), consisting of only lowercase letters.

输出描述

For each test case, output Case #x: y in one line (without quotes), where x indicates the case number starting from 1, and y denotes the answer to this test case.

示例1

输入

1
2
3
4
5
4
aaaa
abba
abacaba
abc

输出

1
2
3
4
Case #1: 6
Case #2: 4
Case #3: 14
Case #4: 0

题解

题意

给定一个字符串 $ s $ ,询问 $ s $ 所有的本质不同回文子串中有多少对 $ a,b $ 满足 $ a $ 是 $ b $ 的子串。

解法

  • next链:除奇根偶根,所有父亲都是儿子的子串。
  • fail链:父亲是儿子的后缀,所以除奇根偶根所有父亲都是儿子的子串。

于每个节点,答案就是其next链上除根外的父亲个数+fail链上除根外的父亲个数。

但是next链和fail链有时存在交叉,也就是一个回文串既是另一个串的后缀,又在那个串中间出现。于是还要想办法去个重。

在dfs并且对每个节点跳fail树统计的时候标记一下即可。

最后做一个dp:当前节点贡献 = 父亲贡献 + fail链贡献 + 1。

代码

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
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define N 100005
#define inf 0x3f3f3f3f
#define mod 1000000007
struct Palindrome_Tree {
int nex[N][26];
int fail[N], cnt[N], num[N];
int len[N], S[N];
int last, n, p;
int sz[N], c[N], vis[N];
int newnode(int l) {
for (int i = 0; i < 26; i++) nex[p][i] = 0;
cnt[p] = num[p] = 0;
len[p] = l;
return p++;
}
void init() {
p = 0;
newnode(0), newnode(-1);
last = n = 0;
S[n] = -1;
fail[0] = 1;
}
int get_fail(int x) {
while (S[n - len[x] - 1] != S[n]) x = fail[x];
return x;
}
void add(int c) {
c -= 'a';
S[++n] = c;
int cur = get_fail(last);
if (!nex[cur][c]) {
int now = newnode(len[cur] + 2);
fail[now] = nex[get_fail(fail[cur])][c];
nex[cur][c] = now;
num[now] = num[fail[now]] + 1;
}
last = nex[cur][c];
cnt[last]++;
}
void count() {
for (int i = p - 1; i >= 2; i--) cnt[fail[i]] += cnt[i];
}
int dfs(int u) {
sz[u] = 1;
c[u] = 0;
for (int t = u; !vis[t] && t > 1; t = fail[t]) {
vis[t] = u;
c[u]++;
}
for (int i = 0; i < 26; i++) {
if (nex[u][i] == 0) continue;
sz[u] += dfs(nex[u][i]);
}
for (int t = u; vis[t] == u && t > 1; t = fail[t]) {
vis[t] = 0;
}
return sz[u];
}
ll solve() {
dfs(0), dfs(1);
ll ans = 0;
for (int i = 2; i < p; i++) ans += (ll)sz[i] * c[i];
return ans - p + 2;
}
} Tree;
char s[N];
int main() {
int T;
scanf("%d", &T);
for (int Case = 1; Case <= T; Case++) {
scanf("%s", s);
Tree.init();
for (int i = 0; s[i]; i++) Tree.add(s[i]);
printf("Case #%d: %lld\n", Case, Tree.solve());
}
return 0;
}

D - Move

题目描述

After the struggle of graduating from college, TangTang is about to move from a student apartment to his new home.

TangTang has n items to move, the i-th of which is of volume viv_ivi​. He can pack all these items into at most K boxes of the same volume.

TangTang is so clever that he uses the following strategies for packing items:

  • Each time, he would put items into a box by the next strategy, and then he would try to fill another box.
  • For each box, he would put an unpacked item of the largest suitable volume into the box repeatedly until there is no such item that can be fitted in the box.

Now, the question is what is the minimum volume of these boxes required to pack all items.

输入描述

There are multiple test cases. The first line contains an integer $ T $ ( $ 1 \leq T \leq 20 $ ), indicating the number of test cases. Test cases are given in the following.

For each test case, the first line contains two integers $ n, K $ ( $ 1 \leq n, K \leq 1000 $ ), representing the number of items and the number of boxes respectively.

The second line contains n integers $ v_1 $ , $ v_2 $ , $ \ldots $ , $ v_n $ ( $ 1 \leq v_1, v_2, \ldots, v_n \leq 1000 $ ), where the i-th integer viv_ivi represents the volume of the i-th item.

输出描述

For each test case, output Case #x: y in one line (without quotes), where x indicates the case number starting from 1, and y denotes the answer to this test case.

示例1

输入

1
2
3
1
5 3
1 2 3 4 5

输出

1
Case #1: 5

题解

题意

给定 $ n $ 个物品及其体积,用 $ k $ 个相同的箱子装,求能装下这 $ 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
#include <bits/stdc++.h>
using namespace std;
#define N 1001
int a[N], w[N];
int n, m;
bool check(int x) {
int num_box = 0;
memset(w, 0, sizeof(w));
for (int i = n; i > 0; i--) {
bool flag = false;
for (int j = 0; j < num_box && !flag; j++)
if (w[j] + a[i] <= x) w[j] += a[i], flag = true;
if (!flag) w[num_box] = a[i], num_box++;
if (num_box > m) return false;
}
return true;
}
int main() {
int T;
scanf("%d", &T);
for (int Case = 1; Case <= T; Case++) {
int maxn = 0, sum = 0;
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++) {
scanf("%d", &a[i]);
sum += a[i];
maxn = max(a[i], maxn);
}
int ans = max(maxn, sum / m);
sort(a + 1, a + n + 1);
while (!check(ans)) ans++;
printf("Case #%d: %d\n", Case, ans);
}
return 0;
}

E - Androgynos

题目描述

In graph theory, an isomorphism of graphs G and H is a bijection between the vertex sets of G and H. The complement of a graph G is a graph H on the same vertices such that two distinct vertices of H are adjacent if and only if they are not adjacent in G.

Give a positive integer n, check whether there exists a simple undirected graph G having n vertices, which is isomorphic to its complement graph H. If the graphs G and H exist, report them with any possible isomorphism.

输入描述

There are multiple test cases. The first line contains an integer $ T $ ( $ 1 \leq T \leq 5 $ ), indicating the number of test cases. Test cases are given in the following.

Each test case consists of only one line, containing an integer $ n $ ( $ 1 \leq n \leq 2000 $ ).

输出描述

For each test case, output Case #x: y in one line (without quotes), where $ x $ indicates the case number starting from $ 1 $ , and $ y $ ( $ y \in \lbrace \text{Yes}, \text{No} \rbrace $ ) denotes whether or not the graphs exist in this test case.

If the graphs exist, then output ( $ n + 1 $ ) extra lines.

The first $ n $ lines represent the graph G, where each line contains a binary string of length $ n $ . In the $ i $ -th line, the $ j $ -th character $ G_{i, j} $ is 1 when the $ i $ -th vertex and the $ j $ -th one are adjacent, or otherwise, in case they are not adjacent, $ G_{i, j} $ is 0. Note that $ G_{i, i} $ must be 0 and $ G_{i, j} $ must be the same as $ G_{j, i} $ .

The last line contains $ n $ space-separated integers $ f_1 $ , $ f_2 $ , $ \ldots $ , $ f_n $ , representing an isomorphism of graphs G and H in which the $ i $ -th vertex in the graph G is mapped to the $ f_i $ -th vertex in the complement graph H. Note that every two consecutive integers in one line should be separated by a single space, $ \text{please do not add any tailing space in your output} $ .

示例1

输入

1
2
3
4
5
4
1
2
3
4

输出

1
2
3
4
5
6
7
8
9
10
11
Case #1: Yes
0
1
Case #2: No
Case #3: No
Case #4: Yes
0100
1010
0101
0010
2 4 1 3

题解

题意

给定 $ n $ ,要求你在构建出一张图使其包含 $ n $ 个节点,且其补图为该图的一个映射并与该图同构。

解法

https://math.stackexchange.com/questions/40745/constructing-self-complementary-graphs

参考上面论坛,只有 $ k=4n $ 或 $ k=4n+1 $ 时答案不为0.所有的答案都可以通过前面的答案不断 $ +4 $ 得到。

代码

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
#include <bits/stdc++.h>
using namespace std;
int main() {
int T, n;
scanf("%d", &T);
for (int Case = 1; Case <= T; Case++) {
scanf("%d", &n);
if (n % 4 == 2 || n % 4 == 3)
printf("Case #%d: No\n", Case);
else {
printf("Case #%d: Yes\n", Case);
if (n % 4 == 0) {
for (int i = 1; i <= n / 2; ++i) {
for (int j = 1; j <= n / 2; ++j) printf("%d", i != j);
for (int j = 1; j <= n / 2; ++j)
printf("%d", (i <= n / 4 && j <= n / 4) ||
(i >= n / 4 + 1 && j >= n / 4 + 1));
printf("\n");
}
for (int i = 1; i <= n / 2; ++i) {
for (int j = 1; j <= n / 2; ++j)
printf("%d", (i <= n / 4 && j <= n / 4) ||
(i >= n / 4 + 1 && j >= n / 4 + 1));
for (int j = 1; j <= n / 2; ++j) printf("0");
printf("\n");
}
for (int i = 1; i <= n; ++i)
printf("%d%c", i <= n / 2 ? i + n / 2 : n - i + 1,
i == n ? '\n' : ' ');
} else {
for (int i = 1; i <= n / 2; ++i) {
for (int j = 1; j <= n / 2; ++j) printf("%d", i != j);
for (int j = 1; j <= n / 2; ++j)
printf("%d", (i <= n / 4 && j <= n / 4) ||
(i >= n / 4 + 1 && j >= n / 4 + 1));
printf("1\n");
}
for (int i = 1; i <= n / 2; ++i) {
for (int j = 1; j <= n / 2; ++j)
printf("%d", (i <= n / 4 && j <= n / 4) ||
(i >= n / 4 + 1 && j >= n / 4 + 1));
for (int j = 1; j <= n / 2; ++j) printf("0");
printf("0\n");
}
for (int i = 1; i <= n; ++i) printf("%d", i <= n / 2);
printf("\n");
for (int i = 1; i < n; ++i)
printf("%d ", i <= n / 2 ? i + n / 2 : n - i);
printf("%d\n", n);
}
}
}
return 0;
}

F - K-ary Heap

题目描述

A K-ary heap of size n is an array $ [a_0, a_1, \ldots, a_{n - 1}] $ , and for each pair of indices i and j which satisfy $ 0 \leq i \leq n - 1 $ , $ K \cdot i + 1 \leq j \leq \min \lbrace K \cdot i + K, n - 1 \rbrace $ , $ a_j $ is strictly greater than $ a_i $ .

Considering all possible K-ary heaps of size n which are also permutations obtained from 1 to n, let us write down these heaps in lexicographical order, and then label them starting from 1. For example, when $ n = 3, K = 2 $ , there are two possible heaps $ [1, 2, 3] $ and $ [1, 3, 2] $ , which are labeled $ 1 $ and $ 2 $ respectively.

Given a K-ary heap of size n which is also a permutation obtained $ 1 $ to $ n $ , we want you to find the label of this heap after doing the aforementioned process. As the answer can be very large, we request you to report the label modulo $ (10^{9} + 7) $ .

输入描述

There are multiple test cases. The first line contains an integer $ T $ ( $ 1 \leq T \leq 20 $ ), indicating the number of test cases. Test cases are given in the following.

For each test case, the first line contains two integers $ n, K $ ( $ 1 \leq n, K \leq 3000 $ ).

The second line contains n distinct integers $ a_0 $ , $ a_1 $ , $ \ldots $ , $ a_{n - 1} $ ( $ 1 \leq a_0, a_1, \ldots, a_{n - 1} \leq n $ ). We ensure that the given heap is a valid K-ary heap and also a permutation obtained from $ 1 $ to $ n $ .

输出描述

For each test case, output Case #x: y in one line (without quotes), where $ x $ indicates the case number starting from $ 1 $ , and $ y $ denotes the label of the heap in this test case modulo $ (10^{9} + 7) $ .

示例1

输入

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

输出

1
2
3
Case #1: 1
Case #2: 6
Case #3: 151

G - Is Today Friday?

题目描述

No, it’s not Friday :(

TangTang loves Friday and he has made up a list of n days which are all Friday! Each date in this list is formed as yyyy/mm/dd, where yyyy is a four-digit number representing the year, mm is a two-digit number representing the month and dd is a two-digit number representing the day. TangTang only considers years between $ 1600 $ and $ 9999 $ (inclusive), so each year in the list always has four digits, but the months and the days may have leading zeros when it’s necessary. For example, August 3rd, 2019 should be formed as 2019/08/03.

To store safely, TangTang ciphered the list using a simple substitution cipher. He substituted each digit by a letter between A and J such that the same digits correspond to the same letter and different digits to different letters.

Unfortunately, TangTang forgot which letter corresponds to which digit. Please help him restore the original list.

输入描述

There are multiple test cases. The first line contains an integer $ T $ ( $ 1 \leq T \leq 10 $ ), indicating the number of test cases. Test cases are given in the following.

For each test case, the first line contains an integer $ n $ ( $ 1 \leq n \leq 100000 $ ), indicating the number of dates.

Each of the next n lines contains a string in the form of yyyy/mm/dd, representing a ciphered date, where each digit is substituted by an uppercase letter between ‘A’ and ‘J’.

输出描述

For each test case, output Case #x: y in one line (without quotes), where $ x $ indicates the case number starting from $ 1 $ , and $ y $ denotes the answer to this test case.

If there is no way to restore the list, then $ y $ is Impossible.

Otherwise, y is a string consisting of ten distinct digits, representing the key to decipher the list. More specifically, the $ i $ -th digit in y corresponds to the $ i $ -th uppercase letter.

If there are at least two ways, then $ y $ is the smallest possible string in the lexicographical order.

示例1

输入

1
2
3
4
5
6
7
8
9
2
1
CABJ/AI/AC
5
CABJ/AI/AC
CABJ/AI/AD
CABJ/AI/AE
CABJ/AI/AF
CABJ/AI/AG

输出

1
2
Case #1: 0123456789
Case #2: Impossible

题解

题意

给定由 $ A $ 到 $ J $ 组成的字符串, $ A $ 到 $ J $ 唯一代表 $ 0 $ 到 $ 9 $ 中的数字(双射),问是否存在一个合法的双射使得所有的给定的字符串都是星期五(现实中的星期五),并且要使得 $ A $ 到 $ J $ 对应的 $ 0 $ 到 $ 9 $ 的字典序最小 。

解法

运用蔡勒公式,然后从字典序最小的开始全排列一个一个判断

代码

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
#include <bits/stdc++.h>
using namespace std;
#define N 100010
string s[N];
int a[10];
int ds[] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
inline bool check(int y, int m, int d) {
if (y < 1600) return false;
if (m == 0 || m > 12) return false;
int tmp = ds[m];
if (m == 2)
if ((y % 4 == 0 && y % 100 != 0) || y % 400 == 0) tmp = 29;
if (d == 0 || d > tmp) return false;
if (m <= 2) m += 12, y--;
int c = y / 100;
y %= 100;
int w =
((y + y / 4 + c / 4 - 2 * c + (26 * (m + 1)) / 10 + d - 1) % 7 + 7) % 7;
return w == 5;
}
int main() {
int T, n, m;
scanf("%d", &T);
for (int Case = 1; Case <= T; Case++) {
printf("Case #%d: ", Case);
for (int i = 0; i <= 9; i++) a[i] = i;
scanf("%d", &n);
for (int i = 0; i < n; i++) cin >> s[i];
sort(s, s + n);
int realn = unique(s, s + n) - s;
bool flag1 = false;
do {
bool flag2 = true;
for (int i = 0; i < realn; i++) {
int y = a[s[i][0] - 'A'] * 1000 + a[s[i][1] - 'A'] * 100 +
a[s[i][2] - 'A'] * 10 + a[s[i][3] - 'A'];
int m = a[s[i][5] - 'A'] * 10 + a[s[i][6] - 'A'];
int d = a[s[i][8] - 'A'] * 10 + a[s[i][9] - 'A'];
if (!check(y, m, d)) {
flag2 = false;
break;
}
}
if (flag2) {
flag1 = true;
for (int i = 0; i < 10; i++) printf("%d", a[i]);
printf("\n");
break;
}
} while (next_permutation(a, a + 9 + 1));
if (!flag1) printf("Impossible\n");
}
return 0;
}

H - Train Driver

题目描述

It’s time for training! WJJ, DYX and ZZH from the team Nonsense Time want to find a place in BUAA (shorten for Beihang University) to hold their team training. BUAA can be regarded as an undirected connected graph $ G = (V, E) $ with n nodes as places and m edges as routes, where the length of each edge is $ 1 $ .

Since there is no fixed place in BUAA for programming competition training, they have to find a meeting place and make training at that place. They always want to minimize the total distance they need to consume from their previous locations to the meeting place so that they save more energy for training.

However, their previous locations are not always fixed as well. As we know, each of DYX and ZZH is always at one of the places they usually stay at, such as dormitory, canteen, etc., but WJJ may be at anywhere inside BUAA! They constantly need to estimate the total distance they would consume, so they build a statistic model for themselves.

In this model, DYX may show up with equal probability at a node randomly chosen from the set $ A $ , ZZH may show up with equal probability at a node randomly chosen from the set $ B $ , and WJJ may show up with equal probability at a node randomly chosen from BUAA. When they want training, they will find a place to meet such that the total distance can be minimized.

As the coach of Nonsense Time, please help them to calculate the expected minimum total distance based on this model.

输入描述

There are multiple test cases. The first line contains an integer $ T $ ( $ 1 \leq T \leq 5 $ ), indicating the number of test cases. Test cases are given in the following.

For each test case, the first line contains two integers $ n, m $ ( $ 1 \leq n, m \leq 100000 $ ), representing the number of nodes and the number of edges in BUAA respectively.

Each of the next $ m $ lines contains two integers $ u, v $ ( $ 1 \leq u, v \leq n $ ), representing an undirected edge between the u-th node and the $ v $ -th one.

The next line begins with an integer $ S_A $ ( $ 1 \leq S_A \leq \min \lbrace n, 20 \rbrace $ ), indicating the size of the set $ A $ , and then $ S_A $ distinct integers follow, representing the indices of nodes in the set $ A $ .

The last line begins with an integer $ S_B $ ( $ 1 \leq S_B \leq \min \lbrace n, 20 \rbrace $ ), indicating the size of the set $ B $ , and then $ S_B $ distinct integers follow, representing the indices of nodes in the set $ B $ .

We ensure that each given index is ranged from $ 1 $ to $ n $ .

输出描述

For each test case, output Case #x: y in one line (without quotes), where $ x $ indicates the case number starting from $ 1 $ , and y denotes the irreducible fraction form of the answer to this test case. Note that the denominator should be omitted when it equals $ 1 $ .

示例1

输入

1
2
3
4
5
6
7
8
9
10
11
12
13
14
2
4 4
1 2
2 3
1 3
1 4
2 1 2
2 3 4
3 3
1 2
2 3
1 3
3 1 2 3
3 1 2 3

输出

1
2
Case #1: 7/4
Case #2: 10/9

题解

题意

$ n $ 个点 $ m $ 个边,一个人随机出现在集合 $ A $ 中的点里,一个人随机出现在集合 $ B $ 中的点里,还有一个人在整个地图中随机出现。询问这三个人会合在一起的最短路径之和的期望值。

解法

首先暴力预处理,获得集合 $ A,B $ 中每个点到所有点的最短距离是多少。然后对于每种 $ AB $ 的的情况建立一个新点,这个点到各个途中点的距离是此时点 $ A $ 到这个点的距离和点 $ B $ 到这个点距离的和,跑最短路, $ dis_i $ 最后表示的含义就是:在 $ AB $ 情况下第三个点这里的时候三个点加起来的最短路径。所有的情况加起来求 $ gcd $ 。

代码

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
#include <bits/stdc++.h>
using namespace std;
#define ll long long
ll __gcd(ll a, ll b) { return !b ? a : __gcd(b, a % b); }
struct DijNode {
int d, u;
DijNode(int d = 0, int u = 0) : d(d), u(u) {}
};
struct graph {
static const int maxn = 1e5 + 5;
static const int maxm = 2e5 + 5;
struct star {
int v, w, nex;
star(int v = 0, int w = 0, int nex = 0) : v(v), w(w), nex(nex) {}
} edge[maxm];
int head[maxn], tot, n;
int d[maxn];
void init(int _n) {
n = _n;
tot = -1;
memset(head, -1, (n + 1) * sizeof(head[0]));
}
void add_edge(int u, int v, int w) {
edge[++tot] = star(v, w, head[u]);
head[u] = tot;
}
void short_path(queue<DijNode>& q2, int s, int* dist) {
queue<DijNode> q1;
dist[s] = 0;
q1.push(DijNode(dist[s], s));
while (!q1.empty() || !q2.empty()) {
DijNode nd;
if (q1.empty())
nd = q2.front(), q2.pop();
else if (q2.empty())
nd = q1.front(), q1.pop();
else if (q1.front().d < q2.front().d)
nd = q1.front(), q1.pop();
else
nd = q2.front(), q2.pop();
if (nd.d != dist[nd.u]) continue;
int u = nd.u;
for (int i = head[u]; ~i; i = edge[i].nex) {
int v = edge[i].v, w = edge[i].w;
if (dist[u] + w < dist[v]) {
dist[v] = dist[u] + w;
q1.push(DijNode(dist[v], v));
}
}
}
}
} g1;

int n, m;
const int maxn = 1e5 + 55;
int d1[20][maxn], d2[20][maxn];

vector<int> vec[maxn];

ll solve(int p1, int p2) {
queue<DijNode> q;
int mx = 0;
for (int i = 1; i <= n; i++) {
vec[d1[p1][i] + d2[p2][i]].push_back(i);
g1.d[i] = d1[p1][i] + d2[p2][i];
mx = max(mx, g1.d[i]);
}
for (int i = 0; i <= mx; i++)
for (int x : vec[i]) q.push(DijNode{d1[p1][x] + d2[p2][x], x});
for (int i = 1; i <= n; i++) vec[d1[p1][i] + d2[p2][i]].clear();
g1.short_path(q, n + 1, g1.d);
ll sum = 0;
for (int i = 1; i <= n; i++) sum += g1.d[i];
return sum;
}

int main() {
int t;
scanf("%d", &t);
for (int ti = 1; ti <= t; ti++) {
scanf("%d%d", &n, &m);
g1.init(n + 1);
for (int i = 0; i < m; i++) {
int u, v;
scanf("%d%d", &u, &v);
g1.add_edge(u, v, 1);
g1.add_edge(v, u, 1);
}
int s1, s2;
scanf("%d", &s1);
for (int i = 0, v1; i < s1; i++) {
scanf("%d", &v1);
queue<DijNode> q;
for (int j = 1; j <= n; j++) d1[i][j] = 2e9;
g1.short_path(q, v1, d1[i]);
}
scanf("%d", &s2);
for (int i = 0, v2; i < s2; i++) {
scanf("%d", &v2);
queue<DijNode> q;
for (int j = 1; j <= n; j++) d2[i][j] = 2e9;
g1.short_path(q, v2, d2[i]);
}

ll sum = 0;
for (int i = 0; i < s1; i++)
for (int j = 0; j < s2; j++) sum += solve(i, j);
ll fenmu = 1ll * s1 * s2 * n;
ll gcd = __gcd(sum, fenmu);
printf("Case #%d: %lld/%lld\n", ti, sum / gcd, fenmu / gcd);
}
}

I - Can They Go to Galar?

题目描述

Pokemons are planning their travel to the new region Galar. However, it is difficult to allow all of them to go there due to limited funds.

There are $ n $ pokemons all over the world, numbered from $ 1 $ to $ n $ . We decide who can go to Galar according to the following rules.

We start with a cactus (i.e. a connected graph in which every edge belongs to at most one simple cycle) having $ n $ vertices and $ m $ bidirectional edges, where the $ i $ -th vertex represents the pokemon $ i $ and each edge has a probability to go through.

Pokemons go to Galar in rounds. In the first round, only the pokemon $ 1 $ is allowed to go to Galar. In the $ i $ -th round ( $ i = 2, 3, \ldots $ ), if pokemon $ u $ has got the permission to Galar in the ( $ i - 1 $ )-th round, pokemon $ v $ hasn’t got the permission yet, and there is an edge between pokemon $ u $ and pokemon $ v $ with probability $ w $ to go through, then pokemon $ v $ will have a probability $ w $ to go to Galar in this round. If there is no pokemon that can get permission, the further rounds will be skipped. You can see the note after the sample for better understanding of this procedure.

Please calculate the expected population of pokemons that can travel to Galar. In order to avoid precision issues, output the expected value modulo $ 998244353 $ . Formally, let the answer be $ \dfrac{p}{q} $ , you need to output the minimum non-negative integer $ r $ satisfying that $ p \equiv q r \pmod{998244353} $ . For example, $ 9 \equiv 4 \times 748683267 \pmod{998244353} $ .

输入描述

There are multiple test cases. The first line contains an integer $ T $ ( $ 1 \leq T \leq 10 $ ), indicating the number of test cases. Test cases are given in the following.

For each test case, the first line contains two integers $ n, m $ ( $ 0 \leq n, m \leq 100000 $ , $ n \geq 1 $ ), representing the number of vertices and the number of edges in the cactus respectively.

Each of the next $ m $ lines contains four integers $ u, v, a, b $ ( $ 1 \leq u, v \leq n $ , $ 0 \leq a \leq b \leq 10^5 $ , $ b \geq 1 $ ), representing an edge between the $ u $ -th vertex and the $ v $ -th one with probability $ \frac{a}{b} $ to go through. We ensure that the given graph is a cactus with no self-loops or multiple edges.

输出描述

For each test case, output Case #x: y in one line (without quotes), where $ x $ indicates the case number starting from $ 1 $ , and $ y $ denotes the answer to this test case modulo $ 998244353 $ .

示例1

输入

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

输出

1
2
Case #1: 499122178
Case #2: 748683267

说明

In the second example case, there are six possible cases in total as following.

  1. $ \lbrace 1 \rbrace \to \emptyset $ with probability $ \dfrac{1}{4} $ .
  2. $ \lbrace 1 \rbrace \to \lbrace 2 \rbrace \to \emptyset $ with probablity $ \frac{1}{8} $ .
  3. $ \lbrace 1 \rbrace \to \lbrace 2 \rbrace \to \lbrace 3 \rbrace \to \emptyset $ with probablity $ \dfrac{1}{8} $ .
  4. $ \lbrace 1 \rbrace \to \lbrace 3 \rbrace \to \emptyset $ with probablity $ \dfrac{1}{8} $ .
  5. $ \lbrace 1 \rbrace \to \lbrace 3 \rbrace \to \lbrace 2 \rbrace \to \emptyset $ with probablity $ \dfrac{1}{8} $ .
  6. $ \lbrace 1 \rbrace \to \lbrace 2, 3 \rbrace \to \emptyset $ with probablity $ \dfrac{1}{4} $ .

Hence, the answer is $ 1 \times \dfrac{1}{4} + 2 \times \dfrac{1}{8} + 3 \times \dfrac{1}{8} + 2 \times \dfrac{1}{8} + 3 \times \dfrac{1}{8} + 3 \times \dfrac{1}{4} = \dfrac{9}{4} $ .

J - Upgrading Technology

题目描述

Rowlet is playing a very popular game in the pokemon world. Recently, he has encountered a problem and wants to ask for your help.

In this game, there is a technology tree system. There are n kinds of technology in this game, each of them has m levels numbered from $ 1 $ to $ m $ . In the beginning, all technologies have no level (regard as level $ 0 $ ). When the $ i $ -th technology is at the ( $ j - 1 $ )-th level, the player can pay $ c_{i j} $ pokedollars (currency used in this game) to upgrade this technology into the $ j $ -th level. However, sometimes upgrading is so easy that the cost might be negative, which implies the player may gain profit from upgrading technologies.

Moreover, if all technologies have been upgraded to level $ j $ , the player will gain an additional profit of $ d_{j} $ pokedollars. However, sometimes too many technologies of the same level might be confusing, hence the profit can be negative as well.

Rowlet wants to determine the optimal strategy that can bring him the most pokedollars. Help him to find the maximum gain. Note that Rowlet may upgrade nothing, and in that case, the profit is zero.

输入描述

There are multiple test cases. The first line contains an integer $ T $ ( $ 1 \leq T \leq 10 $ ), indicating the number of test cases. Test cases are given in the following.

For each test case, the first line contains two integers $ n, m $ ( $ 1 \leq n, m \leq 1000 $ ), representing the number of technologies and the number of levels respectively.

The $ i $ -th of the next $ n $ lines contains $ m $ integers, where the $ j $ -th number is $ c_{i j} $ ( $ -10^{9} \leq c_{i j} \leq 10^{9} $ ).

The last line contains $ m $ integers, where the $ j $ -th number is $ d_{j} $ ( $ -10^{9} \leq d_{j} \leq 10^{9} $ ).

We ensure that the sum of $ n \cdot m $ in all test cases is at most $ 2 \times 10^{6} $ .

输出描述

For each test case, output Case #x: y in one line (without quotes), where $ x $ indicates the case number starting from $ 1 $ , and $ y $ denotes the answer(in pokedollars) to this test case.

示例1

输入

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

输出

1
2
Case #1: 2
Case #2: 4

说明

In the first example, Rowlet can upgrade the first technology to level $ 1 $ and the second technology to level $ 2 $ , which costs $ 1 + 2 - 1 = 2 $ pokedollars, but Rowlet can get $ 4 $ pokedollars as the bonus of upgrading all technologies to level $ 1 $ , so the answer is $ 4 - 2 = 2 $ pokedollars .

In the second example, Rowlet can upgrade all technologies to level $ 2 $ , which costs $ 1\times3 + 2\times3=9 $ pokedollars, but Rowlet can get $ 6 $ pokedollars as the bonus of upgrading all technologies to level $ 1 $ and $ 7 $ pokedollars as the bonus of upgrading all technologies to level $ 2 $ , so the answer is $ 6 + 7 - 9 = 4 $ pokedollars.

题解

题意

Rowlet在口袋妖怪世界中扮演一个非常受欢迎的游戏。最近,他遇到了一个问题,想要求你的帮助。

在这个游戏中,有一个技术树系统。在这个游戏中有 $ n $ 种技术,每种都有 $ m $ 级,从 $ 1 $ 到 $ m $ 。一开始,所有技术都没有水平(视为 $ 0 $ 级)。当第 $ i $ 个技术处于第( $ j-1 $ )级时,玩家可以支付pokedollars(在这个游戏中使用的货币)来将该技术升级到第 $ j $ 级。但是,有时升级很容易,成本可能是负的,这意味着玩家可以通过升级技术获得利润。

此外,如果所有技术都升级到j级,玩家将获得额外的利润。然而,有时太多相同级别的技术可能会令人困惑,因此利润也可能是负面的。

Rowlet希望确定能够为他带来最多刺激的最佳策略。帮助他找到最大的收益。请注意,Rowlet可能不会升级,在这种情况下,利润为零。

解法

因为实在太复杂我已经忘记我当时是怎么A的了,以后有时间再补吧……

时间复杂度似乎是 $ \mathcal{O}(n \times m) $ .

代码

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;
#define ll long long
#define N 2010
ll c[N][N], s[N][N], h[N][N], d[N];
int main() {
int T, n, m;
scanf("%d", &T);
for (int Case = 1; Case <= T; Case++) {
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++) {
scanf("%lld", &c[i][j]);
s[i][j] = s[i][j - 1] + (c[i][j] = -c[i][j]);
}
for (int i = 1; i <= n; i++) {
h[i][m] = s[i][m];
for (int j = m - 1; j >= 0; j--)
h[i][j] = max(h[i][j + 1], s[i][j]);
}
ll ans = 0, x;
for (int i = 1; i <= m; i++) {
scanf("%lld", &x);
d[i] = d[i - 1] + x;
}
for (int j = 0; j <= m; j++) {
ll sum = d[j], maxn = -2147483647LL * 1000;
for (int i = 1; i <= n; i++) {
sum += h[i][j];
maxn = max(maxn, s[i][j] - h[i][j]);
}
ans = max(ans, sum + maxn);
}
printf("Case #%d: %lld\n", Case, ans);
}
return 0;
}