分类： 赛事资讯

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

Bessie is using her nifty telescope to take photos of all the stars in the night sky. Her telescope can capture an N×N(1≤N≤1000) photo of the stars where each pixel is either a star or empty sky. Each star will be represented by exactly one pixel, and no two distinct stars share the same pixel.

Overnight, something strange happens to the stars in the sky. Every star either disappears or moves A pixels to the right, and B pixels downwards (0≤A,B≤N
). If a star disappears or moves beyond the photo boundary, it no longer appears in the second photo.

Bessie took photos before and after the shifting positions, but after experimenting in Mootoshop, she accidentally superimposed one photo onto the other. Now, she can see white pixels where both photos were empty, gray pixels where stars existed in exactly one photo, and black pixels where there was a star in both photos. Bessie also remembers that no new stars moved into the frame of the second photo, so her first photo contains all of the stars in the night sky.

Given the final photo, determine the minimum possible number of stars in the sky before the shifting incident for T (1≤T≤1000) independent test cases. If no arrangement of stars can produce the given final photo, output −1.

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

The first line of input contains T and T test cases will follow.

The first line of each test case will contain N A B .

Then follow N lines each representing one row of the superimposed photo. The ith row from the top is represented by a string c_i,1c_i,2…c_i,N, where each c_i,j∈{W,G,B}, representing the colors white, gray, and black respectively.

It is guaranteed that the sum of N² over all test cases will not exceed 10⁷.

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

For each test case, output the minimum number of stars that existed before the shifting, or −1 if impossible.

SAMPLE INPUT:

1
3 0 0
WWB
BBB
GGG

SAMPLE OUTPUT:

7

In this example, there is no shifting. The first photo is as follows: (. for sky, * for star)

..*
***
***

The second photo, where the stars on the bottom row disappeared, is as follows:

..*
***
...

This is the only way to produce the superimposed photo, so the minimum possible number of initial stars is 7.

SAMPLE INPUT:

3
5 1 2
GWGWW
WGWWW
WBWGW
WWWWW
WWGWW
3 1 1
WWW
WBW
WWW
3 1 0
GGB
GGW
WWW

SAMPLE OUTPUT:

4
-1
4

In the first case, there were at least 4 stars at the start. If we let (r,c) denote the intersection of the rth row from the top and cth column from the left, one possibility is that they were initially at (1,1),(3,2),(2,2), and (1,3). All the stars shifted, except for the one at (2,2)which disappeared.

In the second case, there is no arrangement of stars in the initial photo that can produce the middle black pixel given the shift.

In the third case, there were at least 4 stars at the start. One possibility is that they were initially at (1,1),(1,2),(1,3),and (2,1). In the second photo, the star originally at (1,1) disappeared and the star originally at (1,3) moved off frame. The other two stars shifted to the right by 1.

SCORING:

Input 3: A=B=0
Inputs 4-7: A=1,B=0,N≤10
Inputs 8-9: A=1,B=0
Inputs 10-12: No additional constraints.

Problem credits: Suhas Nagar

扫码领取USACO试题答案+详细解析

咨询一对一备赛规划

Bessie has an N×N (1≤N≤1000) addition table where the integer in the cell at row r and column c is r+c, for all 1≤r,c≤N. For example, for N=3, the table would look like this:

2 3 4
3 4 5
4 5 6

Unfortunately, Elsie got ahold of the table and permuted it by performing the following three types of operations as many times as she wanted.

1. Swap two rows
2. Swap two columns
3. Select two values a and b that are both present in the table, then simultaneously change every occurrence of a to b and every occurrence of b to a.

Elsie will always perform operations in increasing order of type; that is, she performs as many operations as she likes (possibly none) first of type 1, then of type 2, and finally of type 3.

Help Bessie recover a possible state of the table after Elsie finished applying all of her operations of types 1 and 2, but before applying any operations of type 3.There may be multiple possible answers, in which case you should output the lexicographically smallest one.

To compare two tables lexicographically, compare the first entries at which they differ, when reading both tables in the natural order (rows from top to bottom, left to right within a row).

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

The first line contains N.

The next N lines each contain N integers, representing Bessie's addition table after Elsie has permuted it.

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

The lexicographically minimum possible state of the table after all operations of types 1 and 2, but before any operations of type 3. It is guaranteed that the answer exists.

SAMPLE INPUT:

1
2

SAMPLE OUTPUT:

2
Regardless of what operations Elsie performs, the table won't change.

SAMPLE INPUT:

