AGC041

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

这题题解有点难写

上一篇:奇怪装置「APIO 2019」(推柿子+求区间并)


下一篇:巧用 Win 10 内置输入法,提升你的工作效率