A. Creating Words
Matthew is given two strings a a a and b b b, both of length 3 3 3. He thinks it’s particularly funny to create two new words by swapping the first character of a a a with the first character of b b b. He wants you to output a a a and b b b after the swap.
Note that the new words may not necessarily be different.
Input
The first line contains t t t ( 1 ≤ t ≤ 100 1 \leq t \leq 100 1≤t≤100) — the number of test cases.
The first and only line of each test case contains two space-separated strings, a a a and b b b, both of length 3 3 3. The strings only contain lowercase Latin letters.
Output
For each test case, after the swap, output a a a and b b b, separated by a space.
Example
| i n p u t \tt input input |
|---|
| 6 bit set cat dog hot dog uwu owo cat cat zzz zzz |
| o u t p u t \tt output output |
| sit bet dat cog dot hog owu uwo cat cat zzz zzz |
Tutorial
交换首字母输出，可以交换后输出，也可以先输出首字母，再输出另一个字符串的后两个字母
此解法时间复杂度为 O ( 1 ) \mathcal O(1) O(1)
Solution
for _ in range(int(input())):
a, b = map(str, input().split())
print(b[0] + a[1:], a[0] + b[1:])
B. Maximum Multiple Sum
Given an integer n n n, find an integer x x x such that:
- 2 ≤ x ≤ n 2 \leq x \leq n 2≤x≤n.
- The sum of multiples of x x x that are less than or equal to n n n is maximized. Formally, x + 2 x + 3 x + ⋯ + k x x + 2x + 3x + \dots + kx x+2x+3x+⋯+kx where k x ≤ n kx \leq n kx≤n is maximized over all possible values of x x x.
Input
The first line contains t t t ( 1 ≤ t ≤ 100 1 \leq t \leq 100 1≤t≤100) — the number of test cases.
Each test case contains a single integer n n n ( 2 ≤ n ≤ 100 2 \leq n \leq 100 2≤n≤100).
Output
For each test case, output an integer, the optimal value of x x x. It can be shown there is only one unique answer.
Example
| i n p u t \tt input input |
|---|
| 2 3 15 |
| o u t p u t \tt output output |
| 3 2 |
Note
For n = 3 n = 3 n=3, the possible values of x x x are 2 2 2 and 3 3 3. The sum of all multiples of 2 2 2 less than or equal to n n n is just 2 2 2, and the sum of all multiples of 3 3 3 less than or equal to n n n is 3 3 3. Therefore, 3 3 3 is the optimal value of x x x.
For n = 15 n = 15 n=15, the optimal value of x x x is 2 2 2. The sum of all multiples of 2 2 2 less than or equal to n n n is 2 + 4 + 6 + 8 + 10 + 12 + 14 = 56 2 + 4 + 6 + 8 + 10 + 12 + 14 = 56 2+4+6+8+10+12+14=56, which can be proven to be the maximal over all other possible values of x x x.
Tutorial
根据题目原理枚举 k k k，暴力的出答案
此解法时间复杂度为 O ( n 2 ) \mathcal O(n ^ 2) O(n2)
Solution
for _ in range(int(input())):
n = int(input())
ans, cnt = 0, 0
for i in range(2, n + 1):
mid = 0
j = 1
while j * i <= n:
mid += i * j
j += 1
if mid > cnt:
ans = i
cnt = mid
print(ans)
C. Good Prefixes
Alex thinks some array is good if there exists some element that can be represented as the sum of all other elements (the sum of all other elements is 0 0 0 if there are no other elements). For example, the array [ 1 , 6 , 3 , 2 ] [1,6,3,2] [1,6,3,2] is good since 1 + 3 + 2 = 6 1+3+2=6 1+3+2=6. Furthermore, the array [ 0 ] [0] [0] is also good. However, the arrays [ 1 , 2 , 3 , 4 ] [1,2,3,4] [1,2,3,4] and [ 1 ] [1] [1] are not good.
Alex has an array a 1 , a 2 , … , a n a_1,a_2,\ldots,a_n a1,a2,…,an. Help him count the number of good non-empty prefixes of the array a a a. In other words, count the number of integers i i i ( 1 ≤ i ≤ n 1 \le i \le n 1≤i≤n) such that the length i i i prefix (i.e. a 1 , a 2 , … , a i a_1,a_2,\ldots,a_i a1,a2,…,ai) is good.
Input
The first line of the input contains a single integer t t t ( 1 ≤ t ≤ 1 0 4 1 \leq t \leq 10^4 1≤t≤104) — the number of test cases.
The first line of each test case contains a single integer n n n ( 1 ≤ n ≤ 2 ⋅ 1 0 5 1 \le n \le 2 \cdot 10^5 1≤n≤2⋅105) — the number of elements in the array.
The second line of each test case contains n n n integers a 1 , a 2 , … , a n a_1,a_2,\ldots,a_n a1,a2,…,an ( 0 ≤ a i ≤ 1 0 9 0 \le a_i \le 10^9 0≤ai≤109) — the elements of the array.
It is guaranteed that the sum of n n n over all test cases does not exceed 2 ⋅ 1 0 5 2 \cdot 10^5 2⋅105.
Output
For each test case, output a single integer — the number of good non-empty prefixes of the array a a a.
Example
| i n p u t \tt input input |
|---|
| 7 1 0 1 1 4 1 1 2 0 5 0 1 2 1 4 7 1 1 0 3 5 2 12 7 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 294967296 10 0 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 589934592 |
| o u t p u t \tt output output |
| 1 0 3 3 4 1 2 |
Note
In the fourth test case, the array has five prefixes:
- prefix [ 0 ] [0] [0] is a good array, as mentioned in the statement;
- prefix [ 0 , 1 ] [0, 1] [0,1] is not a good array, since 0 ≠ 1 0 \ne 1 0=1;
- prefix [ 0 , 1 , 2 ] [0, 1, 2] [0,1,2] is not a good array, since 0 ≠ 1 + 2 0 \ne 1 + 2 0=1+2, 1 ≠ 0 + 2 1 \ne 0 + 2 1=0+2 and 2 ≠ 0 + 1 2 \ne 0 + 1 2=0+1;
- prefix [ 0 , 1 , 2 , 1 ] [0, 1, 2, 1] [0,1,2,1] is a good array, since 2 = 0 + 1 + 1 2 = 0 + 1 + 1 2=0+1+1;
- prefix [ 0 , 1 , 2 , 1 , 4 ] [0, 1, 2, 1, 4] [0,1,2,1,4] is a good array, since 4 = 0 + 1 + 2 + 1 4 = 0 + 1 + 2 + 1 4=0+1+2+1.
As you can see, three of them are good, so the answer is 3 3 3.
Tutorial
由题意得，需要判断在前缀内，最大值等于其他所有元素之和，即判断前缀最大值的两倍是否等于前缀和即可
遍历一遍，动态维护最大值和前缀和即可
此解法时间复杂度为 O ( n ) \mathcal O(n) O(n)
Solution
for _ in range(int(input())):
n = int(input())
a = list(map(int, input().split()))
cnt = 0
ans, mx = 0, 0
for ai in a:
mx = max(mx, ai)
cnt += ai
if cnt - mx == mx:
ans += 1
print(ans)
D. Manhattan Circle
Given a n n n by m m m grid consisting of ‘.’ and ‘#’ characters, there exists a whole manhattan circle on the grid. The top left corner of the grid has coordinates ( 1 , 1 ) (1,1) (1,1), and the bottom right corner has coordinates ( n , m ) (n, m) (n,m).
Point ( a , b a, b a,b) belongs to the manhattan circle centered at ( h , k h, k h,k) if ∣ h − a ∣ + ∣ k − b ∣ < r |h - a| + |k - b| < r ∣h−a∣+∣k−b∣<r, where r r r is a positive constant.
On the grid, the set of points that are part of the manhattan circle is marked as ‘#’. Find the coordinates of the center of the circle.
Input
The first line contains t t t ( 1 ≤ t ≤ 1000 1 \leq t \leq 1000 1≤t≤1000) — the number of test cases.
The first line of each test case contains n n n and m m m ( 1 ≤ n ⋅ m ≤ 2 ⋅ 1 0 5 1 \leq n \cdot m \leq 2 \cdot 10^5 1≤n⋅m≤2⋅105) — the height and width of the grid, respectively.
The next n n n lines contains m m m characters ‘.’ or ‘#’. If the character is ‘#’, then the point is part of the manhattan circle.
It is guaranteed the sum of n ⋅ m n \cdot m n⋅m over all test cases does not exceed 2 ⋅ 1 0 5 2 \cdot 10^5 2⋅105, and there is a whole manhattan circle on the grid.
Output
For each test case, output the two integers, the coordinates of the center of the circle.
Example
| i n p u t \tt input input |
|---|
| 6 5 5 … … …#… … … 5 5 …#… .###. ##### .###. …#… 5 6 … … .#… ###… .#… 1 1 # 5 6 …#… …###. .##### …###. …#… 2 10 … …#… |
| o u t p u t \tt output output |
| 3 3 3 3 4 2 1 1 3 4 2 4 |
Tutorial
先从上往下找到第一个出现 # 的行，此时可以得到中心点的列坐标，然后在那一列寻找 # 出现的上边界和下边界，中心点即为当前列上边界和下边界的中点
此解法时间复杂度为 O ( n 2 ) \mathcal O(n ^ 2) O(n2)
Solution
for _ in range(int(input())):
n, m = map(int, input().split())
g = [input() for __ in range(n)]
y = -1
up, down = -1, -1
for i in range(n):
for j in range(m):
if g[i][j] == '#':
y = j
up = i
break
if y != -1:
break
for i in range(up, n):
if g[i][y] == '#':
down = i
print(((up + down) >> 1) + 1, y + 1)
E. Secret Box
Ntarsis has a box B B B with side lengths x x x, y y y, and z z z. It lies in the 3D coordinate plane, extending from ( 0 , 0 , 0 ) (0,0,0) (0,0,0) to ( x , y , z ) (x,y,z) (x,y,z).
Ntarsis has a secret box S S S. He wants to choose its dimensions such that all side lengths are positive integers, and the volume of S S S is k k k. He can place S S S somewhere within B B B such that:
- S S S is parallel to all axes.
- every corner of S S S lies on an integer coordinate.
S S S is magical, so when placed at an integer location inside B B B, it will not fall to the ground.
Among all possible ways to choose the dimensions of S S S, determine the maximum number of distinct locations he can choose to place his secret box S S S inside B B B. Ntarsis does not rotate S S S once its side lengths are selected.
Input
The first line consists of an integer t t t, the number of test cases ( 1 ≤ t ≤ 2000 1 \leq t \leq 2000 1≤t≤2000). The description of the test cases follows.
The first and only line of each test case contains four integers x , y , z x, y, z x,y,z and k k k ( 1 ≤ x , y , z ≤ 2000 1 \leq x, y, z \leq 2000 1≤x,y,z≤2000, 1 ≤ k ≤ x ⋅ y ⋅ z 1 \leq k \leq x \cdot y \cdot z 1≤k≤x⋅y⋅z).
It is guaranteed the sum of all x x x, sum of all y y y, and sum of all z z z do not exceed 2000 2000 2000 over all test cases.
Note that k k k may not fit in a standard 32-bit integer data type.
Output
For each test case, output the answer as an integer on a new line. If there is no way to select the dimensions of S S S so it fits in B B B, output 0 0 0.
Example
| i n p u t \tt input input |
|---|
| 7 3 3 3 8 3 3 3 18 5 1 1 1 2 2 2 7 3 4 2 12 4 3 1 6 1800 1800 1800 4913000000 |
| o u t p u t \tt output output |
| 8 2 5 0 4 4 1030301 |
Note
For the first test case, it is optimal to choose S S S with side lengths 2 2 2, 2 2 2, and 2 2 2, which has a volume of 2 ⋅ 2 ⋅ 2 = 8 2 \cdot 2 \cdot 2 = 8 2⋅2⋅2=8. It can be shown there are 8 8 8 ways to put S S S inside B B B.
The coordinate with the least x x x, y y y, and z z z values for each possible arrangement of S S S are:
- ( 0 , 0 , 0 ) (0, 0, 0) (0,0,0)
- ( 1 , 0 , 0 ) (1, 0, 0) (1,0,0)
- ( 0 , 1 , 0 ) (0, 1, 0) (0,1,0)
- ( 0 , 0 , 1 ) (0, 0, 1) (0,0,1)
- ( 1 , 0 , 1 ) (1, 0, 1) (1,0,1)
- ( 1 , 1 , 0 ) (1, 1, 0) (1,1,0)
- ( 0 , 1 , 1 ) (0, 1, 1) (0,1,1)
- ( 1 , 1 , 1 ) (1, 1, 1) (1,1,1)
The arrangement of S S S with a coordinate of ( 0 , 0 , 0 ) (0, 0, 0) (0,0,0) is depicted below:
For the second test case, S S S with side lengths 2 2 2, 3 3 3, and 3 3 3 are optimal.
Tutorial
暴力枚举其中两个维度，然后通过除法操作判断第三维是否满足条件，如果满足条件，那么此时 S S S 三边的长度已知，可以根据 B B B 三边的长度分别找到对应维度有多少种放法，相乘判断大小即可
对于一个维度的方法，如果 B B B 当前维度长度为 a a a， S S S 当前维度长度为 b b b，则有 a − b + 1 a - b + 1 a−b+1 种放法
此解法时间复杂度为 O ( max ( x , y , z ) 2 ) \mathcal O(\max(x, y, z) ^ 2) O(max(x,y,z)2)
Solution
for _ in range(int(input())):
ans = 0
x, y, z, k = map(int, input().split())
for i in range(1, x + 1):
for j in range(1, y + 1):
if k % (i * j) == 0 and 1 <= k // (i * j) <= z:
ans = max(ans, (x - i + 1) * (y - j + 1) * (z - k // (i * j) + 1))
print(ans)
F. Final Boss
You are facing the final boss in your favorite video game. The boss enemy has h h h health. Your character has n n n attacks. The i i i’th attack deals a i a_i ai damage to the boss but has a cooldown of c i c_i ci turns, meaning the next time you can use this attack is turn x + c i x + c_i x+ci if your current turn is x x x. Each turn, you can use all attacks that are not currently on cooldown, all at once. If all attacks are on cooldown, you do nothing for the turn and skip to the next turn.
Initially, all attacks are not on cooldown. How many turns will you take to beat the boss? The boss is beaten when its health is 0 0 0 or less.
Input
The first line contains t t t ( 1 ≤ t ≤ 1 0 4 1 \leq t \leq 10^4 1≤t≤104) – the number of test cases.
The first line of each test case contains two integers h h h and n n n ( 1 ≤ h , n ≤ 2 ⋅ 1 0 5 1 \leq h, n \leq 2 \cdot 10^5 1≤h,n≤2⋅105) – the health of the boss and the number of attacks you have.
The following line of each test case contains n n n integers a 1 , a 2 , . . . , a n a_1, a_2, ..., a_n a1,a2,...,an ( 1 ≤ a i ≤ 2 ⋅ 1 0 5 1 \leq a_i \leq 2 \cdot 10^5 1≤ai≤2⋅105) – the damage of your attacks.
The following line of each test case contains n n n integers c 1 , c 2 , . . . , c n c_1, c_2, ..., c_n c1,c2,...,cn ( 1 ≤ c i ≤ 2 ⋅ 1 0 5 1 \leq c_i \leq 2 \cdot 10^5 1≤ci≤2⋅105) – the cooldown of your attacks.
It is guaranteed that the sum of h h h and n n n over all test cases does not exceed 2 ⋅ 1 0 5 2 \cdot 10^5 2⋅105.
Output
For each test case, output an integer, the minimum number of turns required to beat the boss.
Example
| i n p u t \tt input input |
|---|
| 8 3 2 2 1 2 1 5 2 2 1 2 1 50 3 5 6 7 5 6 7 50 3 2 2 2 3 3 3 90000 2 200000 200000 1 1 100000 1 1 200000 6 7 3 2 3 2 3 1 2 6 5 9 5 10 7 7 21 6 1 1 1 1 1 1 5 5 8 10 7 6 |
| o u t p u t \tt output output |
| 1 3 15 25 1 19999800001 1 21 |
Note
For the first test case, you can use attacks 1 1 1 and 2 2 2 on the first turn, dealing 3 3 3 damage in total, and slaying the boss.
For the second case, you can beat the boss in 3 3 3 turns by using the following attacks:
Turn 1 1 1: Use attacks 1 1 1 and 2 2 2, dealing 3 3 3 damage to the boss. The boss now has 2 2 2 health left.
Turn 2 2 2: Use attack 2 2 2, dealing 1 1 1 damage to the boss. The boss now has 1 1 1 health left.
Turn 3 3 3: Use attack 1 1 1, dealing 2 2 2 damage to the boss. The boss now has − 1 -1 −1 health left. Since its health is less than or equal to 0 0 0, you beat the boss.
For the sixth test case: remember to use 64-bit integers as the answer can get large.
Tutorial
可以在第一轮就把所有的攻击使用掉，然后在今后的每一轮，只要冷却一到就将其使用掉，那么可以用堆动态维护下一个结束冷却的攻击，并将其下一次攻击时间计算出来
此解法时间复杂度为 O ( h log h ) \mathcal O(h \log h) O(hlogh)
Solution
import sys
input = lambda: sys.stdin.readline().strip()
from heapq import heappush, heappop
for _ in range(int(input())):
h, n = map(int, input().split())
a = list(map(int, input().split()))
c = list(map(int, input().split()))
q = []
for i in range(n):
h -= a[i]
heappush(q, (c[i], i))
ans = 0
while h > 0:
round, i = heappop(q)
h -= a[i]
heappush(q, (round + c[i], i))
ans = round
print(ans + 1)
G. D-Function
Let D ( n ) D(n) D(n) represent the sum of digits of n n n. For how many integers n n n where 1 0 l ≤ n < 1 0 r 10^{l} \leq n < 10^{r} 10l≤n<10r satisfy D ( k ⋅ n ) = k ⋅ D ( n ) D(k \cdot n) = k \cdot D(n) D(k⋅n)=k⋅D(n)? Output the answer modulo 1 0 9 + 7 10^9+7 109+7.
Input
The first line contains an integer t t t ( 1 ≤ t ≤ 1 0 4 1 \leq t \leq 10^4 1≤t≤104) – the number of test cases.
Each test case contains three integers l l l, r r r, and k k k ( 0 ≤ l < r ≤ 1 0 9 0 \leq l < r \leq 10^9 0≤l<r≤109, 1 ≤ k ≤ 1 0 9 1 \leq k \leq 10^9 1≤k≤109).
Output
For each test case, output an integer, the answer, modulo 1 0 9 + 7 10^9 + 7 109+7.
Example
| i n p u t \tt input input |
|---|
| 6 0 1 4 0 2 7 1 2 1 1 2 3 582 74663 3 0 3 1 |
| o u t p u t \tt output output |
| 2 3 90 12 974995667 999 |
Note
For the first test case, the only values of n n n that satisfy the condition are 1 1 1 and 2 2 2.
For the second test case, the only values of n n n that satisfy the condition are 1 1 1, 10 10 10, and 11 11 11.
For the third test case, all values of n n n between 10 10 10 inclusive and 100 100 100 exclusive satisfy the condition.
Tutorial
根据题意，想要满足 D ( k ⋅ n ) = k ⋅ D ( n ) D(k \cdot n) = k \cdot D(n) D(k⋅n)=k⋅D(n)，就是需要 n n n 的每一位在乘以 k k k 上后都不能进位
对于每一个数位上，一共有 9 k + 1 \frac{9}{k} + 1 k9+1 种可以取的数字，所以此时可以直接前缀和思想，小于 1 0 l 10 ^ l 10l 且满足此情况的有 ( 9 k + 1 ) l (\frac{9}{k} + 1) ^ l (k9+1)l 个数，小于 1 0 r 10 ^ r 10r 且满足此情况的有 ( 9 k + 1 ) r (\frac{9}{k} + 1) ^ r (k9+1)r 个数
所以答案就是 ( 9 k + 1 ) r − ( 9 k + 1 ) l (\frac{9}{k} + 1) ^ r - (\frac{9}{k} + 1) ^ l (k9+1)r−(k9+1)l，最后注意取余即可
此解法时间复杂度为 O ( log r ) \mathcal O(\log r) O(logr)，即快速幂的时间复杂度
Solution
mod = 10 ** 9 + 7 # 998244353
for _ in range(int(input())):
l, r, k = map(int, input().split())
x = 9 // k + 1
print((pow(x, r, mod) - pow(x, l, mod)) % mod)
H1. Maximize the Largest Component (Easy Version)
Easy and hard versions are actually different problems, so read statements of both problems completely and carefully. The only difference between the two versions is the operation.
Alex has a grid with n n n rows and m m m columns consisting of ‘.’ and ‘#’ characters. A set of ‘#’ cells forms a connected component if from any cell in this set, it is possible to reach any other cell in this set by only moving to another cell in the set that shares a common side. The size of a connected component is the number of cells in the set.
In one operation, Alex selects any row r r r ( 1 ≤ r ≤ n 1 \le r \le n 1≤r≤n) or any column c c c ( 1 ≤ c ≤ m 1 \le c \le m 1≤c≤m), then sets every cell in row r r r or column c c c to be ‘#’. Help Alex find the maximum possible size of the largest connected component of ‘#’ cells that he can achieve after performing the operation at most once.
Input
The first line of the input contains a single integer t t t ( 1 ≤ t ≤ 1 0 4 1 \leq t \leq 10^4 1≤t≤104) — the number of test cases.
The first line of each test case contains two integers n n n and m m m ( 1 ≤ n ⋅ m ≤ 1 0 6 1 \le n \cdot m \le 10^6 1≤n⋅m≤106) — the number of rows and columns of the grid.
The next n n n lines each contain m m m characters. Each character is either ‘.’ or ‘#’.
It is guaranteed that the sum of n ⋅ m n \cdot m n⋅m over all test cases does not exceed 1 0 6 10^6 106.
Output
For each test case, output a single integer — the maximum possible size of a connected component of ‘#’ cells that Alex can achieve.
Example
| i n p u t \tt input input |
|---|
| 6 1 1 . 4 2 … #. #. .# 3 5 .#.#. …#… .#.#. 5 5 #…# …# #…# … …## 6 6 .#…#. #…#… .#…# #.#.#. .#.##. ###…# 6 8 …#…# .####.#. ###.#…# .##.#.## .#.##.## #…##.#. |
| o u t p u t \tt output output |
| 1 6 9 11 15 30 |
Note
In the second test case, it is optimal for Alex to set all cells in column 2 2 2 to be ‘#’. Doing so will lead to the largest connected component of ‘#’ having a size of 6 6 6.
In the third test case, it is optimal for Alex to set all cells in row 2 2 2 to be ‘#’. Doing so will lead to the largest connected component of ‘#’ having a size of 9 9 9.
In the fourth test case, it is optimal for Alex to set all cells in row 4 4 4 to be ‘#’. Doing so will lead to the largest connected component of ‘#’ having a size of 11 11 11.
Tutorial
本题需要用到并查集和差分
在最开始需要遍历一遍图，将所有连通块找出来，对于每个连通块可以将其所在的行方向的区间和列方向的区间用差分标记出来，其改变的值为该连通块的大小，然后对差分数组进行一遍前缀和即可得到当前行或当前列连接了多少 #
另外，对于每一行（列），统计如果填充当前行（列），会多出多少 #，此时就可以对行（列）一次遍历找出最大值
此解法时间复杂度为 O ( n m ) \mathcal O(nm) O(nm)
Solution
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define int long long
struct DSU { // 并查集
vector<int> pre, siz;
DSU() {}
DSU(int n) {
pre.resize(n + 1);
std::iota(pre.begin(), pre.end(), 0);
siz.assign(n + 1, 1);
}
int find(int x) {
if (pre[x] == x) {
return x;
}
return pre[x] = find(pre[x]);
}
bool same(int x, int y) {
return find(x) == find(y);
}
bool merge(int x, int y) {
x = find(x);
y = find(y);
if (x == y) {
return false;
}
siz[x] += siz[y];
pre[y] = x;
return true;
}
int size(int x) {
return siz[find(x)];
}
};
void solve() {
int n, m, ans = 0;
cin >> n >> m;
vector<string> g(n);
vector<int> cnt_row(n), cnt_col(m), up(n * m, n), down(n * m, -1), left(n * m, m), right(n * m, -1), diff_row(n), diff_col(m);
for (string &gi : g) {
cin >> gi;
}
DSU dsu(n * m);
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) {
if (i + 1 < n and g[i][j] == '#' and g[i + 1][j] == '#') {
dsu.merge(i * m + j, (i + 1) * m + j);
}
if (j + 1 < m and g[i][j] == '#' and g[i][j + 1] == '#') {
dsu.merge(i * m + j, i * m + j + 1);
}
}
}
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) {
if (g[i][j] == '.') {
cnt_row[i]++;
cnt_col[j]++;
} else {
int u = dsu.find(i * m + j);
up[u] = min(up[u], max(0ll, i - 1));
down[u] = max(down[u], min(n - 1, i + 1));
left[u] = min(left[u], max(0ll, j - 1));
right[u] = max(right[u], min(m - 1, j + 1));
}
}
}
for (int i = 0; i < n * m; ++i) {
if (dsu.find(i) == i and g[i / m][i % m] == '#') {
int sz = dsu.size(i);
diff_row[up[i]] += sz;
if (down[i] + 1 < n) {
diff_row[down[i] + 1] -= sz;
}
diff_col[left[i]] += sz;
if (right[i] + 1 < m) {
diff_col[right[i] + 1] -= sz;
}
}
}
ans = max(diff_row[0] + cnt_row[0], diff_col[0] + cnt_col[0]);
for (int i = 1; i < n; ++i) {
diff_row[i] += diff_row[i - 1];
ans = max(ans, diff_row[i] + cnt_row[i]);
}
for (int j = 1; j < m; ++j) {
diff_col[j] += diff_col[j - 1];
ans = max(ans, diff_col[j] + cnt_col[j]);
}
cout << ans << endl;
}
signed main() {
cin.tie(nullptr)->sync_with_stdio(false);
int Test; cin >> Test; while (Test--)
solve();
return 0;
}
H2. Maximize the Largest Component (Hard Version)
Easy and hard versions are actually different problems, so read statements of both problems completely and carefully. The only difference between the two versions is the operation.
Alex has a grid with n n n rows and m m m columns consisting of ‘.’ and ‘#’ characters. A set of ‘#’ cells forms a connected component if from any cell in this set, it is possible to reach any other cell in this set by only moving to another cell in the set that shares a common side. The size of a connected component is the number of cells in the set.
In one operation, Alex selects any row r r r ( 1 ≤ r ≤ n 1 \le r \le n 1≤r≤n) and any column c c c ( 1 ≤ c ≤ m 1 \le c \le m 1≤c≤m), then sets every cell in row r r r and column c c c to be ‘#’. Help Alex find the maximum possible size of the largest connected component of ‘#’ cells that he can achieve after performing the operation at most once.
Input
The first line of the input contains a single integer t t t ( 1 ≤ t ≤ 1 0 4 1 \leq t \leq 10^4 1≤t≤104) — the number of test cases.
The first line of each test case contains two integers n n n and m m m ( 1 ≤ n ⋅ m ≤ 1 0 6 1 \le n \cdot m \le 10^6 1≤n⋅m≤106) — the number of rows and columns of the grid.
The next n n n lines each contain m m m characters. Each character is either ‘.’ or ‘#’.
It is guaranteed that the sum of n ⋅ m n \cdot m n⋅m over all test cases does not exceed 1 0 6 10^6 106.
Output
For each test case, output a single integer — the maximum possible size of a connected component of ‘#’ cells that Alex can achieve.
Example
| i n p u t \tt input input |
|---|
| 6 1 1 . 4 2 … #. #. .# 3 5 .#.#. …#… .#.#. 5 5 #…# …# #…# … …## 6 6 .#…#. #…#… .#…# #.#.#. .#.##. ###…# 6 8 …#…# .####.#. ###.#…# .##.#.## .#.##.## #…##.#. |
| o u t p u t \tt output output |
| 1 7 11 16 22 36 |
Note
In the fourth test case, it is optimal for Alex to set all cells in row 4 4 4 and column 2 2 2 to be ‘#’. Doing so will lead to the largest connected component of ‘#’ having a size of 16 16 16.
In the fifth test case, it is optimal for Alex to set all cells in row 2 2 2 and column 4 4 4 to be ‘#’. Doing so will lead to the largest connected component of ‘#’ having a size of 22 22 22.
Tutorial
本题需要用到并查集和二维差分，整体思维与 H1 相似
在最开始需要遍历一遍图，将所有连通块找出来，对于每个连通块可以将其所在的行方向的区间和列方向的区间用二维差分标记出来，其改变的值为该连通块的大小，然后在行方向和列方向对差分数组进行一遍二维前缀和即可得到当前位置的行和列连接了多少 #
另外，对于每一行（列），统计如果填充当前行（列），会多出多少 #，此时就可以对行（列）一次遍历找出最大值
此解法时间复杂度为 O ( n m ) \mathcal O(nm) O(nm)
UPD：搞不清二维差分的可以自己画一下图手推一下，例如下图
Solution
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define int long long
struct DSU { // 并查集
vector<int> pre, siz;
DSU() {}
DSU(int n) {
pre.resize(n + 1);
std::iota(pre.begin(), pre.end(), 0);
siz.assign(n + 1, 1);
}
int find(int x) {
if (pre[x] == x) {
return x;
}
return pre[x] = find(pre[x]);
}
bool same(int x, int y) {
return find(x) == find(y);
}
bool merge(int x, int y) {
x = find(x);
y = find(y);
if (x == y) {
return false;
}
siz[x] += siz[y];
pre[y] = x;
return true;
}
int size(int x) {
return siz[find(x)];
}
};
void solve() {
int n, m, ans = 0;
cin >> n >> m;
vector<string> g(n);
vector<int> cnt_row(n), cnt_col(m), up(n * m, n), down(n * m, -1), left(n * m, m), right(n * m, -1);
vector diff(n, vector<int>(m));
for (string &gi : g) {
cin >> gi;
}
DSU dsu(n * m);
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) {
if (i + 1 < n and g[i][j] == '#' and g[i + 1][j] == '#') {
dsu.merge(i * m + j, (i + 1) * m + j);
}
if (j + 1 < m and g[i][j] == '#' and g[i][j + 1] == '#') {
dsu.merge(i * m + j, i * m + j + 1);
}
}
}
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) {
if (g[i][j] == '.') {
cnt_row[i]++;
cnt_col[j]++;
} else {
int u = dsu.find(i * m + j);
up[u] = min(up[u], max(0ll, i - 1));
down[u] = max(down[u], min(n - 1, i + 1));
left[u] = min(left[u], max(0ll, j - 1));
right[u] = max(right[u], min(m - 1, j + 1));
}
}
}
for (int i = 0; i < n * m; ++i) {
if (dsu.find(i) == i and g[i / m][i % m] == '#') {
int sz = dsu.size(i);
diff[up[i]][left[i]] -= sz;
diff[up[i]][0] += sz;
diff[0][left[i]] += sz;
if (down[i] + 1 < n) {
diff[down[i] + 1][left[i]] += sz;
diff[down[i] + 1][0] -= sz;
if (right[i] + 1 < m) {
diff[down[i] + 1][right[i] + 1] -= sz;
}
}
if (right[i] + 1 < m) {
diff[up[i]][right[i] + 1] += sz;
diff[0][right[i] + 1] -= sz;
}
}
}
for (int i = 0; i < n; ++i) {
for (int j = 1; j < m; ++j) {
diff[i][j] += diff[i][j - 1];
}
}
for (int i = 1; i < n; ++i) {
for (int j = 0; j < m; ++j) {
diff[i][j] += diff[i - 1][j];
}
}
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) {
ans = max(ans, diff[i][j] + cnt_row[i] + cnt_col[j] - (g[i][j] == '.'));
}
}
cout << ans << endl;
}
signed main() {
cin.tie(nullptr)->sync_with_stdio(false);
int Test; cin >> Test; while (Test--)
solve();
return 0;
}