3
3 4 2
5 2 3
6 3 5

SAMPLE OUTPUT:

4 2 3
5 3 4
6 4 5

Here is a possible sequence of operations Elsie might have performed.

2 3 4
3 4 5
4 5 6
-> (op 1: swap columns 2 and 3)
2 4 3
3 5 4
4 6 5
-> (op 1: swap columns 1 and 2)
4 2 3
5 3 4
6 4 5
-> (op 3: swap values 2 and 3)
4 3 2
5 2 4
6 4 5
-> (op 3: swap values 3 and 4)
3 4 2
5 2 3
6 3 5

Note: the following is also a possible state of the table after operations of types 1 and 2, but it is not the lexicographically smallest because the second entry of the first row is larger than in the correct answer.

4 6 5
3 5 4
2 4 3

SAMPLE INPUT:

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

SAMPLE OUTPUT:

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

SCORING:

Inputs 4-5: N≤6
Inputs 6-7: N≤8
Inputs 8-11: N≤100
Inputs 12-15: No additional constraints.

Problem credits: Benjamin Qi

扫码领取USACO试题答案+详细解析

咨询一对一备赛规划

It is another cold and boring day on Farmer John's farm. To pass the time, Farmer John has invented a fun leisure activity involving performing operations on an integer array.

Farmer John has an array a of N (1≤N≤2⋅10⁵) non-negative integers and an integer M(1≤M≤10⁹). Then, FJ will ask Bessie for an integer x. In one operation, FJ can pick an index i and subtract or add 1 to a_i. FJ's boredom value is the minimum number of operations he must perform so that a_i−x is divisible by M for all 1≤i≤N.

Among all possible x, output FJ's minimum possible boredom value.

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

The first line contains T (1≤T≤10), the number of independent test cases to solve.

The first line of each test case contains N and M.

The second line of each test case contains a₁,a₂,...,a_N (0≤a_i≤10⁹).

It is guaranteed that the sum of N over all test cases does not exceed 5⋅10⁵.

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

For each test case, output an integer on a new line containing FJ's minimum possible boredom value among all possible values of x.

SAMPLE INPUT:

2
5 9
15 12 18 3 8
3 69
1 988244353 998244853

SAMPLE OUTPUT:

10
21

In the first test case, one optimal choice of x is 3. FJ can perform 10 operations to make a=[12,12,21,3,12].

SCORING:

Input 2: N≤1000 and M≤1000.
Input 3: N≤1000.
Inputs 4-5: M≤10⁵.
Inputs 6-16: No additional constraints.

Problem credits: Chongtian Ma

扫码领取USACO试题答案+详细解析

咨询一对一备赛规划

Farmer John's N (1≤N≤5⋅10⁵) cows are standing in a line, with cow 1
at the front of the line and cow N at the back of the line. FJ's cows also come in many different species. He denotes each species with an integer from 1 to N. The i'th cow from the front of the line is of species a_i (1≤a_i ≤N).

FJ is taking his cows to a checkup at a local bovine hospital. However, the bovine veterinarian is very picky and wants to perform a checkup on the i'th cow in the line, only if it is species b_i (1≤b_i≤N).

FJ is lazy and does not want to completely reorder his cows. He will perform the following operation exactly once.

Select two integers l and r such that 1≤l≤r≤N. Reverse the order of the cows that are between the l-th cow and the r-th cow in the line, inclusive.

FJ wants to measure how effective this approach is. Find the sum of the number of cows that are checked by the veterinarian over all N(N+1)/2 possible operations.

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

The first line contains an integer N.

The second line contains a₁,a₂,…,a_N.

The third line contains b₁,b₂,…,b_N.

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

Output one line with the sum of the number of cows that are checked by the veterinarian over all possible operations.

SAMPLE INPUT:

3
1 3 2
3 2 1

SAMPLE OUTPUT:

3

If FJ chooses (l=1,r=1), (l=2,r=2), or (l=3,r=3) then no cows will be checked. Note that those operations do not modify the location of the cows.

The following operations result in one cow being checked.

• l=1,r=2: FJ reverses the order of the first and second cows so the species of each cow in the new lineup will be [3,1,2]. The first cow will be checked.
• l=2,r=3: FJ reverses the order of the second and third cows so the species of each cow in the new lineup will be [1,2,3]. The second cow will be checked.
• l=1,r=3: FJ reverses the order of the first, second, and third cows so the species of each cow in the new lineup will be [2,3,1]. The third cow will be checked.

