[CF Replay] Codeforces Round 874 (Div. 3 20230520
-
- Summarize
- A. Musical Puzzle
-
- 2. Thinking analysis
- 3. Code implementation
- B. Restore the Weather
-
- 1. Description of the topic
- 2. Thinking analysis
- 3. Code implementation
- C. Vlad Building Beautiful Array
-
- 1. Description of the topic
- 2. Thinking analysis
- 3. Code implementation
- D. Flipper
-
- 1. Description of the topic
- 2. Thinking analysis
- 3. Code implementation
- E. Round Dance
-
- 1. Description of the topic
- 2. Thinking analysis
- 3. Code implementation
- F. Ira and Flamenco
-
- 1. Description of the topic
- 2. Thinking analysis
- 3. Code implementation
Summary
- G seems to have been out of lc, and F is stuck for an hour, and G doesn’t want to make up.
- A simulation
- B greedy
- C simulation
- D greedy + category discussion
- E greedy + union check
- F inverse element + prefix multiplication
A. Musical Puzzle
2. Thinking Analysis
3. Code implementation
PROBLEM = """Using a string of length 2 to combine the entire string s, how many different strings are needed
"""
# ms
def solve():
n, = RI()
s, = RS()
p = set()
for i in range(n - 1):
p. add(s[i:i + 2])
print(len(p))
B. Restore the Weather
Link: B. Restore the Weather
1. Title description
2. Thinking Analysis
3. Code implementation
PROBLEM = """Input n, k and array a, b of length n.
a[i] represents the predicted temperature for the i-th day.
b[i] represents the actual temperature of day i. But b is messed up.
It is known that the daily abs (predicted value - actual value) <= k.
Please restore a correct b. Data Guaranteed
"""
"""Greedy thinking, just match large or small values first. Since the data is guaranteed to have a solution, k is actually useless.
For the convenience of the code, start matching from the big one, so that b can always pop
"""
# ms
def solve():
n, k = RI()
a = RILST()
b = RILST()
b. sort()
ans = [0] * n
for i in sorted(range(n), key=lambda x: -a[x]):
ans[i] = b. pop()
print(*ans)
C. Vlad Building Beautiful Array
Link: C. Vlad Building Beautiful Array
1. Title description
2. Thinking Analysis
3. Code implementation
PROBLEM = """Enter n and n positive integers a[i].
Constructs an array b of length n.
Where b[i] is either equal to a[i], or equal to a[i]-a[j]. Among them, j randomly chooses 1~n.
It is required that all data in b have the same parity.
"""
"""Try odd or even numbers respectively.
The spirit of this question has also explored more properties. In fact, the code can be very short, and only the smallest odd number can be discussed.
But there is no need to dig deep in the competition, just write directly"""
# ms
def solve():
n, = RI()
a = RILST()
even, odd = [], []
for v in a:
if v & 1:
odd.append(v)
else:
even.append(v)
if not even or not odd:
return print("YES")
even. sort()
odd. sort()
def try_1():
for i, v in enumerate(a):
if v & 1:
continue
if odd[0] >= v:
return False
return True
def try_2():
for i, v in enumerate(a):
if not v & 1:
continue
if odd[0] >= v:
return False
return True
if try_1() or try_2():
return print("YES")
print("NO")
D. Flipper
Link: D. Flipper
1. Title description
2. Thinking Analysis
3. Code implementation
PROBLEM = """Gives a permutation p of length n. You must do the following exactly once:
1. Select a sub-segment [l, r], (1<=l<=r<=n) flip this segment.
2. Exchange the data on both sides of this segment. That is, exchange [1~l-1], [r + 1, n], note that these two paragraphs can be empty
The p with the largest lexicographical order after the output operation
"""
"""Greedy, just enumerate l. Pay attention to the discussion
- First find the position pos of the largest number, namely n, let pos be r, and enumerate l. If n is at the end, it can be used as r and flipped to 0 directly.
- If n is on 0, since it must be flipped once, n must go backwards, then let n-1 go to 0, the method is the same as before.
---
- This question also has an O(n) approach. You can watch the video of Spirit God.
After finding pos, the front segment is actually unchanged, and r is also unchanged after flipping. Just discuss r-1.
"""
# ms
def solve():
n, = RI()
p = RILST()
if n == 1:
return print(1)
ans = p[::-1]
pos = p. index(n)
if pos:
ans = max(ans, p[pos + 1:] + p[pos:] + p[:pos])
mx = []
r = pos
for l in range(pos):
mx = max(mx, p[l:r][::-1] + p[:l])
ans = max(ans, p[pos:] + mx)
else:
pos = p.index(n - 1)
ans = max(ans, p[pos + 1:] + p[pos:] + p[:pos])
mx = []
r = pos
for l in range(pos):
mx = max(mx, p[l:r][::-1] + p[:l])
ans = max(ans, p[pos:] + mx)
print(*ans)
E. Round Dance
Link: E. Round Dance
1. Title description
2. Thinking Analysis
3. Code implementation
PROBLEM = """Give n and an array a[i] of length n. Where a[i] is a neighbor of i.
It is known that each i actually has 2 neighbors, forming multiple rings as a whole.
Ask the minimum and maximum number of rings.
"""
""" and lookup.
Merge directly by known neighbors. In the end there are several families, and at most there are several rings.
How to discuss it at least.
- When merging known edges, if x and y are already in a ring, either x is connected to y, or z is connected to y, and z and x are already connected. Obviously the second case will cause this loop to be closed.
- then this calculates a closed loop. First calculate how many closed loops there are. cc
- Then calculate how many points are in the non-closed family. (There is only one calculation here, because it is the least discussion), connect all non-closed points into a ring. op
- mn=cc + op
"""
class DSU:
def __init__(self, n):
self. fathers = list(range(n))
self.size = [1] * n # size of this family
self.edge_size = [0] * n # Number of edges in this family (with self-loop/multiple edges)
self.n = n
self.setCount = n # total number of families
def find_fa(self, x):
fs = self.fathers
t = x
while fs[x] != x:
x = fs[x]
while t != x:
fs[t], t = x, fs[t]
return x
def union(self, x: int, y: int) -> bool:
x = self. find_fa(x)
y = self. find_fa(y)
if x == y:
# self. edge_size[y] + = 1
return False
# if self.size[x] > self.size[y]: # Note that if you want to merge x->y in a directional way, you need to kill this; in fact, after the above is changed to find_fa, it is unnecessary to merge according to yi, so you can always close it
# x, y = y, x
self. fathers[x] = y
self.size[y] + = self.size[x]
self.edge_size[y] + = 1 + self.edge_size[x]
self.setCount -= 1
return True
# ms
def solve():
n, = RI()
a = RILST()
dsu = DSU(n)
c = set() # points inside the ring
vis = set()
for i, v in enumerate(a):
if not dsu.union(i, v - 1) and (v - 1, i) not in vis:
c.add(dsu.find_fa(i))
vis. add((i, v - 1))
cc = set() # representative element of each ring
for p in c:
cc.add(dsu.find_fa(p))
op = set() # points not in the ring
for i in range(n):
if dsu.find_fa(i) not in cc:
op. add(i)
break # just one will do
if not op:
mn = len(cc)
elif not cc:
mn = 1
else:
mn = len(cc) + 1
# print(cc,op)
print(mn, dsu. setCount)
F. Ira and Flamenco
Link: F. Ira and Flamenco
1. Title description
2. Thinking Analysis
3. Code implementation
MOD = 10 ** 9 + 7
PROBLEM = """Enter n, m and an array a[i] of length n.
You need to choose m numbers from it. Every two numbers are different, and the difference between every two numbers is strictly smaller than m.
How many options are there. Different subscripts are regarded as different schemes.
"""
"""Inverse element/interval multiplication/multiplication principle
I read the wrong question for a long time, and later found that m numbers are strictly selected, and the difference is less than m, then only a continuous number can be selected.
Each number has cnt[x], then the multiplication principle can be calculated. The remaining problem is how to do interval multiplication.
You can slide the window to maintain a segment with a length of m. The legal situation is that the values at the beginning and end of the segment are exactly m-1 apart.
Every time the right side of the window is multiplied, just remove the number out of the window on the left side of the window. Since the division does not satisfy the congruence, it is necessary to multiply the inverse element logn.
But by directly preprocessing the prefix multiplication, each inverse can be calculated in O(n).
---
Kahashi broke down after the game and cried
"""
# ms
def solve():
n, m = RI()
a = RILST()
cnt = Counter(a)
b = sorted((k, v) for k, v in cnt.items())
fact = [1]
for c, v in b:
fact.append(fact[-1] * v % MOD)
inv = [1] * len(fact)
inv[-1] = pow(fact[-1], MOD - 2, MOD)
for i in range(len(b) - 1, -1, -1):
inv[i] = b[i][1] * inv[i + 1] % MOD
ans = 0
for i in range(m - 1, len(b)):
j = i - m + 1
if j >= 0 and b[j][0] == b[i][0] - m + 1:
ans = (ans + fact[i + 1] * inv[j]) % MOD
print(ans % MOD)