AGC041
B
降序排序
- (ile p)则(i)一定合法
-
(i>p)
若(a_i+m<a_{p})则显然不合法
那么([1,p)[i,n])这些全选。至于(xin[p,i))中间这些点，最多升至(a_i+m)，由于(a_xge 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 imes 3)的对角线拼起来
(2|n)
大概是这样
aa....cd
bb....cd
cdaa....
cdbb....
..cdaa..
..cdbb..
....cdaa
....cdbb
然后(n)不是(3)倍数的奇数，(7 imes 7)之后是偶数块
D
做法1
合法的充要条件
- (a_1le a_2le cdotsle a_{n-1}le a_n)
- (forall kin[1,n),.s.t~sumlimits_{i=1}^{k+1} a_i>sumlimits_{i=n-k+1}^n a_iLongrightarrow sumlimits_{i=1}^{k+1} a_i>sumlimits_{i=n-k+1}^n a_i(k=leftlfloorfrac{n-1}{2} ight floor))
若(2|n)，令(k=leftlfloorfrac{n-1}{2} ight floor)
- (a_{k+2}-a_ile a_{k+2}-a_{i-1}(iin(k+2,1)))；(a_{i}-a_{k+2}le a_{i+1}-a_{k+2}(iin(k+2,n)))
- (sumlimits_{i=1}^{k+1} a_i>sumlimits_{i=n-k+1}^n a_iLongrightarrow a_{k+2}>(sumlimits_{i=n-k+1}^n a_i-a_{k+2})+(sumlimits_{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})。我们有(ille n)。故复杂度为(O(n^2logn))
令(g_{i,s})为后(i)个数，与(a_{k+2})的差的和为(s)。转移类似
若(n)不是(2)的倍数，令(k=leftlfloorfrac{n-1}{2} ight floor)
- (a_{k+1}-a_ile a_{k+1}-a_{i-1}(iin(k+1,1)))；(a_{i}-a_{k+1}le a_{i+1}-a_{k+1}(iin(k+1,n)))
- (sumlimits_{i=1}^{k} a_i>sumlimits_{i=n-k+1}^n a_iLongrightarrow a_{k+1}>(sumlimits_{i=n-k+1}^n a_i-a_{k+1})+(sumlimits_{i=1}^{k}a_{k+1}-a_i))
做法2
令(a_i=1+sum limits_{j=1}^i b_i)
- (sum b_i<n,b_ige 0)
- (forall kin[1,n),.s.t~sumlimits_{i=1}^{k+1} (1+sum limits_{j=1}^i b_i)>sumlimits_{i=n-k+1}^n (1+sum limits_{j=1}^i b_i)(k=leftlfloorfrac{n-1}{2} ight floor))
第二个限制可以化简成(sumlimits_{i=1}^{n}c_ib_ile 0)。其中(c_i)可以分(n)的奇偶性得到。特殊的，其中只有(c_1)为负数，且为(-1)
即约数条件可以重新写为
- (b_1le n-1-sumlimits_{i=2}^n b_i)
- (b_1ge sumlimits_{i=2}^n c_ib_i)
在已知(b_i(iin[2,n]))的条件下，合法的(b_1)的个数为(max(0,n-sumlimits_{i=2}^n (c_i+1)b_i))
令(f_j)为(sumlimits_{i=2}^n (c_i+1)b_i)=j)的方案数，(ans=sumlimits_{i=0}^{n-1}(n-i)f_i)
E
这题比较简单
F
这题题解有点难写