The total number of cows checked over all six operations is 0+0+0+1+1+1=3.

SAMPLE INPUT:

3
1 2 3
1 2 3

SAMPLE OUTPUT:

12

There are three possible operations that cause 3 cows to be checked: (l=1,r=1), (l=2,r=2), and (l=3,r=3). The remaining operations each result in 1 cow being checked. The total number of cows checked over all six operations is 3+3+3+1+1+1=12.

SAMPLE INPUT:

7
1 3 2 2 1 3 2
3 2 2 1 2 3 1

SAMPLE OUTPUT:

60

SCORING:

Input 4: N≤100
Input 5: N≤5000
Inputs 6-9:a_i,b_i  are all generated uniformly at random in the range [1,N]
Inputs 10-15:a_i,b_i are all generated uniformly at random in the range [1,2]
Inputs 16-23: No additional constraints.

Problem credits: Chongtian Ma, Haokai Ma, and Alex Liang

扫码领取USACO试题答案+详细解析

咨询一对一备赛规划

Farmer John's farm is full of lush vegetation and every cow wants a photo of its natural beauty. Unfortunately, Bessie still has places to be, but she doesn't want to disrupt any photo ops.

Bessie is currently standing at (X,0) on the XY-plane and she wants to get to (0,Y)
(1≤X,Y≤106). Unfortunately, N (1≤N≤3⋅105 ) other cows have decided to pose on the X axis. More specifically, cow i will be positioned at (xi,0) with a photographer at (0,yi) where (1≤xi,yi≤106) ready to take their picture. They will begin posing moments before time si (1≤si<T) and they will keep posing for a very long time (they have to get their picture just right). Here, 1≤T≤N+1.

Bessie knows the schedule for every cow's photo op, and she will take the shortest Euclidean distance to get to her destination, without crossing the line of sight from any photographer to their respective cow (her path will consist of one or more line segments).

If Bessie leaves at time t , she will avoid the line of sights for all photographer/cow pairs that started posing at time si≤t , and let the distance to her final destination be dt. Determine the values of ⌊dt⌋ for each integer t from 0 to T−1 inclusive.

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

The first line of input contains N and T, representing the number of cows posing on the x-axis and the timeframe that Bessie could leave at.

The second line of input contains X and Y, representing Bessie's starting X coordinate and her target Y coordinate respectively.

The next N lines contain s_i x_i and y_i . It is guaranteed that all xi are distinct from each other and X, and all y_i are distinct from each other and Y. All s_i  will be given in increasing order, where s_i ≤s_i +1.

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

Print T lines, with the t th (0-indexed) line containing ⌊dt⌋.

SAMPLE INPUT:

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

SAMPLE OUTPUT:

9
9
9
10
12

SAMPLE INPUT:

2 3
10 7
1 2 10
1 9 1

SAMPLE OUTPUT:

12
16
16

For t=0 the answer is =12.

For t=1 the answer is =16.

SAMPLE INPUT:

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

SAMPLE OUTPUT:

12
12
12
12
14
14

For t=5 the answer is . Path: (8,0)→(9,0)→(0,7)→(0,9)

SCORING:

Inputs 4-6: N≤100
Inputs 7-9: N≤3000
Inputs 10-12: T≤10
Inputs 13-18: No additional constraints

Problem credits: Suhas Nagar

扫码领取USACO试题答案+详细解析

咨询一对一备赛规划

Consider an undirected graph with N nodes labeled 1…N and M edges (1≤N≤2⋅10⁵,0≤M≤4⋅10⁵). You're given a binary string s1s2…sN. At time t
for each t∈[1,N],

If st=0, node t is removed from the graph.
If st=1, node t is removed from the graph, and edges are added between every pair of neighbors that node t had just before removal.

Note that in both cases, when a node is removed from the graph all of its incident edges are removed as well.

Count the number of pairs of nodes that can reach each other via some sequence of edges just before each of timesteps 1…N.

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

The first line contains N and M.

The second line contains the bit string s of length N.

The next M lines each contain two integers denoting an edge of the graph.

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

N lines, the number of pairs before each timestep.

SAMPLE INPUT:

3 2
111
1 2
1 3

SAMPLE OUTPUT:

3
1
0

Before any removals, all pairs of nodes are reachable from each other. After node 1 is removed, an edge is added between 2 and 3, so they can still reach each other.

SAMPLE INPUT:

3 2
000
1 2
1 3

SAMPLE OUTPUT:

3
0
0

