分类： 赛事资讯

Pareidolia is the phenomenon where your eyes tend to see familiar patterns in images where none really exist -- for example seeing a face in a cloud. As you might imagine, with Farmer John's constant proximity to cows, he often sees cow-related patterns in everyday objects. For example, if he looks at the string "bqessiyexbesszieb", Farmer John's eyes ignore some of the letters and all he sees is "bessiexbessieb" -- a string that has contains two contiguous substrings equal to "bessie".

Given a string of length at most 2⋅105 consisting only of characters a-z, where each character has an associated deletion cost, compute the maximum number of contiguous substrings that equal "bessie" you can form by deleting zero or more characters from it, and the minimum total cost of the characters you need to delete in order to do this.

INPUT FORMAT (input arrives from the terminal / stdin):
The first line contains the string. The second line contains the deletion cost associated with each character (an integer in the range [1,1000]).
OUTPUT FORMAT (print output to the terminal / stdout):
The maximum number of occurrences, and the minimum cost to produce this number of occurrences.

SAMPLE INPUT:

besssie
1 1 5 4 6 1 1

SAMPLE OUTPUT:

1
4

By deleting the 's' at position 4 we can make the whole string "bessie". The character at position 4 has a cost of 4, so our answer is cost 4 for 1 instance of "bessie", which is the best we can do.

SAMPLE INPUT:

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

SAMPLE OUTPUT:

1
21

By deleting the "con" at positions 5-7, we can make the string "bebessiete" which has "bessie" in the middle. Characters 5-7 have costs 5+7+9=21, so our answer is cost 21 for 1 instance of "bessie", which is the best we can do.

SAMPLE INPUT:

besgiraffesiebessibessie
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1

SAMPLE OUTPUT:

2
7
This sample satisfies the constraints for the second subtask.

By deleting the "giraffe" at positions 4-10, we can make the string "bessiebessibessie", which has "bessie" at the beginning and the end. "giraffe" has 7 characters and all characters have cost 1, so our answer is cost 7 for 2 instances of "bessie", which is the best we can do.

SCORING:

Inputs 4-5: N≤2000
Inputs 6-8: All costs are 1
Inputs 9-17: No additional constraints.
Problem credits: Benjamin Qi

Having just completed a course in graph algorithms, Bessie the cow has begun coding her very own graph visualizer! Currently, her graph visualizer is only capable of visualizing rooted trees with nodes of distinct values, and it can only perform one kind of operation: merging.

In particular, a merging operation takes any two distinct nodes in a tree with the same parent and merges them into one node, with value equal to the maximum of the values of the two nodes merged, and children a union of all the children of the nodes merged (if any).

Unfortunately, after Bessie performed some merging operations on a tree, her program crashed, losing the history of the merging operations she performed. All Bessie remembers is the tree she started with and the tree she ended with after she performed all her merging operations.

Given her initial and final trees, please determine a sequence of merging operations Bessie could have performed. It is guaranteed that a sequence exists.

Each input consists of T (1≤T≤100) independent test cases. It is guaranteed that the sum of N over all test cases does not exceed 1000.

INPUT FORMAT (input arrives from the terminal / stdin):

The first line contains T, the number of independent test cases. Each test case is formatted as follows.
The first line of each test case contains the number of nodes N (2≤N≤1000) in Bessie's initial tree, which have values 1…N.

Each of the next N−1 lines contains two space-separated node values vi and pi (1≤vi,pi≤N) indicating that the node with value vi is a child node of the node with value pi in Bessie's initial tree.

The next line contains the number of nodes M (2≤M≤N) in Bessie's final tree.

Each of the next M−1 lines contains two space-separated node values vi and pi (1≤vi,pi≤N) indicating that the node with value vi is a child node of the node with value pi in Bessie's final tree.

OUTPUT FORMAT (print output to the terminal / stdout):

For each test case, output the number of merging operations, followed by an ordered sequence of merging operations of that length, one per line.
Each merging operation should be formatted as two distinct space-separated integers: the values of the two nodes to merge in any order.

If there are multiple solutions, output any.

SAMPLE INPUT:

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

SAMPLE OUTPUT:

4
2 5
4 8
3 8
7 8

SCORING:

Inputs 2-6: The initial and final trees have the same number of leaves.
Inputs 7-16: No additional constraints.
Problem credits: Aryansh Shrivastava

Due to the disorganized structure of his mootels (much like motels but with bovine rather than human guests), Farmer John has decided to take up the role of the mootel custodian to restore order to the stalls.

Each mootel has N stalls labeled 1 through N (1≤N≤105) and M (0≤M≤105) corridors that connect pairs of stalls to each other bidirectionally. The ith stall is painted with color Ci and initially has a single key of color Si in it. FJ will have to rearrange the keys to appease the cows and restore order to the stalls.

FJ starts out in stall 1 without holding any keys and is allowed to repeatedly do one of the following moves:

