CF1129

link

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$次,每次把点随便排列,二分。————————-

评论

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×