Before any removals, all pairs of nodes are reachable from each other. After node 1 is removed, 2 and 3 can no longer reach each other.

SAMPLE INPUT:

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

SAMPLE OUTPUT:

11
7
4
2
1
1
0

SCORING:

Inputs 4-6: N≤100
Inputs 7-8: All s_i equal zero.
Inputs 9-11: All s_i equal one.
Inputs 12-23: No additional constraints.

Problem credits: Benjamin Qi

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

Farmer John has a binary tree with N nodes where the nodes are numbered from 1 to N (1≤N<2⋅10⁵ and N is odd). For i>1, the parent of node i is ⌊i/2⌋. Each node has an initial integer value a_i, and a cost c_i to change the initial value to any other integer value (0≤a_i,c_i ≤10⁹).

He has been tasked by the Federal Bovine Intermediary (FBI) with finding an approximate median value within this tree, and has devised a clever algorithm to do so.

He starts at the last node N and works his way backward. At every step of the algorithm, if a node would not be the median of it and its two children, he swaps the values of the current node and the child value that would be the median. At the end of this algorithm, the value at node 1 (the root) is the median approximation.

The FBI has also given Farmer John a list of Q (1≤Q≤2⋅10⁵) independent queries each specified by a target value m (0≤m≤10⁹). For each query, FJ will first change some of the node's initial values, and then execute the median approximation algorithm. For each query, determine the minimum possible total cost for FJ to make the output of the algorithm equal to m.

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

The first line of input contains N.

The next N lines each contain two integers a_i and c_i.

The next line contains Q.

The next Q lines each contain a target value m.

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

Output Q lines, the minimum possible total cost for each target value m.

SAMPLE INPUT:

5
10 10000
30 1000
20 100
50 10
40 1
11
55
50
45
40
35
30
25
20
15
10
5

SAMPLE OUTPUT:

111
101
101
100
100
100
100
0
11
11
111

To make the median approximation equal 40, FJ can change the value at node 3 to 60. This costs c₃=100.

To make the median approximation equal 45, FJ can change the value at node 3 to 60 and the value at node 5 to 45. This costs c₃+c₅=100+1=101.

SCORING:

Inputs 2-4: N,Q≤50
Inputs 5-7: N,Q≤1000
Inputs 8-16: No additional constraints

Problem credits: Suhas Nagar and Benjamin Qi

扫码领取USACO试题答案+详细解析

咨询一对一备赛规划

Bessie's garden has N plants labeled 1 through N(2≤N≤5⋅10⁵) from left to right. Bessie knows that plant i requires at least wi (0≤w_i≤10⁶) units of water.

Bessie has a very peculiar irrigation system with N−1 canals, numbered 1 through N−1. Each canal i has an associated unit cost c_i (1≤c_i≤10⁶), such that Bessie can pay cik to provide plants i and i+1 each with k units of water, where k is a non-negative integer.

Bessie is busy and may not have time to use all the canals. For each 2≤i≤N compute the minimum cost required to water plants 1 through i using only the first i−1 canals.

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

The first line contains a single positive integer N.

The second line contains N space-separated integers w₁,…,w_N.

The third line contains N−1 space-separated integers c₁,…,c_N−1.

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

Output N−1 newline-separated integers. The (i−1)th integer should contain the minimum cost to water the first i plants using the first i−1 canals.

SAMPLE INPUT:

3
39 69 33
30 29

SAMPLE OUTPUT:

2070
2127

The minimum cost to water the first 2 plants using the first canal is to pay 30⋅69=2070 by using the first canal 69 times.

The minimum cost to water the first 3 plants is to use the first canal 39 times and the second canal 33 times, paying 39⋅30+29⋅33=2127.

SAMPLE INPUT:

3
33 82 36
19 1

SAMPLE OUTPUT:

1558
676

SAMPLE INPUT:

8
35 89 44 1 35 3 62 50
7 86 94 62 63 9 49

SAMPLE OUTPUT:

623
4099
4114
6269
6272
6827
8827

SCORING:

Input 4: N≤200, and all w_i ≤200.
Inputs 5-6: All w_i ≤200.
Inputs 7-10: N≤5000.
Inputs 11-14: All w_i and c_i are generated independently and uniformly at random.
Inputs 15-19: No additional constraints.

Problem credits: Benjamin Qi

扫码领取USACO试题答案+详细解析

咨询一对一备赛规划

Bessie is experimenting with a powerful hoof implant that has the ability to create massive shock waves. She has N (2≤N≤10⁵) tiles lined up in front of her, which require powers of at least p₀,p₁,…,p_N−1 to break, respectively (0≤p_i≤10¹⁸).

