B
降序排序
- \(i\le p\)则\(i\)一定合法
- \(i>p\)
若\(a_i+m<a_{p}\)则显然不合法
那么\([1,p)[i,n]\)这些全选。至于\(x\in[p,i)\)中间这些点，最多升至\(a_i+m\)，由于\(a_x\ge a_i\)，其不会消耗完天数，故边界条件就是将其全部升至\(a_i+m\)
C
\(n=5\)
aabc.
..bcd
fee.d
f.ghh
iigjj
\(n=7\)
aabbcc.
ddee..c
ffgg..c
....geb
....geb
....fda
....fda
\(3|n\)
有\(3\times 3\)的对角线拼起来
\(2|n\)
大概是这样
aa....cd
bb....cd
cdaa....
cdbb....
..cdaa..
..cdbb..
....cdaa
....cdbb
然后\(n\)不是\(3\)倍数的奇数，\(7\times 7\)之后是偶数块
D
做法1
合法的充要条件
- \(a_1\le a_2\le \cdots\le a_{n-1}\le a_n\)
- \(\forall k\in[1,n),.s.t~\sum\limits_{i=1}^{k+1} a_i>\sum\limits_{i=n-k+1}^n a_i\Longrightarrow \sum\limits_{i=1}^{k+1} a_i>\sum\limits_{i=n-k+1}^n a_i(k=\left\lfloor\frac{n-1}{2}\right\rfloor)\)
若\(2|n\)，令\(k=\left\lfloor\frac{n-1}{2}\right\rfloor\)
- \(a_{k+2}-a_i\le a_{k+2}-a_{i-1}(i\in(k+2,1))\)；\(a_{i}-a_{k+2}\le a_{i+1}-a_{k+2}(i\in(k+2,n))\)
- \(\sum\limits_{i=1}^{k+1} a_i>\sum\limits_{i=n-k+1}^n a_i\Longrightarrow a_{k+2}>(\sum\limits_{i=n-k+1}^n a_i-a_{k+2})+(\sum\limits_{i=1}^{k+1}a_{k+2}-a_i)\)
令\(f_{i,s}(i<k+2)\)为前\(i\)个数，与\(a_{k+2}\)差的和为\(s\)。
为满足差的单调性，考虑分层转移，即在最外层降序枚举与\(a_{k+2}\)的差\(l\)，然后内层\(f_{i+1,s+l}=f_{i+1,s+l}+f_{i,s}\)。我们有\(il\le n\)。故复杂度为\(O(n^2logn)\)
令\(g_{i,s}\)为后\(i\)个数，与\(a_{k+2}\)的差的和为\(s\)。转移类似
若\(n\)不是\(2\)的倍数，令\(k=\left\lfloor\frac{n-1}{2}\right\rfloor\)
- \(a_{k+1}-a_i\le a_{k+1}-a_{i-1}(i\in(k+1,1))\)；\(a_{i}-a_{k+1}\le a_{i+1}-a_{k+1}(i\in(k+1,n))\)
- \(\sum\limits_{i=1}^{k} a_i>\sum\limits_{i=n-k+1}^n a_i\Longrightarrow a_{k+1}>(\sum\limits_{i=n-k+1}^n a_i-a_{k+1})+(\sum\limits_{i=1}^{k}a_{k+1}-a_i)\)
做法2
令\(a_i=1+\sum \limits_{j=1}^i b_i\)
- \(\sum b_i<n,b_i\ge 0\)
- \(\forall k\in[1,n),.s.t~\sum\limits_{i=1}^{k+1} (1+\sum \limits_{j=1}^i b_i)>\sum\limits_{i=n-k+1}^n (1+\sum \limits_{j=1}^i b_i)(k=\left\lfloor\frac{n-1}{2}\right\rfloor)\)
第二个限制可以化简成\(\sum\limits_{i=1}^{n}c_ib_i\le 0\)。其中\(c_i\)可以分\(n\)的奇偶性得到。特殊的，其中只有\(c_1\)为负数，且为\(-1\)
即约数条件可以重新写为
- \(b_1\le n-1-\sum\limits_{i=2}^n b_i\)
- \(b_1\ge \sum\limits_{i=2}^n c_ib_i\)
在已知\(b_i(i\in[2,n])\)的条件下，合法的\(b_1\)的个数为\(max(0,n-\sum\limits_{i=2}^n (c_i+1)b_i)\)
令\(f_j\)为\(\sum\limits_{i=2}^n (c_i+1)b_i)=j\)的方案数，\(ans=\sum\limits_{i=0}^{n-1}(n-i)f_i\)
E
这题比较简单
F
这题题解有点难写
AGC041
原文：https://www.cnblogs.com/Grice/p/13271760.html