Pick up a key in the stall he is currently in. FJ can hold multiple keys at a time.
Place down a key he is holding into the stall he is currently in. A stall may hold multiple keys at a time.
Enter stall 1 by moving through a corridor.
Enter a stall other than stall 1 by moving through a corridor. He can only do this if he currently holds a key that is the same color as the stall he is entering.
Unfortunately, it seems that the keys are not in their intended locations. To restore order to FJ's mootel, the ith stall requires that a single key of color Fi is in it. It is guaranteed that S is a permutation of F.

For T different mootels (1≤T≤100), FJ starts in stall 1 and needs to place every key in its appropriate location, ending back in stall 1. For each of the T mootels, please answer if it is possible to do this.

INPUT FORMAT (input arrives from the terminal / stdin):
The first line contains T, the number of mootels (test cases).
Each test case will be preceded by a blank line. Then, the first line of each test case contains two integers N and M.

The second line of each test case contains N integers. The i-th integer on this line, Ci, means that stall i has color Ci (1≤Ci≤N).

The third line of each test case contains N integers. The i-th integer on this line, Si, means that stall i initially holds a key of color Si (1≤Si≤N).

The fourth line of each test case contains N integers. The i-th integer on this line, Fi, means that stall i needs to have a key of color Fi in it (1≤Fi≤N).

The next M lines of each test case follow. The i-th of these lines contains two distinct integers, ui and vi (1≤ui,vi≤N). This represents that a corridor exists between stalls ui and vi. No corridors are repeated.

The sum of N over all mootels will not exceed 105, and the sum of M over all mootels will not exceed 2⋅105.

OUTPUT FORMAT (print output to the terminal / stdout):

For each mootel, output YES on a new line if there exists a way for FJ to return a key of color Fi to each stall i and end back in stall 1. Otherwise, output NO on a new line.

SAMPLE INPUT:
2

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

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

SAMPLE OUTPUT:

YES
NO
For the first test case, here is a possible sequence of moves:

Current stall: 1. Keys held: []. Keys in stalls: [3, 4, 3, 4, 2]
(pick up key of color 3)
Current stall: 1. Keys held: [3]. Keys in stalls: [x, 4, 3, 4, 2]
(move from stall 1 to 2, allowed since we have a key of color C_2=3)
Current stall: 2. Keys held: [3]. Keys in stalls: [x, 4, 3, 4, 2]
(pick up key of color 4)
Current stall: 2. Keys held: [3, 4]. Keys in stalls: [x, x, 3, 4, 2]
(move from stall 2 to 1 to 4 to 5, allowed since we have keys of colors C_4=4 and C_5=3)
Current stall: 5. Keys held: [3, 4]. Keys in stalls: [x, x, 3, 4, 2]
(pick up key of color 2 and place key of color 3)
Current stall: 5. Keys held: [2, 4]. Keys in stalls: [x, x, 3, 4, 3]
(move from stall 5 to 4 to 1 to 3, allowed since we have keys of colors C_4=4 and C_3=2)
Current stall: 3. Keys held: [2, 4]. Keys in stalls: [x, x, 3, 4, 3]
(pick up key of color 3 and place key of color 4)
Current stall: 3. Keys held: [2, 3]. Keys in stalls: [x, x, 4, 4, 3]
(move from stall 3 to stall 2 and place key of color 3)
Current stall: 2. Keys held: [2]. Keys in stalls: [x, 3, 4, 4, 3]
(move from stall 2 to stall 1 and place key of color 2)
Current stall: 1. Keys held: []. Keys in stalls: [2, 3, 4, 4, 3]
For the second test case, there exists no way for FJ to return a key of color Fi to each stall i and end back at stall 1.

SAMPLE INPUT:

5

2 0
1 2
2 2
2 2

2 1
1 1
2 1
2 1
1 2

2 1
1 1
2 1
1 2
1 2

2 1
1 1
1 2
2 1
1 2

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

SAMPLE OUTPUT:

YES
YES
NO
YES
NO

SCORING:

Test cases 3-6 satisfy N,M≤8.
Test cases 7-10 satisfy Ci=Fi.
Test cases 11-18 satisfy no additional constraints.
Problem credits: Eric Yachbes

There are initially N−1 pairs of friends among FJ's N (2≤N≤2⋅105) cows labeled 1…N, forming a tree. The cows are leaving the farm for vacation one by one. On day i, the ith cow leaves the farm, and then all pairs of the ith cow's friends still present on the farm become friends.

For each i from 1 to N, just before the ith cow leaves, how many ordered triples of distinct cows (a,b,c) are there such that none of a,b,c are on vacation, a is friends with b, and b is friends with c?

INPUT FORMAT (input arrives from the terminal / stdin):

The first line contains N.
The next N−1 lines contain two integers ui and vi denoting that cows ui and vi are initially friends (1≤ui,vi≤N).

OUTPUT FORMAT (print output to the terminal / stdout):

The answers for i from 1 to N on separate lines.

SAMPLE INPUT:
3
1 2
2 3

SAMPLE OUTPUT:
2
0
0
(1,2,3) and (3,2,1) are the triples just before cow 1 leaves.

After cow 1 leaves, there are less than 3 cows left, so no triples are possible.