Bessie can apply power by punching a specific tile but due to the strange nature of her implant, it will not apply any power to the tile she punches. Instead, if she chooses to punch tile x once, where x is an integer in [0,N−1], it applies |i−x| power to tile i for all integers i in the range [0,N−1]. This power is also cumulative, so applying 2 power twice to a tile will apply a total of 4 power to the tile.

Please determine the fewest number of punches required to break all the tiles.

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

The first line contains T(1≤T≤100) representing the number of test cases.

Line 2t contains a single integer N, the number of tiles in test case t.

Line 2t+1 contains N space separated numbers p₀,p₁,…,p_N−1 representing that tile i takes p_i  power to be broken.

It is guaranteed that the sum of all N in a single input does not exceed 5⋅10⁵.

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

T lines, the ith line representing the answer to the ith test case.

SAMPLE INPUT:

6
5
0 2 4 5 8
5
6 5 4 5 6
5
1 1 1 1 1
5
12 10 8 6 4
7
6 1 2 3 5 8 13
2
1000000000000000000 1000000000000000000

SAMPLE OUTPUT:

2
3
2
4
4
2000000000000000000

For the first test, the only way for Bessie to break all the tiles with two punches is to punch 0 twice, applying total powers of [0,2,4,6,8] respectively.

For the second test, one way for Bessie to break all the tiles with three punches is to punch 0, 2, and 4 one time each, applying total powers of [6,5,4,5,6] respectively.

For the third test, one way for Bessie to break all the tiles with two punches is to punch 0 and 1 one time each, applying total powers of [1,1,3,5,7] respectively.

SCORING:

Input 2: All p_i are equal.
Inputs 3-6: N≤100
Inputs 7-14: No additional constraints.

Problem credits: Suhas Nagar

扫码领取USACO试题答案+详细解析

咨询一对一备赛规划

Bessie has a simple undirected graph with vertices labeled 1…N(2≤N≤750). She generates a depth-first search (DFS) order of the graph by calling the function dfs(1), defined by the following C++ code. Each adjacency list (adj[i] for all 1≤i≤N) may be permuted arbitrarily before starting the depth first search, so a graph can have multiple possible DFS orders.

vector<bool> vis(N + 1);
vector<vector<int>> adj(N + 1); // adjacency list
vector<int> dfs_order;

void dfs(int x) {
if (vis[x]) return;
vis[x] = true;
dfs_order.push_back(x);
for (int y : adj[x]) dfs(y);
}

You are given the initial state of the graph as well as the cost to change the state of each edge. Specifically, for every pair of vertices (i,j) satisfying 1≤i<j≤N, you are given an integer a_i,j(0<|a_i,j|≤1000) such that

If a_i,j >0, edge (i,j) is not currently in the graph, and can be added for cost a_i,j.
If a_i,j<0, edge (i,j)is currently in the graph, and can be removed for cost −a_i,j.

Determine the minimum total cost to change the graph so that [1,2…,N]
is a possible DFS ordering.

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

The first line contains N.

Then N−1 lines follow. The j−1
th line contains a_1,j ,   a_2,j,…,a_j−1,_j separated by spaces.

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

The minimum cost to change the graph so that [1,2,…,N]
is a possible DFS ordering.

SAMPLE INPUT:

4
1
2 3
40 6 11

SAMPLE OUTPUT:

10

Initially, the graph contains no edges. (1,2),(2,3),(2,4)
can be added for a total cost of 1+3+6. The graph now has two possible DFS orderings: [1,2,3,4],[1,2,4,3].

SAMPLE INPUT:

5
-1
10 -2
10 -7 10
-6 -4 -5 10

SAMPLE OUTPUT:

5

Initially, the graph contains edges (1,2),(2,3),(2,4),(1,5),(2,5),(3,5). Edge (3,5) can be removed for a cost of 5.

SAMPLE INPUT:

4
-1
-2 300
4 -5 6

SAMPLE OUTPUT:

9

Initially, the graph contains edges (1,2),(1,3),(2,4). Edge (2,4)
can be removed and edge (1,4) can be added for a total cost of 5+4=9.

SCORING:

Inputs 4-9: All a_i,j >0
Inputs 10-16: N≤50
Inputs 17-23: No additional constraints.

Problem credits: Benjamin Qi

扫码领取USACO试题答案+详细解析

咨询一对一备赛规划