AtCoder Regular Contest 104 题解
s_r_f
·
·
个人记录
A
由二元一次方程组的知识可知 X = \frac{A+B}{2} Y = \frac{A-B}{2} , 直接输出即可.
\Theta(1)
B
对 A,T 做一个前缀和 cnt1[i] 表示前 i 个数当中 A 的个数减去 T 的个数
对 C,G 做一个前缀和 cnt2[i] 表示前 i 个数当中 C 的个数减去 G 的个数
枚举区间，可以 \Theta(1) 判断区间内 A 的个数减去 T 的个数 以及 C 的个数减去 G 的个数 是否等于 0 .
实际上这个题可以用 map 做到 \Theta(n\log n) .
C
首先判掉读入的数里面就有相等的非 -1 的数的情况。
考虑一个区间是否合法，即区间 [L,R] 内部是否能成为一段相交的合法解。
首先必然有 (R-L+1) 是偶数，否则不合法
令 t = \frac{R-L+1}{2} , 有 t 个 pair 并且它们互相相交，不难发现这 t 个 pair 必然是长度为 t+1 的，形如 [L,L+t] , [L+1,L+1+t] \cdots [R-t,R] 的。
然后判断是否可能存在这 t 个 pair 即可。
判断好之后考虑记 dp_i 表示区间 [1...i] 能否形成一组合法解即可，不需要记录使用的 -1 -1 的次数，因为我们在 check 的过程中保证了端点互不相等。
判断区间合法的复杂度为 \Theta(n) , 最多需要判断 \Theta(n^2) 次，所以复杂度为 \Theta(n^3) .
D
对于每个询问的 x , 我们相当于是 x 可以看成 0 ,
x-1,x-2 \cdots 1$ 看成 $-1,-2 \cdots -(x-1)
记 $f_{i,j}$ 为值域为 $[1,i]$ 的可重集(每个数字出现次数不超过 $K$ 次) , 总和为 j 的方案数。
由于 $j$ 的范围是 $\Theta(KN^2)$ , 所以状态总数是 $\Theta(KN^3)$ , 可以每次转移的时候通过前缀和实现 $\Theta(1)$ 转移，就可以在 $\Theta(KN^3)$ 的时间内求出所有的 $f_{i,j}$ .
最后对于每个询问的$x$ 答案为 $((K+1)\sum\limits_{i=0}^{\infty} f_{x-1,i} f_{n-x-1,i}) - 1
E
枚举大小顺序之后直接按照值域 DP 即可。
\Theta(N^3 N!)
F
记 f_{v,l,r} 表示区间 [l,r] 左边有一个比区间 [l,r] 都大的数 , 区间内所有数都小于等于 v 的方案数。
转移的时候直接枚举区间最大值的位置即可。
由于 X_i 可以对 n 取 \min , 所以复杂度为 \Theta(N^4) .