SAMPLE INPUT:

4
1 2
1 3
1 4

SAMPLE OUTPUT:

6
6
0
0
At the beginning, cow 1 is friends with all other cows, and no other pairs of cows are friends, so the triples are (a,1,c) where a,c are different cows from {2,3,4}, which gives 3⋅2=6 triples.

After cow 1 leaves, the remaining three cows are all friends, so the triples are just those three cows in any of the 3!=6 possible orders.

After cow 2 leaves, there are less than 3 cows left, so no triples are possible.

SAMPLE INPUT:

5
3 5
5 1
1 4
1 2

SAMPLE OUTPUT:
8
10
2
0
0

SCORING:

Inputs 4-5: N≤500
Inputs 6-10: N≤5000
Inputs 11-20: No additional constraints.
Problem credits: Aryansh Shrivastava, Benjamin Qi

For any two positive integers a and b, define the function gen_string(a,b) by the following Python code:

def gen_string(a: int, b: int):
	res = ""
	ia, ib = 0, 0
	while ia + ib < a + b:
		if ia * b <= ib * a:
			res += '0'
			ia += 1
		else:
			res += '1'
			ib += 1
	return res

Equivalent C++ code:

string gen_string(int64_t a, int64_t b) {
	string res;
	int ia = 0, ib = 0;
	while (ia + ib < a + b) {
		if ((__int128)ia * b <= (__int128)ib * a) {
			res += '0';
			ia++;
		} else {
			res += '1';
			ib++;
		}
	}
	return res;
}

ia will equal a and ib will equal b when the loop terminates, so this function returns a bitstring of length a+b with exactly a zeroes and b ones. For example, gen_string(4,10)=01110110111011.

Call a bitstring s good if there exist positive integers x and y such that s=gen_string(x,y). Given two positive integers A and B (1≤A,B≤1018), your job is to compute the number of good prefixes of gen_string(A,B). For example, there are 6 good prefixes of gen_string(4,10):

x = 1 | y = 1 | gen_string(x, y) = 01
x = 1 | y = 2 | gen_string(x, y) = 011
x = 1 | y = 3 | gen_string(x, y) = 0111
x = 2 | y = 5 | gen_string(x, y) = 0111011
x = 3 | y = 7 | gen_string(x, y) = 0111011011
x = 4 | y = 10 | gen_string(x, y) = 01110110111011

INPUT FORMAT (input arrives from the terminal / stdin):

The first line contains T (1≤T≤10), the number of independent test cases.
Each of the next T lines contains two integers A and B.

OUTPUT FORMAT (print output to the terminal / stdout):

The answer for each test case on a new line.

SAMPLE INPUT:

6
1 1
3 5
4 7
8 20
4 10
27 21

SAMPLE OUTPUT:

1
5
7
10
6
13

SCORING:

Input 2: A,B≤100
Input 3: A,B≤1000
Inputs 4-7: A,B≤106
Inputs 8-13: All answers are at most 105.
Inputs 14-21: No additional constraints.
Problem credits: Benjamin Qi

Note: The time limit for this problem is 4s, twice the default. The memory limit for this problem is 512MB, twice the default.

Pareidolia is the phenomenon where your eyes tend to see familiar patterns in images where none really exist -- for example seeing a face in a cloud. As you might imagine, with Farmer John's constant proximity to cows, he often sees cow-related patterns in everyday objects. For example, if he looks at the string "bqessiyexbesszieb", Farmer John's eyes ignore some of the letters and all he sees is "bessiebessie".

Given a string s, let B(s)represent the maximum number of repeated copies of "bessie" one can form by deleting zero or more of the characters from s. In the example above, B("bqessiyexbesszieb")=2. Furthermore, given a string t, let A(t)
represent the sum of B(s)over all contiguous substrings s of t.

Farmer John has a string t of length at most 2⋅10⁵consisting only of characters a-z. Please compute A(t), and how A(t) would change after U(1≤U≤2⋅105) updates, each changing a character of t. Updates are cumulative.

INPUT FORMAT (input arrives from the terminal / stdin):

The first line of input contains t.

The next line contains U, followed by U lines each containing a position p
(1≤p≤N) and a character c in the range a-z, meaning that the pth character of t
is changed to c.

OUTPUT FORMAT (print output to the terminal / stdout):

Output U+1 lines, the total number of bessies that can be made across all substrings of t before any updates and after each update.

SAMPLE INPUT:

bessiebessie
3
3 l
7 s
3 s

SAMPLE OUTPUT:

14
7
1
7
Before any updates, twelve substrings contain exactly 1 "bessie" and 1 string contains exactly 2 "bessie"s, so the total number of bessies is 12⋅1+1⋅2=14.

After one update, t is "belsiebessie." Seven substrings contain exactly one "bessie."

After two updates, t is "belsiesessie." Only the entire string contains "bessie."

SCORING:

Input 2: |t|,U≤300
Inputs 3-5: U≤10
Inputs 6-13: |t|,U≤105
Inputs 14-21: No additional constraints.
Problem credits: Brandon Wang and Benjamin Qi