10.9 Luogu P12195 [NOISG 2025 Prelim] Itinerary 关键在于发现按 s s s u → s 1 u \to s _ 1 u → s 1
还是思维的锅啊，一直往子序列靠没往路径经过次数。
AtCoder ABC250E Prefix Equality 哈希不要用和哈希这种容易被卡的，用类 B a s e Base B a se
还有就是比较长的代码或者纯模拟，注意细节与理清思路，不要没想好就开写导致调的时间大于重构时间。
10.10 LibreOJ 2833 「JOISC 2018 Day 1」帐篷 思维灵活一点，限制放宽，不需要确定每一行的存在情况。
我们发现同一行与同一列不能同时放两个以上的帐篷，同时不能在同行与同列交点处有帐篷，我们就可以考虑对这个状态进行刻画。
记 d p i , j dp _ {i,j} d p i , j i i i j j j i i i
一个都不放：d p i , j = d p i , j dp _ {i,j} = dp _ {i,j} d p i , j = d p i , j 放且不同行也不同列：则有 4 j 4j 4 j j j j d p i − 1 , j − 1 dp _ {i - 1,j - 1} d p i − 1 , j − 1 和之前一个放同列不同行： 之前的帐篷可选 i − 1 i - 1 i − 1 j j j d p i − 2 , j − 1 dp _ {i - 2,j - 1} d p i − 2 , j − 1 和之前一个放同行不同列： 在 j j j C j 2 = j ( j − 1 ) 2 C _ {j} ^ 2 = \frac{j(j - 1)}{2} C j 2 = 2 j ( j − 1 ) d p i − 1 , j − 2 dp _ {i - 1,j - 2} d p i − 1 , j − 2 所以，总的 DP 方程就是 d p i , j = d p i − 1 , j + 4 j ⋅ d p i − 1 , j − 1 + ( i − 1 ) j ⋅ d p i − 2 , j − 1 + j ( j − 1 ) 2 ⋅ d p i − 1 , j − 2 dp _ {i,j} = dp _ {i - 1,j} + 4j \cdot dp _ {i - 1,j - 1} + (i - 1)j \cdot dp _ {i - 2,j - 1} + \frac{j(j - 1)}{2} \cdot dp _ {i - 1,j - 2} d p i , j = d p i − 1 , j + 4 j ⋅ d p i − 1 , j − 1 + ( i − 1 ) j ⋅ d p i − 2 , j − 1 + 2 j ( j − 1 ) ⋅ d p i − 1 , j − 2
初始状态是 d p 0 , j = d p i , 0 = 1 dp _ {0,j} = dp _ {i,0} = 1 d p 0 , j = d p i , 0 = 1
AtCoder ABC251D At Most 3 (Contestant ver.) 很有意思的一道构造题。
发现 W ∈ [ 1 , 10 6 ] W \in [1,10 ^ 6] W ∈ [ 1 , 1 0 6 ] 300 300 300
我们发现，十进制下任意 < 10 6 \lt 10 ^ 6 < 1 0 6 a b c d e f ‾ \overline{abcdef} ab c d e f
考虑用百进制来表示出来这个数，发现只需要表示出 { x ∣ x = 100 2 × y , y ∈ [ 1 , 99 ] ∩ Z } ∩ { x ∣ x = 100 × y , y ∈ [ 1 , 99 ] ∩ Z } ∩ { x ∣ x = 100 2 × y , y ∈ [ 1 , 99 ] ∩ Z } \{x \mid x = 100 ^ 2 \times y,y \in [1,99] \cap \Z\} \cap \{x \mid x = 100 \times y,y \in [1,99] \cap \Z\} \cap \{x \mid x = 100 ^ 2 \times y,y \in [1,99] \cap \Z\} { x ∣ x = 10 0 2 × y , y ∈ [ 1 , 99 ] ∩ Z } ∩ { x ∣ x = 100 × y , y ∈ [ 1 , 99 ] ∩ Z } ∩ { x ∣ x = 10 0 2 × y , y ∈ [ 1 , 99 ] ∩ Z } x ∈ [ 1 , 10 6 ) ∩ Z x \in [1,10 ^ 6) \cap \Z x ∈ [ 1 , 1 0 6 ) ∩ Z
上述一共有 99 × 3 = 297 99 \times 3 = 297 99 × 3 = 297 10 6 10 ^ 6 1 0 6 298 298 298
心得：关于数的构造题不一定要从纯数论角度，也可以通过数的构成来构造。
10.11 Link↗
A 询问 发现这个 2 a − i 2a - i 2 a − i 2 b − i 2b - i 2 b − i a + i a + i a + i b + i b + i b + i 2 a − i 2a - i 2 a − i 2 b − i 2b - i 2 b − i
所以可以暴力预处理前 30 30 30 a , b ∈ [ 0 , 10 9 + 7 ) a,b \in [0,10 ^ 9 + 7) a , b ∈ [ 0 , 1 0 9 + 7 ) long long 了，然后后面用矩阵快速幂转移。
我们发现需要一个自增的变量，所以维护的矩阵是 [ a i b i p i 1 ] \begin{bmatrix} a _ i & b _ i & p _ i & 1 \end{bmatrix} [ a i b i p i 1 ] [ a i b i p i 1 ] ⇒ [ 2 b i − i 2 a i − i p i + 1 1 ] \begin{bmatrix} a _ i & b _ i & p _ i & 1 \end{bmatrix} \Rightarrow \begin{bmatrix} 2 b _ i - i & 2 a _ i - i & p _ i + 1 & 1 \end{bmatrix} [ a i b i p i 1 ] ⇒ [ 2 b i − i 2 a i − i p i + 1 1 ] [ 2 0 0 0 0 2 0 0 − 1 − 1 1 0 0 0 1 1 ] \begin{bmatrix} 2 & 0 & 0 & 0 \\ 0 & 2 & 0 & 0 \\ -1 & -1 & 1 & 0 \\ 0 & 0 & 1 & 1 \end{bmatrix} 2 0 − 1 0 0 2 − 1 0 0 0 1 1 0 0 0 1
B k-绍兴序列 正问题不好做，我们考虑取约束条件的否命题，即 ¬ ( ∃ i < j , a i < k a j ) = ∀ i < j , a i ≥ k a j \neg (\exist i \lt j,a _ i \lt k a _ j) = \forall i \lt j,a _ i \ge k a _ j ¬ ( ∃ i < j , a i < k a j ) = ∀ i < j , a i ≥ k a j ( m + 1 ) n − A n s (m + 1) ^ n - Ans ( m + 1 ) n − A n s
k = 1 k = 1 k = 1 [ 0 , m ] [0,m] [ 0 , m ] n n n n n n 1 1 1 m m m n + m n + m n + m n n n 1 1 1 m m m C n + m n C _ {n + m} ^ n C n + m n k ≥ 2 k \ge 2 k ≥ 2 d p i , x dp _ {i,x} d p i , x i i i x x x d p i , x = ∑ y = k x n d p i − 1 , y dp _ {i,x} = \sum \limits _ {y = kx} ^ {n} dp _ {i - 1,y} d p i , x = y = k x ∑ n d p i − 1 , y d p 1 , [ 0 , m ] = 1 dp _ {1,[0,m]} = 1 d p 1 , [ 0 , m ] = 1 d p dp d p 0 0 0 ⌊ m k i − 1 ⌋ \lfloor \frac{m}{k ^ {i - 1}} \rfloor ⌊ k i − 1 m ⌋ ∑ i = 0 ⌊ m k n − 1 ⌋ d p n , i \sum \limits _ {i = 0} ^ {\lfloor \frac{m}{k ^ {n - 1}} \rfloor} dp _ {n,i} i = 0 ∑ ⌊ k n − 1 m ⌋ d p n , i C 二次根式 显然 G = N ! F G = \frac{N!}{F} G = F N ! F F F
考虑对每个平方因子求有多少个数有这个因子，我们枚举质数，然后计算含有这个质数的所有倍数的平方的数的个数之和，所以 F = ∏ p ≤ N , p ∈ Prime p ∑ k = 1 ⌊ N p 2 k ⌋ F = \prod \limits _ {p \le \sqrt{N},p \in \text{Prime}} p ^ {\sum \limits _ {k = 1} \lfloor \frac{N}{p ^ {2k}} \rfloor} F = p ≤ N , p ∈ Prime ∏ p k = 1 ∑ ⌊ p 2 k N ⌋
线性筛预处理出 [ 1 , 10 9 + 7 ] [1,\sqrt{10 ^ 9 + 7}] [ 1 , 1 0 9 + 7 ] O ( N ln N × log N ) = O ( n ) \Omicron(\frac{\sqrt{N}}{ \ln N} \times \log N) = \Omicron(\sqrt{n}) O ( l n N N × log N ) = O ( n )
现在问题是如何快速求出 N ! N ! N ! B = 3 × 10 5 B = 3 \times 10 ^ 5 B = 3 × 1 0 5 B ! , ( 2 B ) ! … B!,(2B)!\dots B ! , ( 2 B )! … O ( B ) \Omicron(B) O ( B ) 33.8 kB 33.8\text{kB} 33.8 kB
10.12 打 CF，汇总链接↗ 。
10.13 AtCoder ABC250G Stonks 第一次见这种题。
我们先考虑一个贪心，如果 i < j i \lt j i < j a i < a j a _ i \lt a _ j a i < a j i i i j j j
这玩意显然不对，因为后面可能会有更高的价格，于是我们考虑带上反悔操作，如果 a i < a k a _ i \lt a _ k a i < a k i i i k k k a k < a j a _ k \lt a _ j a k < a j k k k j j j i i i j j j
实现上，我们维护一个小根堆，对于 a i a _ i a i a j a _ j a j a i a _ i a i a i − a j a _ i - a _ j a i − a j a j a _ j a j a i a _ i a i a i a _ i a i
10.14 Link↗
A Happy·Lovely·Everyday！ 我们发现 popcount ( x ⊕ y ) = x ⊕ y \operatorname{popcount}(x \oplus y) = x \oplus y popcount ( x ⊕ y ) = x ⊕ y
而这个分段可以想到前缀的差分，我们设 s i = ⨁ j = 1 i a i s _ i = \bigoplus _ {j = 1} ^ {i} a _ i s i = ⨁ j = 1 i a i { b i } \{b _ i\} { b i } p p p p 0 = 0 , p k = n p _ 0 = 0,p _ k = n p 0 = 0 , p k = n ∀ i , b i = a p i ⊕ a p i − 1 \forall i,b _ i = a _ {p _ i} \oplus a _ {p _ {i - 1}} ∀ i , b i = a p i ⊕ a p i − 1
我们再对 b b b B B B b b b B B B b b b a [ 1 , n − 1 ] a _ {[1,n - 1]} a [ 1 , n − 1 ]
我们设 d p i dp _ {i} d p i i i i a i a _ i a i d p i = 2 d p i − 1 + 1 dp _ {i} = 2 dp _ {i - 1} + 1 d p i = 2 d p i − 1 + 1 a i a _ i a i
如果前面有与 a i a _ i a i l a s t last l a s t d p i = 2 d p i − 1 − d p l a s t − 1 dp _ {i} = 2 dp _ {i - 1} - dp _ {last - 1} d p i = 2 d p i − 1 − d p l a s t − 1 [ 1 , l a s t − 1 ] [1,last - 1] [ 1 , l a s t − 1 ] d p l a s t − 1 + 1 dp _ {last - 1} + 1 d p l a s t − 1 + 1
最终答案是 d p n − 1 dp _ {n - 1} d p n − 1 d p 1 = 1 dp _ 1 = 1 d p 1 = 1
B 敬启，致那时的我 显然斐波那契数列没有什么好的性质，而看到斐波那契数列你应该能想到这是递推，而想到递推就能想到矩阵快速幂。
设转移矩阵为 B B B P k = B 2 k , k ∈ [ 0 , n ) P _ k = B ^ {2 ^ k},k \in [0,n) P k = B 2 k , k ∈ [ 0 , n ) P P P k k k
因为矩阵乘法有分配律，所以可以记录和，最后一起左乘初始矩阵。考虑 DP，设 d p i , j dp _ {i,j} d p i , j i i i j j j d p 0 , 0 = I dp _ {0,0} = I d p 0 , 0 = I i i i d p i , j = d p i − 1 , j + d p i − 1 , j − 1 × P i − 1 dp _ {i,j} = dp _ {i - 1,j} + dp _ {i - 1,j - 1} \times P _ {i - 1} d p i , j = d p i − 1 , j + d p i − 1 , j − 1 × P i − 1
然后考虑一般情况，这个时候就有数位限制了。我们参考迭代实现的数位 DP 统计答案的方式，枚举这一位是否达到上限。
我们用递归实现，设 f n , k f _ {n,k} f n , k n n n k k k
s n = 1 s _ {n} = 1 s n = 1 0 0 0 1 1 1 0 0 0 d p n − 1 , k dp _ {n - 1,k} d p n − 1 , k 1 1 1 f n − 1 , k − 1 × P n − 1 f _ {n - 1,k - 1} \times P _ {n - 1} f n − 1 , k − 1 × P n − 1 s n = 0 s _ {n} = 0 s n = 0 f n − 1 , k f _ {n - 1,k} f n − 1 , k 到最底层判断一下 k k k 0 0 0 0 0 0 O O O I I I
10.15 Link↗
A 火 鉴定为学矩阵和学线段树学魔怔了。
我们对每个位置分别考虑被选到的概率，加起来就是总期望。
一棵树燃烧，当且仅当 [ max { 1 , i − k } , min { n , i + k } ] [\max \{1,i - k\},\min \{n,i + k\}] [ max { 1 , i − k } , min { n , i + k }] i i i i − k i - k i − k p i − k p _ {i - k} p i − k i − k + 1 i - k + 1 i − k + 1 ( 1 − p i − k ) p i − k + 1 (1 - p _ {i - k})p _ {i - k + 1} ( 1 − p i − k ) p i − k + 1
直接做是 O ( n k ) \Omicron(nk) O ( nk ) [ s u m p r o d ] \begin{bmatrix} sum & prod \end{bmatrix} [ s u m p ro d ] [ s u m p r o d ] ⇒ [ s u m + p r o d × p i p r o d × ( 1 − p i ) ] \begin{bmatrix} sum & prod \end{bmatrix} \Rightarrow \begin{bmatrix} sum + prod \times p _ i & prod \times (1 - p _ i) \end{bmatrix} [ s u m p ro d ] ⇒ [ s u m + p ro d × p i p ro d × ( 1 − p i ) ] [ 1 0 p i 1 − p i ] \begin{bmatrix} 1 & 0 \\ p _ i & 1 - p _ i \end{bmatrix} [ 1 p i 0 1 − p i ] O ( n log k ) \Omicron(n \log k) O ( n log k )
B 捐赠 先考虑一个双 log \log log
我们发现取的一定是能做正贡献的，所以我们选取的是所有 a i + b i ≥ 0 a _ i + b _ i \ge 0 a i + b i ≥ 0 i i i k k k k k k a a a k k k b b b k k k 0 0 0 k k k a a a k k k b b b k k k 然后你就能发现你过了，卡不掉你。
还是写一下单 log \log log a a a b b b a a a b b b b b b b b b b b b
于是我们只用一棵权值线段树，存储 a a a b b b num ( b ) \text{num}(b) num ( b ) b b b
C 染色 考虑一个 O ( n 2 ) \Omicron(n ^ 2) O ( n 2 )
设 d p u , i dp _ {u,i} d p u , i u u u i i i i = 0 i = 0 i = 0 ∀ i ∈ [ 1 , n ] , d p u , i = ∏ v ∈ Son ( u ) ( d p v , 0 + d p v , i ) − ∏ v ∈ Son ( u ) d p v , 0 \forall i \in [1,n],dp _ {u,i} = \prod \limits _ {v \in \text{Son}(u)} (dp _ {v,0} + dp _ {v,i}) - \prod \limits _ {v \in \text{Son}(u)} dp _ {v,0} ∀ i ∈ [ 1 , n ] , d p u , i = v ∈ Son ( u ) ∏ ( d p v , 0 + d p v , i ) − v ∈ Son ( u ) ∏ d p v , 0 v v v i i i
对于 i = 0 i = 0 i = 0 d p u , 0 = ( m + 1 ) ∏ v ∈ Son ( u ) d p v , 0 + ∑ i = 1 m d p u , i dp _ {u,0} = (m + 1) \prod \limits _ {v \in \text{Son}(u)} dp _ {v,0} + \sum \limits _ {i = 1} ^ m dp _ {u,i} d p u , 0 = ( m + 1 ) v ∈ Son ( u ) ∏ d p v , 0 + i = 1 ∑ m d p u , i u u u i i i u u u i i i
直接做是 O ( n 2 ) \Omicron(n ^ 2) O ( n 2 ) O ( n log n ) \Omicron(n \log n) O ( n log n )
为什么被卡空间了啊艹
10.16 Link↗
A 玩具 第一遍还没读懂题意说是（
题意就是从区间 [ l i , r i ] [l _ i,r _ i] [ l i , r i ] k i k _ i k i w i w _ i w i
一个区间可以被表示为两个前缀和之差，所以和可以被 k i k _ i k i k i k _ i k i
我们发现，一个长为 l e n len l e n l e n + 1 len + 1 l e n + 1 r i − l i + 1 > max { k i } r _ i - l _ i + 1 \gt \max \{k _ i\} r i − l i + 1 > max { k i } max { k i } \max \{k _ i\} max { k i } 99 99 99
C 文件 神奇东西，用的二维链表。
先写一下二维链表是什么，就是每个结点的指针指向它右边的结点与下面的结点，双向就是加上左边和上面的。
然后回到这道题上来，我们先想一下交换一个序列不交的两个区间的做法，可以用链表，将每段前一个元素的指针交换，再将每段最后一个元素的指针交换。
扩展到二维，我们需要交换矩形的四个边界的指针，找到之后直接交换就行了。
10.17 Link↗
A 并非贪心 我们发现这个 ∏ i ∈ S a i \prod \limits _ {i \in S} a _ i i ∈ S ∏ a i e e e ∏ i ∈ S exp ( ln a i ) ∑ i ∈ S b i = exp ( ∑ i ∈ S ln a i ) ∑ i ∈ S b i = exp ( ∑ i ∈ S ln a i ∑ i ∈ S b i ) \sqrt[\sum \limits _ {i \in S} b _ i]{\prod \limits _ {i \in S}\exp(\ln a _ i)} = \sqrt[\sum \limits _ {i \in S} b _ i]{\exp(\sum \limits _ {i \in S} \ln a _ i)} = \exp(\frac{\sum \limits _ {i \in S}{\ln a _ i}}{\sum \limits _ {i \in S} b _ i}) i ∈ S ∑ b i i ∈ S ∏ exp ( ln a i ) = i ∈ S ∑ b i exp ( i ∈ S ∑ ln a i ) = exp ( i ∈ S ∑ b i i ∈ S ∑ l n a i ) ∑ b i \sum b _ i ∑ b i
还是太糖了，典中典 Trick 没想到。
C 斐波那契 这个故事告诉我们 Trick 不要乱用，套几天前的 Trick 做出来个没有前途的做法，其实正解非常糖。
以下记 f i f _ i f i i i i
首先有个结论： gcd ( f i , f j ) = f gcd ( i , j ) \gcd(f _ i,f _ j) = f _ {\gcd(i,j)} g cd( f i , f j ) = f g c d ( i , j )
然后我们开始推推推推推式子：
∑ i = 1 n ∑ j = 1 n gcd ( f i , f j ) = ∑ i = 1 n ∑ j = 1 n f gcd ( i , j ) = ∑ d = 1 f d ∑ i = 1 n ∑ j = 1 n [ gcd ( i , j ) = d ] = ∑ d = 1 f d ∑ i = 1 ⌊ n d ⌋ ∑ j = 1 ⌊ n d ⌋ [ gcd ( i , j ) = 1 ] \begin{aligned} \sum _ {i = 1} ^ n \sum _ {j = 1} ^ n \gcd(f _ i,f _ j) &= \sum _ {i = 1} ^ n \sum _ {j = 1} ^ n f _ {\gcd(i,j)} \\ &= \sum _ {d = 1} f _ {d} \sum _ {i = 1} ^ n \sum _ {j = 1} ^ n [\gcd(i,j) = d]\\ &= \sum _ {d = 1} f _ {d} \sum _ {i = 1} ^ {\lfloor \frac{n}{d} \rfloor} \sum _ {j = 1} ^ {\lfloor \frac{n}{d} \rfloor} [\gcd(i,j) = 1]\\ \end{aligned} i = 1 ∑ n j = 1 ∑ n g cd( f i , f j ) = i = 1 ∑ n j = 1 ∑ n f g c d ( i , j ) = d = 1 ∑ f d i = 1 ∑ n j = 1 ∑ n [ g cd( i , j ) = d ] = d = 1 ∑ f d i = 1 ∑ ⌊ d n ⌋ j = 1 ∑ ⌊ d n ⌋ [ g cd( i , j ) = 1 ] 考虑每个元素的贡献，一个数会在 i ≤ j i \le j i ≤ j φ ( j ) \varphi(j) φ ( j ) i > j i \gt j i > j φ ( i ) \varphi(i) φ ( i ) φ ( i ) \varphi(i) φ ( i ) n n n ( 2 ∑ i = 1 ⌊ n d ⌋ φ ( i ) ) − 1 (2\sum \limits _ {i = 1} ^ {\lfloor \frac{n}{d} \rfloor} \varphi(i)) - 1 ( 2 i = 1 ∑ ⌊ d n ⌋ φ ( i )) − 1
观察到 n ≤ 10 10 n \le 10 ^ {10} n ≤ 1 0 10 d d d f d f _ {d} f d
10.18 Link↗
发现只有 a u ≤ a v a _ u \le a _ v a u ≤ a v
但是有个问题，当 a u = a v a _ u = a _ v a u = a v 什么你说 SPFA？亲测被卡了。
又发现，当 a u = a v a _ u = a _ v a u = a v 0 0 0 0 0 0
缩点不用写 Tarjan，用并查集合并起来就行。
一个等于的限制可以用两个不等于的限制来刻画，所以原限制等价于 { x v ≤ x u + w x v ≥ x u + w ⇒ { x v ≤ x u + w x u ≤ x v − w \begin{cases} x _ v \le x _ u + w \\ x _ v \ge x _ u + w \end{cases} \Rightarrow \begin{cases} x _ v \le x _ u + w \\ x _ u \le x _ v - w \end{cases} { x v ≤ x u + w x v ≥ x u + w ⇒ { x v ≤ x u + w x u ≤ x v − w u → w v , v → − w u u \xrightarrow{w}v,v \xrightarrow{-w} u u w v , v − w u
但是裸的 SPFA 被卡了，于是我们可以用 DFS SPFA，这样就能卡过去了。
发现只能一条路走到底，而走到环就出不去了，所以至多有 1 1 1 n n n n n n
我们设 B i , l + 1 B _ {i,l + 1} B i , l + 1 B i , p B _ {i,p} B i , p p − 1 p - 1 p − 1
所以一条长度为 l l l A n − 1 l − 1 n n − l l ( l − 1 ) 2 A _ {n - 1} ^ {l - 1} n ^ {n - l} \frac{l(l - 1)}{2} A n − 1 l − 1 n n − l 2 l ( l − 1 ) A n − 1 l − 1 A _ {n - 1} ^ {l - 1} A n − 1 l − 1 l − 1 l - 1 l − 1 n n − l n ^ {n - l} n n − l ∑ i = 1 l ( i − 1 ) \sum \limits _ {i = 1} ^ l (i - 1) i = 1 ∑ l ( i − 1 )
正解是单调队列优化 DP，但是我就要写歪解（
发现有个恰好 k k k
我们把删去 k k k n − k n - k n − k f ( x ) f(x) f ( x ) k k k f f f
于是我们二分惩罚 p p p d p i dp _ i d p i i i i i i i
若 l i > r j l _ i \gt r _ j l i > r j d p i = max { d p j } + r i − l i − p dp _ i = \max \{dp _ j\} + r _ i - l _ i - p d p i = max { d p j } + r i − l i − p 若 r j ∈ [ l i , r i ] r _ j \in [l _ i,r _ i] r j ∈ [ l i , r i ] d p i = max { d p j − r j } + r i − p dp _ i = \max \{dp _ j - r _ j\} + r _ i - p d p i = max { d p j − r j } + r i − p 第一个可以用树状数组维护，算完 d p i dp _ i d p i r i r _ i r i O ( n log n log V ) \Omicron(n \log n \log V) O ( n log n log V )
略微卡常，我们可以使用 ZKW 线段树来卡常，就能过了。
10.20 CF Round 1060 Link↗
10.21 Link↗
A 小 h 学步 你发现每一个向量的贡献是独立的，所以我们只需要求出每个向量的贡献再乘上方案数就行，方案数就是剩下 n − 1 n - 1 n − 1 n n − 1 n ^ {n - 1} n n − 1
为什么我会把 n 写成 d 挂了 100 啊艹
B 小球进洞 首先能想到一个 O ( n m 2 ) \Omicron(n m ^ 2) O ( n m 2 )
但是显然过不了，考虑优化。我们发现如果只考虑不同的洞，最多只有 O ( size u ) \Omicron(\text{size} _ u) O ( size u ) d p u , j dp _ {u,j} d p u , j u u u j j j
我们先直接将子结点卷起来，再考虑 u u u d p u , i + j = ∑ v , u ∈ Son ( u ) d p u , i × d p w , j dp _ {u,i + j} = \sum \limits _ {v,u \in \text{Son}(u)} dp _ {u,i} \times dp _ {w,j} d p u , i + j = v , u ∈ Son ( u ) ∑ d p u , i × d p w , j u u u
u u u d p u , i ← d p u , i × i dp _ {u,i} \gets dp _ {u,i} \times i d p u , i ← d p u , i × i u u u u u u size u − 1 n − 1 \frac{\text{size} _ u - 1}{n - 1} n − 1 size u − 1 d p u , i ← d p u , i − 1 × size u − 1 n − 1 dp _ {u,i} \gets dp _ {u,i - 1} \times \frac{\text{size} _ u - 1}{n - 1} d p u , i ← d p u , i − 1 × n − 1 size u − 1 然后考虑最后的答案，我们先从所有坑中选出 i i i i ! i ! i ! ∑ d p 1 , i × C m i × i ! \sum dp _ {1,i} \times C _ m ^ i \times i! ∑ d p 1 , i × C m i × i !
10.22 Link↗
A 石头人 我们先对 a a a s u m i = ∑ j = 1 i a j sum _ {i} = \sum \limits _ {j = 1} ^ i a _ j s u m i = j = 1 ∑ i a j s u m n − ( s u m r − s u m l − 1 ) ≥ k ⇒ s u m l − 1 ≥ k + s u m r − s u m n sum _ n - (sum _ r - sum _ {l - 1}) \ge k \Rightarrow sum _ {l - 1} \ge k + sum _ r - sum _ n s u m n − ( s u m r − s u m l − 1 ) ≥ k ⇒ s u m l − 1 ≥ k + s u m r − s u m n s u m r sum _ r s u m r r r r set 里面，然后就直接查询大于 k + s u m r − s u m n k + sum _ r - sum _ n k + s u m r − s u m n s u m sum s u m
B 炒鱿鱼 我们考虑对于一个人入职的那天与被开除的那天连边，表示这两天人事不能相同，则原问题转化为图的染色问题。
首先我们发现，因为这个序列 LIFO 的性质，开掉一段人，会把他前面所有人全部开掉，而开掉的人不能被再次连边，所以染色数最大的情况就是 u u u v v v w w w u , v u,v u , v 3 3 3
然后考虑怎么构造方案，我们对于每个连通块，随便找一个点当作起点，然后第一遍循环，遍历所有邻居标记邻居不能和 u u u
10.25 Link↗
A 你脑子呢 我脑子呢？
发现你只要让第 i i i x i = ∑ t = 1 n [ a t < a i ] x _ i = \sum \limits _ {t = 1} ^ n [a _ t \lt a _ i] x i = t = 1 ∑ n [ a t < a i ] A n s i = C x i − 1 k − 1 Ans _ i = C _ {x _ i - 1} ^ {k - 1} A n s i = C x i − 1 k − 1
还有一般情况下，n ≠ m n \neq m n = m
B 原题 相等答案为 0 0 0 max { A , B } \max\{A,B\} max { A , B } gcd ( A , B ) ≠ 1 \gcd(A,B) \neq 1 g cd( A , B ) = 1 gcd ( A , B ) \gcd(A,B) g cd( A , B ) B B B A + B A + B A + B
考虑 A , B A,B A , B 2 2 2 B B B min \min min 2 2 2 A , B A,B A , B
所以我们可以一遍线性筛筛出最小质因子，然后按上面的做就行。
C 请输入文本 我们先预处理出 a i a _ i a i p i p _ i p i a i a _ i a i a i a _ i a i 0 0 0 [ L , R ] [L,R] [ L , R ] l l l [ l > p i ] [l \gt p _ i] [ l > p i ] l l l R − i + 1 R - i + 1 R − i + 1 ∑ i = L R ( i − max { p i , L − 1 } ) ( R − i + 1 ) \sum \limits _ {i = L} ^ R (i - \max\{ p _ i,L - 1 \})(R - i + 1) i = L ∑ R ( i − max { p i , L − 1 }) ( R − i + 1 ) max \max max ∑ i = L R ( i − p i ) ( R − i + 1 ) − ∑ i = L R [ p i ≤ L − 1 ] ( L − 1 − x i ) ( R − i + 1 ) \sum \limits _ {i = L} ^ R (i - p _ i)(R - i + 1) - \sum \limits _ {i = L} ^ R [p _ i \le L - 1](L - 1 - x _ i)(R - i + 1) i = L ∑ R ( i − p i ) ( R − i + 1 ) − i = L ∑ R [ p i ≤ L − 1 ] ( L − 1 − x i ) ( R − i + 1 )
前面的一堆全是与询问无关的，可以用前缀和维护。因为前面那堆等于 ( R + 1 ) ∑ i = L R ( i − p i ) − ∑ i = L R i ( i − p i ) (R + 1)\sum \limits _ {i = L} ^ R (i - p _ i) - \sum \limits _ {i = L} ^ R i (i - p _ i) ( R + 1 ) i = L ∑ R ( i − p i ) − i = L ∑ R i ( i − p i ) ∑ ( i − p i ) , ∑ i ( i − p i ) \sum (i - p _ i),\sum i(i - p _ i) ∑ ( i − p i ) , ∑ i ( i − p i ) ( L − 1 ) ( R + 1 ) ∑ i = L R [ p i ≤ L − 1 ] − ( L − 1 ) ∑ i = L R [ p i ≤ L − 1 ] i − ( R + 1 ) ∑ i = L R [ p i ≤ L − 1 ] p i + ∑ i = L R [ p i ≤ L − 1 ] i ⋅ p i (L - 1)(R + 1)\sum \limits _ {i = L} ^ R [p _ i \le L - 1] - (L - 1)\sum \limits _ {i = L} ^ R [p _ i \le L - 1]i - (R + 1)\sum \limits _ {i = L} ^ R [p _ i \le L - 1]p _ i + \sum \limits _ {i = L} ^ R [p _ i \le L - 1]i \cdot p _ i ( L − 1 ) ( R + 1 ) i = L ∑ R [ p i ≤ L − 1 ] − ( L − 1 ) i = L ∑ R [ p i ≤ L − 1 ] i − ( R + 1 ) i = L ∑ R [ p i ≤ L − 1 ] p i + i = L ∑ R [ p i ≤ L − 1 ] i ⋅ p i
D 我爱数数 首先可以想到一个类似填数的 d p dp d p O ( n m ) \Omicron(nm) O ( nm )
从填数的角度来看，这一位是否贡献只跟是否相等有关，不跟具体值有关。所以，答案就与 a i a _ i a i
那么就正难则反，考虑这个的反问题，就是有多少个 b b b a a a a a a i i i a i a _ i a i k m − ∑ i = 0 n − 1 C m i ( k − 1 ) m − i k ^ m - \sum \limits _ {i = 0} ^ {n - 1} C _ m ^ i (k - 1) ^ {m - i} k m − i = 0 ∑ n − 1 C m i ( k − 1 ) m − i
10.27 A 玩数字 糖题，暴力枚举就行。
B 课程 假定全选 b i b _ i b i n n n a i a _ i a i
C 卡牌 首先我们先把所有 a i a _ i a i B − 1 B - 1 B − 1
D 排队 你打个表可以发现 n n n n n n
E 士兵 我们考虑拆掉这个 min \min min
考虑一个二元组 ( a i , p , b i , p ) (a _ {i,p},b _ {i,p}) ( a i , p , b i , p ) ( 0 , 0 ) , ( 0 , 1 ) , ( 1 , 0 ) , ( 1 , 1 ) (0,0),(0,1),(1,0),(1,1) ( 0 , 0 ) , ( 0 , 1 ) , ( 1 , 0 ) , ( 1 , 1 )
分类讨论：
( 0 , 0 ) (0,0) ( 0 , 0 ) ( 0 , 1 ) (0,1) ( 0 , 1 ) ( 1 , 1 ) (1,1) ( 1 , 1 ) ( 1 , 0 ) (1,0) ( 1 , 0 ) a i ⊕ a j a _ i \oplus a _ j a i ⊕ a j ( 0 , 0 ) (0,0) ( 0 , 0 ) ( 1 , 0 ) (1,0) ( 1 , 0 ) ( 1 , 1 ) (1,1) ( 1 , 1 ) ( 0 , 1 ) (0,1) ( 0 , 1 ) b i ⊕ b j b _ i \oplus b _ j b i ⊕ b j ( 0 , 0 ) (0,0) ( 0 , 0 ) ( 1 , 1 ) (1,1) ( 1 , 1 ) ( 0 , 1 ) (0,1) ( 0 , 1 ) ( 1 , 0 ) (1,0) ( 1 , 0 ) 10.28 A 排序 打表发现答案为 { n ! , k > n k ! × ( k + 1 ) n − k , k ≤ n \begin{cases} n !,k \gt n \\ k ! \times (k + 1) ^ {n - k},k \le n \end{cases} { n ! , k > n k ! × ( k + 1 ) n − k , k ≤ n
B 重排 我们先做环的问题，也就是求 max { ∣ a n − a 1 ∣ + ∑ i = 2 ∣ a i − a i − 1 ∣ } \max \{ |a _ n - a _ 1| + \sum \limits _ {i = 2} | a _ i - a _ {i - 1} |\} max { ∣ a n − a 1 ∣ + i = 2 ∑ ∣ a i − a i − 1 ∣ } a a a { a 1 , a n , a 2 , a n − 1 , … , a n 2 , a n 2 + 1 } \{a _ 1,a _ n,a _ 2,a _ {n - 1}, \ldots,a _ {\frac{n}{2}},a _ {\frac{n}{2} + 1}\} { a 1 , a n , a 2 , a n − 1 , … , a 2 n , a 2 n + 1 } { a 1 , a n , a 2 , a n − 1 , … , a n 2 } \{a _ 1,a _ n,a _ 2,a _ {n - 1}, \ldots,a _ {\frac{n}{2}}\} { a 1 , a n , a 2 , a n − 1 , … , a 2 n }
发现每一个数都能贡献两次，大的数做正贡献，小的数做负贡献。现在考虑删去环新加的那部分贡献，偶数情况很简单，就是 a n 2 + 1 − a 1 a _ {\frac{n}{2} + 1} - a _ 1 a 2 n + 1 − a 1 a n 2 + 1 − a n 2 a _ {\frac{n}{2} + 1} - a _ {\frac{n}{2}} a 2 n + 1 − a 2 n a n 2 − a n 2 − 1 a _ {\frac{n}{2}} - a _ {\frac{n}{2} - 1} a 2 n − a 2 n − 1
所以我们维护前 n 2 \frac{n}{2} 2 n n 2 \frac{n}{2} 2 n n 2 \frac{n}{2} 2 n n 2 \frac{n}{2} 2 n
10.29 A ⼗字斩 直接 map 维护。
B ⼤富翁 首先变形一下，假设全部时间每个都能赚 2 2 2
将购买和装修视作两个相互独立的事件，每个的价值都是 1 1 1 A n s = 2 n m − min { t i × k i } Ans = 2nm - \min \{ t _ i \times k _ i \} A n s = 2 nm − min { t i × k i } t i t _ i t i k k k
考虑怎么最小化后面那一堆，显然我们需要尽量让小的数在前面，大的数在后面。对于 a i , 0 ≤ a i , 1 a _ {i,0} \le a_ {i,1} a i , 0 ≤ a i , 1
再考虑 a i , 0 > a i , 1 a _ {i,0} \gt a _ {i,1} a i , 0 > a i , 1
我们考虑在何处放入这一对 ( x , y ) (x,y) ( x , y ) p p p s s s Δ = min i = 0 k { 2 s i + ( k + 1 − i ) x + ( k − i ) y } = min i { 2 s i − i ( x + y ) } + ( k + 1 ) x + k y = min i { ∑ j ( 2 p j − ( x + y ) ) } + ( k + 1 ) x + k y \Delta = \min \limits _ {i = 0} ^ k \{ 2 s _ i + (k + 1 - i) x + (k - i) y\} = \min \limits _ i \{ 2 s _ i - i (x + y) \} + (k + 1) x + ky = \min \limits _ i \{ \sum \limits _ j (2p _ j - (x + y)) \} + (k + 1) x + ky Δ = i = 0 min k { 2 s i + ( k + 1 − i ) x + ( k − i ) y } = i min { 2 s i − i ( x + y )} + ( k + 1 ) x + k y = i min { j ∑ ( 2 p j − ( x + y ))} + ( k + 1 ) x + k y
最小的时候一定有 2 p i ≤ ( x + y ) → p i ≤ x + y 2 2 p _ i \le (x + y) \rightarrow p _ i \le \frac{x + y}{2} 2 p i ≤ ( x + y ) → p i ≤ 2 x + y 2 p i − ( x + y ) 2 p _ i - (x + y) 2 p i − ( x + y )
C 联谊舞会 首先转成人 i i i
然后你发现，i , j i,j i , j a i < a j ∧ b i > b j a _ i \lt a _ j \wedge b _ i \gt b _ j a i < a j ∧ b i > b j i < j ∧ b i > b j i \lt j \wedge b _ i \gt b _ j i < j ∧ b i > b j i < j , i , j ∈ S i \lt j,i,j \in S i < j , i , j ∈ S b i > b j b _ i \gt b _ j b i > b j
11.4 虽迟但到的 CSP-S 题解（
A 社团招新 首先我们考虑贪心的选最大的，显然会导致选多，然后我们按最大值与次大值的差排序，对于多的那个值，我们选取较小的 c n t − n 2 cnt - \frac{n}{2} c n t − 2 n
这是对的，因为剩下那两个和一定不会超过 n 2 \frac{n}{2} 2 n
B 道路修复 我们先枚举选的村庄的集合，是 O ( 2 k ) \Omicron(2 ^ k) O ( 2 k )
发现这个 m m m m m m O ( 2 k k n log n ) \Omicron(2 ^ k k n \log n) O ( 2 k kn log n )
考虑优化掉那个 log \log log O ( n ) \Omicron(n) O ( n ) O ( m log m + k n log k n + 2 k k n ) \Omicron(m \log m + kn \log kn + 2 ^ k k n) O ( m log m + kn log kn + 2 k kn )
C 谐音替换 欸woc我怎么没想到合起来建串啊艹艹艹
我们考虑将一个变换 s 1 → s 2 s _ 1 \to s _ 2 s 1 → s 2 A B C → A D C ABC \to ADC A BC → A D C A , C A,C A , C A#BD#C 插入 ACAM 即可。
注意特判 ∣ t 1 ∣ ≠ ∣ t 2 ∣ |t _ 1| \neq |t _ 2| ∣ t 1 ∣ = ∣ t 2 ∣
做题记录 8052 字 · 32 分钟