★ \color{blue}★ ★ 表示巧妙但有点单薄的题。
★ \color{red}★ ★ 表示分析过程曲折复杂，且有启发的题。
★ \color{yellow}★ ★ 表示两者兼有，神仙题！
❤️ 我也不知道为什么但就是比较喜欢
上述标记和题目难度没有必然关系。
ARC187 A 略
B 发现，对于一对
( i , j ) (i,j) ( i , j ) 如果满足
a i ≤ a j a_i\le a_j a i ≤ a j ，那么
i ∼ j i\sim j i ∼ j 每个点都在一个连通块里。因为对于
i < k < j i<k<j i < k < j ，要么
a i ≤ a k a_i\le a_k a i ≤ a k 要么
a k ≤ a j a_k\le a_j a k ≤ a j 。
所以有
( i , i + 1 ) (i,i+1) ( i , i + 1 ) 不连边的条件：
min j = 1 i a j > max j = i + 1 n a j \min_{j=1}^{i}a_j>\max_{j=i+1}^{n}a_j j = 1 min i a j > j = i + 1 max n a j 令
A A A 里满足该条件的
i i i 共有
x x x 个，那么
f ( A ) = x + 1 f(A)=x+1 f ( A ) = x + 1 。
于是对于每个
i i i 去考虑多少种方案中
( i , i + 1 ) (i,i+1) ( i , i + 1 ) 不连边。令
p i p_i p i 表示
1 ∼ i 1\sim i 1 ∼ i 的最小值，
s i s_i s i 表示
i ∼ n i\sim n i ∼ n 的最大值（
− 1 -1 − 1 分别视为
m m m 和
1 1 1 ）。
考虑枚举
1 ∼ i 1\sim i 1 ∼ i 的最小值
x x x ，则
i + 1 ∼ n i+1\sim n i + 1 ∼ n 的最大值必须
< x <x < x ，所以
s i + 1 < x ≤ p i s_{i+1}<x\le p_i s i + 1 < x ≤ p i 。
考虑前半部分，如果
x ≠ p i x\ne p_i x = p i ，那么必有一个
− 1 = x -1=x − 1 = x 。考虑看哪些
− 1 = x -1=x − 1 = x ，则剩下的只要
> x >x > x 即可。令
q q q 为
1 ∼ i 1\sim i 1 ∼ i 中
− 1 -1 − 1 的个数，所以方案为：
∑ i = 1 q C q i ( m − x ) q − i = ∑ i = 0 q C q i 1 i ( m − x ) q − i − ( m − x ) q = ( m − x + 1 ) q − ( m − x ) q \begin{aligned}
\sum_{i=1}^{q}C_{q}^{i}(m-x)^{q-i}&=\sum_{i=0}^{q}C_{q}^{i}1^i(m-x)^{q-i}-(m-x)^{q}\\
&=(m-x+1)^{q}-(m-x)^q
\end{aligned} i = 1 ∑ q C q i ( m − x ) q − i = i = 0 ∑ q C q i 1 i ( m − x ) q − i − ( m − x ) q = ( m − x + 1 ) q − ( m − x ) q 否则如果
x = p i x=p_i x = p i ，那么所有
− 1 -1 − 1 只要
≥ x \ge x ≥ x 即可，即为
( m − x + 1 ) q (m-x+1)^q ( m − x + 1 ) q 。
考虑后半部分，由于只要
< x <x < x ，所以在
1 ∼ x − 1 1\sim x-1 1 ∼ x − 1 中任选，即为
( x − 1 ) p − q (x-1)^{p-q} ( x − 1 ) p − q ，
p p p 为
− 1 -1 − 1 的总数。两部分相乘即为总方案数。
ARC201 A 令
c n t a cnt_a c n t a 为执行
a + b a+b a + b 的操作数，
c n t b cnt_b c n t b 为执行
b + c b+c b + c 的操作数，则要最大化
min ( c n t a , c n t b ) \min(cnt_a,cnt_b) min ( c n t a , c n t b ) 。
发现减少一个
c n t a cnt_a c n t a 最多只会增加一个
c n t b cnt_b c n t b ，所以可以先最大化
c n t a cnt_a c n t a 后调整。
对于
i i i ，如果
a i + c i ≤ b i a_i+c_i\le b_i a i + c i ≤ b i ，那么
c n t a cnt_a c n t a 和
c n t b cnt_b c n t b 分别加上
a i a_i a i 和
c i c_i c i 即可；否则优先处理
c n t a cnt_a c n t a ，令
x = min ( a i , b i ) x=\min(a_i,b_i) x = min ( a i , b i ) ，
y = min ( b i − x , c i ) y=\min(b_i-x,c_i) y = min ( b i − x , c i ) ，则分别加上
x , y x,y x , y 即可，同时减少
c n t a cnt_a c n t a 以增加
c n t b cnt_b c n t b 的次数最多为
min ( x , c − y ) \min(x,c-y) min ( x , c − y ) 。
最后处理，如果
c n t a ≤ c n t b cnt_a\le cnt_b c n t a ≤ c n t b ，不需要减少了，答案就是
c n t a cnt_a c n t a 。否则，令
s s s 为最多减少的次数，如果
c n t a − s ≥ c n t b + s cnt_a-s\ge cnt_b+s c n t a − s ≥ c n t b + s ，则答案为
c n t b + s cnt_b+s c n t b + s ，否则就是
c n t a + c n t b 2 \frac{cnt_a+cnt_b}{2} 2 c n t a + c n t b 。
B 不断执行如下操作（每个体积都可以添加无限个价值为
0 0 0 的物品）：
若 w w w 1 1 1 2 2 2 w w w 2 2 2
若 w w w 1 1 1
C 首先容易想到建出 Trie，考虑统计答案。
令每个字符串的结尾点为关键点，将 Trie 上只有一个儿子的点补上一个叶子，于是问题转换成选出若干个关键点，使得所有根到叶子的路径都经过选出的点的方案数。
这东西可以树形 dp，在线每次修改只会修改一条链。
D 如果将
A A A 和
B B B 递增排序，那么最优的方案肯定是选取一个点
s s s 分成
[ 1 , s − 1 ] [1,s-1] [ 1 , s − 1 ] 和
[ s , r ] [s,r] [ s , r ] 两段区间，然后每段区间
a i a_i a i 和
b i b_i b i 交替相加。
要求
[ s , r ] [s,r] [ s , r ] 区间
a i a_i a i 和
b i b_i b i 交替相加结果都
≥ m \ge m ≥ m 且
s s s 最小，因为
s s s 越大
max ( a + b ) \max(a+b) max ( a + b ) 越大。然后直接二分即可。
CF2150 D 首先思考哪种状态是合法的，设
p i p_i p i 表示
i i i 位置上的人数，容易发现
p i p_i p i [ L , R ] [L,R] [ L , R ] ∀ i ∈ ( L , R ) \forall i\in (L,R) ∀ i ∈ ( L , R ) p i p_i p i
是合法的充要条件，模拟过程可得到。
于是考虑统计权值和，假设
L = 1 L=1 L = 1 ，则枚举
R R R ，不妨换一种形式表达
p p p ：
p 1 = 2 q 1 + x ( 1 ≤ x ≤ 2 ) p_1=2q_1+x(1\le x\le 2) p 1 = 2 q 1 + x ( 1 ≤ x ≤ 2 ) p i = 2 q i + 1 ( 1 < i < R ) p_i=2q_i+1(1<i<R) p i = 2 q i + 1 ( 1 < i < R ) p R = 2 q R + y ( 1 ≤ y ≤ 2 ) p_R=2q_R+y(1\le y\le 2) p R = 2 q R + y ( 1 ≤ y ≤ 2 )
考察
q i q_i q i 的性质，容易发现
∑ q i = n − x − y − ( R − 2 ) 2 \sum q_i=\frac{n-x-y-(R-2)}{2} ∑ q i = 2 n − x − y − ( R − 2 ) ，然后求
∑ 2 q i a i \sum 2q_i a_i ∑ 2 q i a i 。然后发现
q i q_i q i 是轮换对称的，所以
q i q_i q i 的期望值就是
n − x − y − ( R − 2 ) 2 R \frac{n-x-y-(R-2)}{2R} 2 R n − x − y − ( R − 2 ) ，于是就变成
w n − x − y − ( R − 2 ) R ∑ a i w \frac{n-x-y-(R-2)}{R}\sum a_i w R n − x − y − ( R − 2 ) ∑ a i ，其中
w w w 为
q i q_i q i 的方案数，用隔板法可求。
F 第一步选
k = 3 k=3 k = 3 ，因为 wxr 说加的边最多。
然后考虑第二步直接选
⌈ d 2 ⌉ + 1 \lceil\frac{d}{2}\rceil+1 ⌈ 2 d ⌉ + 1 ，其中
d d d 为原图任意一棵生成树的直径，接下来说明对于每个点对一定存在长度为
p = ⌈ d 2 ⌉ p=\lceil\frac{d}{2}\rceil p = ⌈ 2 d ⌉ 的路径。
d i s u , v ≥ p dis_{u,v}\ge p d i s u , v ≥ p u , v u,v u , v 2 2 2 1 1 1 d i s u , v < p dis_{u,v}<p d i s u , v < p x x x ∣ u ⇝ x ⋃ u ⇝ v ∣ = p + 1 |u\leadsto x\bigcup u\leadsto v|=p+1 ∣ u ⇝ x ⋃ u ⇝ v ∣ = p + 1 x x x u u u ≥ p \ge p ≥ p t t t
CF2152 F 首先把条件改一下，因为
y y y 有序，假设选了
p 1 , p 2 , ⋯ , p k p_1,p_2,\cdots,p_k p 1 , p 2 , ⋯ , p k ，则等价于要求
∀ i ≥ 3 , y [ p i ] − y [ p i − 2 ] > z \forall i\ge 3,y[p_{i}]-y[p_{i-2}]>z ∀ i ≥ 3 , y [ p i ] − y [ p i − 2 ] > z 。
所以考虑对于每个
i i i ，找到前面第一个
j j j 满足
y i − y j > z y_i-y_j>z y i − y j > z ，记为
t i t_i t i ，则
p i − 2 ≤ t [ p i ] p_{i-2}\le t[p_i] p i − 2 ≤ t [ p i ] 。
然后再考虑，区间
[ l , r ] [l,r] [ l , r ] 选出来的子集一定可以包含
{ r − 1 , r } \{r-1,r\} { r − 1 , r } ，否则将后两个替换为
r − 1 r-1 r − 1 和
r r r 一定不劣，于是考虑从
r − 1 r-1 r − 1 和
r r r 开始跳
t t t ，这个可以倍增预处理，如果跳到某个位置相同后，则要将其中一个数
− 1 -1 − 1 ，然后变成子问题。
G 首先将题目要求转换为，有多少个
u u u 满足
a u = 1 a_u=1 a u = 1 且子树内没有其他
1 1 1 。然后有子树，有翻转，考虑括号序。将
a u = 1 a_u=1 a u = 1 进来和出去分别看为
1 1 1 和
3 3 3 ，
a u = 0 a_u=0 a u = 0 看为
0 0 0 和
2 2 2 ，则转为求最长的
131313 ⋯ 131313\cdots 131313 ⋯ ，用线段树维护即可。对于子树翻转，交换
1 , 0 1,0 1 , 0 和
2 , 3 2,3 2 , 3 即可。
CF2159 D2 首先需要注意几个关键性质：
选取的右端点一定是后缀最小值，不然替换后一定不劣。
任何区间代价都 ≤ 2 log V \le 2\log V ≤ 2 log V [ 1 , 2 ] [1,2] [ 1 , 2 ] [ 2 , 4 ] [2,4] [ 2 , 4 ] ⋯ \cdots ⋯
增加一段的代价 ≤ 3 \le 3 ≤ 3 ≥ 4 \ge 4 ≥ 4 2 2 2 ⌈ x 2 ⌉ \lceil \frac{x}{2}\rceil ⌈ 2 x ⌉
考虑对于一个右端点
i i i ，求出
w ( l , i ) ≤ j w(l,i)\le j w ( l , i ) ≤ j 的最左的
l l l ，记为
f i , j f_{i,j} f i , j ，考虑然后求。即枚举左边加入段的代价，设
L i , j L_{i,j} L i , j 表示
c o s t ( l , i ) ≤ j \mathtt{cost}(l,i)\le j cost ( l , i ) ≤ j 的最左的
l l l ，那么容易转移
f i , j = min { L f i , j − k − 1 , k } f_{i,j}=\min \{L_{f_{i,j-k}-1,k}\} f i , j = min { L f i , j − k − 1 , k } 。
差分算答案即可。
E 先考虑求
[ x k ] F ( n ) [x^k]F(n) [ x k ] F ( n ) 。直接做显然不好做，注意到
n ≤ 3 × 10 5 n\le 3\times 10^5 n ≤ 3 × 1 0 5 ，考虑分块。
假设块长为
B B B ，先递推算出
F ( 0 ∼ B − 1 ) F(0\sim B-1) F ( 0 ∼ B − 1 ) ，这一部分时间复杂度
O ( B 2 ) O(B^2) O ( B 2 ) 。然后要求出任意一个
F ( n ) F(n) F ( n ) ，还要算出
F ( 0 , B , 2 B , ⋯ , ⌊ N B ⌋ B ) F(0,B,2B,\cdots,\lfloor \frac{N}{B}\rfloor B) F ( 0 , B , 2 B , ⋯ , ⌊ B N ⌋ B ) ，假设当前要求
F ( m ) F(m) F ( m ) 。
由于
F ( m ) = f m F(m)=f^m F ( m ) = f m ，其中
f = a x 2 + b x + c f=ax^2+bx+c f = a x 2 + b x + c ，考虑一种常见思路，即先求导。
F ( m ) = f m F ′ ( m ) = m f m − 1 f ′ F ′ ( m ) f = m F ( m ) f ′ F(m)=f^m\\
F'(m)=mf^{m-1}f'\\
F'(m)f=mF(m)f' F ( m ) = f m F ′ ( m ) = m f m − 1 f ′ F ′ ( m ) f = m F ( m ) f ′ 考察
[ x k − 1 ] [x^{k-1}] [ x k − 1 ] （以下记
F [ k ] F[k] F [ k ] 表示
[ x k ] F ( m ) [x^k]F(m) [ x k ] F ( m ) ）：
F [ k ] k c + F [ k − 1 ] ( k − 1 ) b + F [ k − 2 ] ( k − 2 ) a = m ( F [ k − 1 ] b + 2 F [ k − 2 ] a ) F [ k ] = ( m − k + 1 ) b F [ k − 1 ] + ( 2 m − k + 2 ) a F [ k − 2 ] k c F[k]kc+F[k-1](k-1)b+F[k-2](k-2)a=m(F[k-1]b+2F[k-2]a)\\
F[k]=\frac{(m-k+1)bF[k-1]+(2m-k+2)aF[k-2]}{kc} F [ k ] k c + F [ k − 1 ] ( k − 1 ) b + F [ k − 2 ] ( k − 2 ) a = m ( F [ k − 1 ] b + 2 F [ k − 2 ] a ) F [ k ] = k c ( m − k + 1 ) b F [ k − 1 ] + ( 2 m − k + 2 ) a F [ k − 2 ] 所以先求出
F [ 0 ] F[0] F [ 0 ] 和
F [ 1 ] F[1] F [ 1 ] 便可递推算了，这一部分时间复杂度
O ( N 2 B ) O(\frac{N^2}{B}) O ( B N 2 ) 。
然后每次询问
n , k n,k n , k ，只需要算
F ( n m o d B ) ⋅ F ( ⌊ n B ⌋ B ) F(n\bmod B)\cdot F(\lfloor \frac{n}{B}\rfloor B) F ( n mod B ) ⋅ F (⌊ B n ⌋ B ) 的第
k k k 项，假设两个多项式长度分别为
p , q p,q p , q ，则这一部分时间复杂度是
O ( min ( p , q ) ) = O ( B ) O(\min(p,q))=O(B) O ( min ( p , q )) = O ( B ) 的。所以取
B = N B=\sqrt N B = N 最优。
现在是求前
k k k 项的和，只需要将
F ( 0 , B , 2 B , ⋯ ) F(0,B,2B,\cdots) F ( 0 , B , 2 B , ⋯ ) 做一遍前缀和即可。
F 将路径上的点拿出来建序列，则
f f f 是一个滑动窗口。
首先发现由
f ( l , p ∼ p + l − 1 ) f(l,p\sim p+l-1) f ( l , p ∼ p + l − 1 ) 构成的函数值是一个单谷函数，证明考虑如果
f ( l , p ) < f ( l , p + 1 ) f(l,p)<f(l,p+1) f ( l , p ) < f ( l , p + 1 ) ，则
f ( l , p + 1 ) f(l,p+1) f ( l , p + 1 ) 为第一次出现，将对后
l l l 个产生贡献。
于是枚举
l l l ，分成
⌈ n l ⌉ \lceil \frac{n}{l}\rceil ⌈ l n ⌉ 段，考虑对每一段找到其极值点，然后放到优先队列里每次往左右扩展即可。
考虑二分，首先考虑将区间里的数从大到小覆盖未覆盖的数，区间长度为
l l l ，则对于一段平台，如果位于谷底左侧则一定作为后缀出现，否则作为前缀出现。假设当前二分区间为
[ L , R ] [L,R] [ L , R ] ，对于中点
m i d mid mi d 其函数值为
v = f ( l , m i d ) v=f(l,mid) v = f ( l , mi d ) ，如果
v v v 第一次出现的位置为
s ≥ L s\ge L s ≥ L ，则一定是作为前缀出现，否则是后缀，根据此移动
L , R L,R L , R 即可。由于谷底可能是中间一段区间，所以需要注意二分写法。
总询问次数
O ( n log 2 n + m ) O(n\log^2 n+m) O ( n log 2 n + m ) 。
CF2154 D 出得好。注意到每次割掉一个叶子需要考虑的最少，只需要保证当前不在这个点即可。联想到题目
3 n 3n 3 n 的限制，考虑当前的深度的奇偶。执行
1 1 1 操作后奇偶一定会发生变化，所以只需要让猫猫当前的深度跟当前叶子的深度不一样即可。
F1 由于
n ≤ 3000 n\le 3000 n ≤ 3000 ，考虑直接枚举
k k k 。先想如何判断一个序列是否满足，即对于
a i ≤ k a_i\le k a i ≤ k ，必须要求
a i a_i a i 前面有
a i − 1 a_i-1 a i − 1 个数也
≤ k \le k ≤ k ；对于
a i > k a_i>k a i > k ，必须要求
a i a_i a i 前面有
a i − k − 1 a_i-k-1 a i − k − 1 个数也
> k >k > k 。
在知道这个过后，容易通过组合计数算出合法的方案数。
AGC074 B 考虑不变量。首先很显然的是交换不会改变和，然后再注意到由于长度相等，所以等价于两个区间里的
1 1 1 下标分别加和减定值
x x x ，所以交换不会改变
1 1 1 位置的下标和。
容易发现上面两个条件合起来是充要的。考虑怎么构造，不妨设
f i f_i f i 和
g i g_i g i 分别表示
A A A 第
i i i 个
1 1 1 的下标和
B B B 第
i i i 个
1 1 1 的下标，考虑最终使
f i = g i f_i=g_i f i = g i 。将其分成
f i < g i f_i<g_i f i < g i 和
f i > g i f_i>g_i f i > g i 两类，相当于第一类的
1 1 1 要向右移，第二类要向左移。于是容易想到将两类对应起来，为了不影响后续操作，第一类要从后往前改，第二类要从前往后改。每次可以将
∣ f i − g i ∣ |f_i-g_i| ∣ f i − g i ∣ 相差较小的那个归位，那么操作次数是
O ( c n t 1 ) O(cnt_1) O ( c n t 1 ) 的，如果
c n t 1 > c n t 0 cnt_1>cnt_0 c n t 1 > c n t 0 翻转即可。
C 神奇构造。考虑
or \text{or} or 一个数的本质，相当于将
p p p 中这些位抹除，于是想构造出
p 1 ≤ p 2 ≤ p 3 ≤ ⋯ p_1\le p_2\le p_3\le \cdots p 1 ≤ p 2 ≤ p 3 ≤ ⋯ ，那么 考虑递归构造。
先考虑
n n n 是奇数，先将
( n − 1 ) / 2 (n-1)/2 ( n − 1 ) /2 构造出来，并复制一份，记当前最高位为
d d d ，将第二份
d + 1 d+1 d + 1 位设为
1 1 1 ，显然原来 LIS 为
i i i 的变为
2 i 2i 2 i 了，考虑通过第
n n n 个数来调整出
2 i + 1 2i+1 2 i + 1 。考虑将第
n n n 个数设为
p n − 1 or 2 d + 2 p_{n-1} \text{ or }2^{d+2} p n − 1 or 2 d + 2 ，然后把
a 2 i + 1 a_{2i+1} a 2 i + 1 设为
a 2 i a_{2i} a 2 i ，
a 2 i = a 2 i or 2 d + 2 a_{2i} =a_{2_i}\text{ or }2^{d+2} a 2 i = a 2 i or 2 d + 2 ，即是否抹去
p n p_n p n 的最高位。
n n n 是偶数只需在
n − 1 n-1 n − 1 的基础上加一个元素即可。
AGC002 F 先考虑判定。容易发现一个充要条件，即对于任意前缀颜色
0 0 0 的个数需要大于等于其他颜色种类数。于是考虑设
f i , j f_{i,j} f i , j 表示已经放了
i i i 个颜色
0 0 0 的球，
j j j 种其他颜色的球的方案数。转移只需考虑下一个放哪种球，放非颜色
0 0 0 的球时要一次放满
k − 1 k-1 k − 1 个，通过组合数算即可。
AGC006 D 看到中位数，考虑二分+01序列。即新序列
b i = [ a i ≥ x ] b_i=[a_i\ge x] b i = [ a i ≥ x ] 。考虑这个01序列的变化规律，手玩容易发现当相邻两个
b b b 相等时会向上拓展，直到被其他相邻段合并。然后再观察到影响答案的是距离终点最近的相邻段，并且唯一，于是这道题就做完了。
AGC007 C 没啥思路，考虑手玩一下。比如当
n = 3 n=3 n = 3 时：
考虑变到
n = 2 n=2 n = 2 每段长度的期望，容易得到
8 d + 5 x 6 8 d + 15 x 6 8 d + 25 x 6 8 d + 35 x 6 \frac{8d+5x}{6}\ \ \ \ \ \frac{8d+15x}{6}\ \ \ \ \ \frac{8d+25x}{6}\ \ \ \ \ \frac{8d+35x}{6} 6 8 d + 5 x 6 8 d + 15 x 6 8 d + 25 x 6 8 d + 35 x 发现这又是一个等差数列，并且分析第一段得到首项为
( 2 n + 2 ) d + 5 x 2 n \frac{(2n+2)d+5x}{2n} 2 n ( 2 n + 2 ) d + 5 x ，第二段减第一段得到公差为
( 2 n + 4 ) x 2 n \frac{(2n+4)x}{2n} 2 n ( 2 n + 4 ) x 。于是只需要算出每一步的期望长度
∑ i = 0 2 n − 1 ( d + i x ) 2 n = d + 2 n − 1 2 x \frac{\sum_{i=0}^{2n-1}(d+ix)}{2n}=d+\frac{2n-1}{2}x 2 n ∑ i = 0 2 n − 1 ( d + i x ) = d + 2 2 n − 1 x 。
CF2168 B 考虑到如果答案为
n − 1 n-1 n − 1 一定可以确定出这段区间有
1 1 1 和
n n n 。由于单调性，所以可以二分出包含
1 1 1 和
n n n 的最短前缀和最短后缀，便得到了
1 1 1 和
n n n 的位置集合。
第一个人只需简单的返回
1 1 1 和
n n n 的先后顺序即可。
C 拜谢 @wxr_。考虑到增删元素操作，我们为了还原出本来的序列，考虑返回一个异或和为
0 0 0 的子集。打表发现
1 ∼ 20 1\sim 20 1 ∼ 20 异或和为
0 0 0 的子集个数恰为
2 15 2^{15} 2 15 。
发现
1 ∼ n 1\sim n 1 ∼ n 的子集异或和在
0 ∼ 2 ⌊ log ( n ) ⌋ + 1 − 1 0\sim 2^{\lfloor\log (n)\rfloor +1}-1 0 ∼ 2 ⌊ l o g ( n )⌋ + 1 − 1 均匀随机，考虑归纳证明。
ARC209 A ⑩
首先判断最开始不合法和
k k k 是奇数的情况。那么第一个人每次操作会使序列不合法，第二个人每次要让序列合法。
可以证明第一个人只会不断删除一侧的字符，直接判一下就好了。
B 假设
c c c 是
s s s 中出现次数最多的字符，并出现了
A A A 次，其他字符出现了
B B B 次。
首先考虑
A ≤ B A\le B A ≤ B ，比较显然存在策略使得
f ( s ′ ) = 0 f(s')=0 f ( s ′ ) = 0 。
然后是
A > B A>B A > B ，设只考虑
S S S 中只包含
c c c 的偶回文子串个数为
g ( S ) g(S) g ( S ) ，那么显然有
f ( S ) ≥ g ( S ) f(S)\ge g(S) f ( S ) ≥ g ( S ) 。考虑将
s s s 重排使得
g ( s ′ ) g(s') g ( s ′ ) 最小且
f ( s ′ ) = g ( s ′ ) f(s')=g(s') f ( s ′ ) = g ( s ′ ) ，那么
s ′ s' s ′ 即为答案。
再设
h ( n ) h(n) h ( n ) 表示
n n n 个
c c c 组成字符串的
f f f 值，那么有
h ( 2 m ) = m 2 , h ( 2 m + 1 ) = m ( m + 1 ) h(2m)=m^2,h(2m+1)=m(m+1) h ( 2 m ) = m 2 , h ( 2 m + 1 ) = m ( m + 1 ) 。显然将
c c c 划分段数越多越好，即分割成
B + 1 B+1 B + 1 个连续段，设
l i l_i l i 分别表示每段的长度，那么
g ( s ′ ) = ∑ i = 1 B + 1 h ( l i ) \displaystyle g(s')=\sum_{i=1}^{B+1}h(l_i) g ( s ′ ) = i = 1 ∑ B + 1 h ( l i ) ，注意到
h h h 是一个凸函数，满足
h ( a ) + h ( b ) ≥ 2 h ( a + b 2 ) \displaystyle h(a)+h(b)\ge 2h\left(\frac{a+b}{2}\right) h ( a ) + h ( b ) ≥ 2 h ( 2 a + b ) ，所以我们又希望
l i l_i l i 尽量接近。
设
A = k ( B + 1 ) + r ( 0 ≤ r ≤ B ) A=k(B+1)+r(0\le r\le B) A = k ( B + 1 ) + r ( 0 ≤ r ≤ B ) ，那么
l i l_i l i 中有
r r r 个
k + 1 k+1 k + 1 和
( B + 1 − r ) (B+1-r) ( B + 1 − r ) 个
k k k 。现在已经达成
g ( s ′ ) g(s') g ( s ′ ) 最小的条件，则还需要满足
f ( s ′ ) = g ( s ′ ) f(s')=g(s') f ( s ′ ) = g ( s ′ ) 。影响因素是当
l i l_i l i 为偶数时计算了包含第
i i i 段的答案，那么考虑让
l i l_i l i 尽量为奇数。注意到当
a a a 是偶数时
2 h ( a ) = h ( a − 1 ) + h ( a + 1 ) 2h(a)=h(a-1)+h(a+1) 2 h ( a ) = h ( a − 1 ) + h ( a + 1 ) ，所以当
l i l_i l i 中有多个偶数时便可以将其中两个变成奇数。所以最终只会剩下至多一个偶数，让其为开头即可。
