D F J G H A I K C B E L
2025 & 2025
2025 5 29
2025 & 2025 1 / 34
D F J G H A I K C B E L
• Easy: D, F
• Easy-Medium: G, H, J
• Medium: A, I, K
• Medium-Hard: B, C, E
• Hard: L
2025 & 2025 2 / 34
D F J G H A I K C B E L
D.
• 2x
10x
2025 & 2025 3 / 34
D F J G H A I K C B E L
F.
•
-1
2025 & 2025 4 / 34
D F J G H A I K C B E L
• O(n log n) O(n2n ) O(n)
2025 & 2025 5 / 34
D F J G H A I K C B E L
J.
•
ai
wj
• x ai
0.
•
• n ≤ 105 , m ≤ 106 , k ≤ 105 , ai ≤ 105 , wi , xi ≤ 109
2025 & 2025 6 / 34
D F J G H A I K C B E L
•
1
• ai 0
x inf
•
2025 & 2025 7 / 34
D F J G H A I K C B E L
G.
• f (x)
x m f (i) = m
i
•
• n ≤ 105 , q ≤ 106 , Ai ≤ 106 , mi ≤ 109
2025 & 2025 8 / 34
D F J G H A I K C B E L
• {Ak }nk=1
f (x + An , n) = f (x, n) + 1
x ∈ [1, An ] f (x, n) x > An
f (x, n) = f (x mod An , n) + ⌊x/An ⌋
• {Bk }∞k=1 Bk x ∈ [1, An ]
f (x, n) = k x
An k > An Bk = 0
An
2025 & 2025 9 / 34
D F J G H A I K C B E L
• f (x, n) = 1 x B1
f (x, n) = 2 x B1 + B2 B1 x
f (x + An , n) = 2 f (x, n) = 3 x
B1 + B2 + B3 B1 x
f (x + 2An , n) = 3 B2 x
f (x + An , n) = 3
∑m
• f (x, n) = m x k=1 Bk
x ∈ [1, An ]
f (x, n) {Bk }A n
k=1
{B ∞
∑km}k=1 An
m B A n m
∑m ∑An
k=1 k
k=1 B k = k=1 Bk
• O(An ) O(1)
O(max(An , q))
2025 & 2025 10 / 34
D F J G H A I K C B E L
H.
• n S k
• S T posi T i
S T posi − posi−1 > k
• S
•
∑
• n ≤ 106 , k ≤ n, n ≤ 106
2025 & 2025 11 / 34
D F J G H A I K C B E L
• k=0
• dp[i] i i
• i a[i] dp[i]
∑
i
dp[i] = dp[j]
j=0
• occ[i] a[i] a[i]
0 ∼ occ[i] − 1
∑
i−1
dp[i] = dp[j]
j=occ[i]
• k ̸= 0 a[i] dp[i − k] ∼ dp[i − 1]
∑
i−1
dp[i + k] = dp[j]
j=occ[i]
• O(n)
2025 & 2025 12 / 34
D F J G H A I K C B E L
A.
• n×m 01 A, B,
/
∑n ∑m
• i=1 j=1 (A × i + B × j)[ai,j = 1]
• n≤ 106 , m ≤ 10, |A|, |B| ≤ 106 , ai,j ∈ {0, 1}
2025 & 2025 13 / 34
D F J G H A I K C B E L
• O(2m ) O(2m )
∑
m
• s W = j [sj = 1] i
j=1
i s
• S1 = A · i · cnt1 + B · W
• S2 = A · i · (m − cnt1 ) + B · ( m(m+1)
2 −W)
cnt1 = popcount(s)
2025 & 2025 14 / 34
D F J G H A I K C B E L
• i S2 > S1
m(m+1)
A · i · (m − 2cnt1 ) > B(2W − 2 )
• i
• k
i≤k i i>k i
i≤k i i>k i
•
•
O(22m log n)
2025 & 2025 15 / 34
D F J G H A I K C B E L
I.
• n ≤ 105
2025 & 2025 16 / 34
D F J G H A I K C B E L
•
i
i
i
• fi,s i
s
gi,s i
s
fwt/SOSdp s
23 f g 23
map/unordered_map vector
2025 & 2025 17 / 34
D F J G H A I K C B E L
• f fi,0
i
i
i (82 )
popcount(s)
(fi,s ) ≥2 s
2
• O(23 n log n)
O(43 n log n) O(23 n) O(43 n)
2025 & 2025 18 / 34
D F J G H A I K C B E L
K.
• S T = aLb S (aLbLR )∞
• S
∑
• |S| ≤ 106 , |S| ≤ 106
2025 & 2025 19 / 34
D F J G H A I K C B E L
• |T | = 1 |T | ≥ 2
′
T = T T [2..(|T | − 1)] = R
T [1]T [2] . . . T [|T | − 1]T [|T |]T [|T | − 1] . . . T [2]
• S T S
(T ′ )∞
• 1. |S| > |T ′ | = 2|T | − 2 S[1..(2|T | − 1)]
|T ′ | S
• 2. |T | < |S| ≤ |T ′ | S[(2|T | − |S|)..|S|]
• 3. |S| ≤ |T | S T
2025 & 2025 20 / 34
D F J G H A I K C B E L
• S 1 |T1 | < 1+|S|
2
1+|S|
2 2 ≤ |T2 | < |S| 3 |T3 | ≥ |S|
• S[1..i] 1 T1
S[1..i]
2 3
|S[1..i]| = i
• O(|S|)
Manacher
2 Z
Manacher
1 min
• log
2025 & 2025 21 / 34
D F J G H A I K C B E L
C.
• 1 n k
1 n
• Q
• n, Q ≤ 105
2025 & 2025 22 / 34
D F J G H A I K C B E L
• n, k
• k
n−k x x −1
x −1 px−1 x px
(px−1 , px )
px−1 < px
• : px−1 < py−1 < py < px ,
px−1 < py−1 x y py < px
,x y
• : k
k
2025 & 2025 23 / 34
D F J G H A I K C B E L
• k
k +1
k
• x pax −1 < x
(pax −1 , x) (pax+1 −1 , x + 1)
(pax −1 , x)
(pax+1 −1 , x + 1) (pax+1 −1 , x + 1)
x y
y
• O(1)
O(1)
O(n log n)
2025 & 2025 24 / 34
D F J G H A I K C B E L
B.
• xor, and,
or
• x, 70 x
• n ≤ 105 , x < 230
2025 & 2025 25 / 34
D F J G H A I K C B E L
• V S x
log V = 30 x
•
•
• 2 log V = 60
O(n 2 (log V )2 )
•
O(n log V + (log V )4 )
2025 & 2025 26 / 34
D F J G H A I K C B E L
• x1 , x2 , . . . , xm B
a1 , a2 , . . . , an
•
• 1. ∀i, j ai ∧ aj ∈ B B
• 2. ∀i, j xi ∧ xj ∈ B ∀i, j ai ∧ aj ∈ B
2025 & 2025 27 / 34
D F J G H A I K C B E L
• 1 ai ∨ aj = (ai ∧ aj ) ⊕ ai ⊕ aj
• S 2n − 1
B
• c ,c = 1 c=2
,c = 3 a1 ∧ a2 ∧ a3 ∈ B
• a1 ∧ a2 ∈ B {q} a1 ∧ a2 = ⊕i aqi
•
• a1 ∧ a2 ∧ a3 = (⊕i aqi ) ∧ a3 = ⊕i (aqi ∧ a3 )
• B B
• B 1
2025 & 2025 28 / 34
D F J G H A I K C B E L
• 2 {p} ai = ⊕j xpi,j
• ai ∧ aj = (⊕l xpi,l ) ∧ (⊕k xpj,k ) = ⊕l,k (xpi,l ∧ xpj,k )
• 2
•
2025 & 2025 29 / 34
D F J G H A I K C B E L
E.
• 2×N
• N ≤ 2 × 105
2025 & 2025 30 / 34
D F J G H A I K C B E L
•
0
• O(n)
2025 & 2025 31 / 34
D F J G H A I K C B E L
L.
• n×m (1, 1) (n, m) k
x y
• n ≤ 50, m ≤ 4, k ≤ 105
2025 & 2025 32 / 34
D F J G H A I K C B E L
• dp
•
•
• (1: 2:
3: 4: / 5: /
6: )
• O(nm7m × 36), 7m ,
36 6×6
2025 & 2025 33 / 34
D F J G H A I K C B E L
Thank you!
2025 & 2025 34 / 34