2023牛客多校训练营1

Linxrain的博客 / 2023-08-30 / 原文

A . Almost Correct

给你一个长度$n ( 1 \leq n \leq 16)$的$01$串，要求你给出一种排序算法使得长度为$n$的$01$串中只有该串不能被排好序

此处的排序算法指，一个长度不超过$120$的$pair$序列，每次把$pair$两个位置的数字比较并排序

假设原串有$cnt$个$1$

我们考虑一条新串，然后先把第一个为$1$的位置和其他所有为$1$的位置进行交换，这样一来

存在原串为$1$的位置，新串为$0$，那么新串该位置不再是$1$
不存在原串为$1$的位置，新串为$0$，那么新串有其他位置是$1$

我们继续将除了原串第一个$1$外的所有位置$log$和它们后面的所有位置从$n$到$loc+1$进行交换，然后将第一个$1$的位置$loc$和$n-cnt$到$loc+1$进行交换

不难发现，如果存在原串为$1$的位置，新串为$0$，那么原串第一个$1$的位置新串此时为$0$，已经排好

否则新串的$1$一定比原串多，我们空出一格再排序即可

Code

C . Carrot Trees

长度为$n ( 1 \leq n \leq 10^6) $，$ m ( 1 \leq m \leq 2 \times 10^5 )$次询问，每次询问进行区间加$x_i$或区间减$k$，与往常不同的是，当前值小于$k$的项不会做减法，问最多能减去多少个$k$

那么有

\[该点成功减去的次数=\lfloor \frac {该点减法次数 \times \ k + 该点最小值}{k} \rfloor \]

线段树分治求解，复杂度$n\ logn\ logm$

Code

题解$n\ logm$不知道怎么做的，会了再说