CF1129
A
随便搞搞就做完了。
B
考虑一个序列:$n$个$0$,然后$1$个$-1$,然后$m$个数$a_1\dots a_m$,其中$a_1\ge 1,a_i\ge 0$,设$s=\sum a_i$
差就是$(s-1)(n+1+m)-ms=(n+1)s-n-1-m=k$
所以$s=\frac{k+m+n+1}{n+1}$。
枚举$n,m$,判断下是否合法($s$是整数且$s\le 10^6m$。
C
设$f(l,r)$表示得到S[l:r]
的方案数。
然后用trie判断一下每个后缀是否出现过。
D
设$f_i$表示前$i$个数可行的划分方案数。
设$s_j$表示$(j,i]$区间内只出现了一次的元素个数。
则$f_i=\sum_j [s_j\le k]f_j$
设$p_i$表示$a_i$上一次出现的位置。
当i+=1
的时候,$s_{p_i...i-1}$+=1
,$s_{p_{p_i}...p_i-1}$-=1
。
然后分块维护一下就好了。
E
记一次询问为$(S,T,v)$。
首先把这个树以$1$为根。$d_i=(\{1\},\{2,3,...,i-1,i+1,...,n\} a,i)$表示$i$子树大小-1。
接着把点按照$d$升序排序为$v_1,v_2...v_{n-1}$
记录$X$集合为还没有找到父亲的点集合。
初始$X=\{v_1\}$
按顺序从$v_2$开始考虑每个点:
询问$(\{1\},X,v_i)$得到$v_i$的儿子个数$k$。
然后$k$次,每次把点随便排列,二分。-------------------------