CVBB ACM Team

• 日期：2020.7.27

• 比赛地址： 传送门

• 做题情况：lxh(-)，tyx(EJK)，gyp(BC)

构造一个$1$到$n$的排列，使对于任意$1 \le i \le n$，可以从这个排列中取出一个连续的长度为$i$的部分，它们的和$\mod \ n = k$，若没有解输出-1

$1 \le n \le 5000$，$0 \le k < n$

首先我们发现$n$是奇数的时候必须有$k=0$，$n$是偶数的时候必须有$k=\frac{n}{2}$，其余情况均无解。$n$是奇数的时候，构造$n,1,n-1,2,n-2 \ldots$，$n$是偶数时构造$n,\frac{n}{2},1,n-1,2,n-2 \ldots$即可

有一个排列$1,2 \ldots n$，$m$次操作，每次操作对其做$x$次$K$-约瑟夫变换，问最后这个排列是什么，$K$-约瑟夫变换的意思是，每次进行约瑟夫游戏，并依次将出局的人放到下一个排列

$1 \le n,m \le 10^5$，$n \times m \le 10^6$，$1 \le k \le n$，$1 \le x \le 10^9$

$K$-约瑟夫变换本质也是一个置换，这个置换是固定的，所以我们对于每个环可以将其长度$\mod \ K$，这样我们可以在$O(len)$时间处理每个环变成了什么样，至于约瑟夫变换，可以每次通过在平衡树里query相应位置的数在$O(n \log n)$的时间内解决，因此总复杂度为$O(nm \log n)$

定义一个序列是$K-Bag$的，当且仅当它是由若干个$1$到$K$的排列组成的，例如$1\ 2\ 3\ 3\ 1\ 2\ 3\ 2\ 1\ 1\ 2\ 3$，现在给出一个长度为$n$序列，问它有没有可能是一个$K-Bag$序列的子序列

$1 \le n \le 10^5$，$1 \le K \le 10^9$

当$K > n$的时候，这个序列最多被分成前一半后一半分别是两个排列的一部分，单独判断一下即可，当$K \le n$时，我们考虑在$O(n)$的时间内求出某个位置以及它之前的$K-1$个位置能否组成一个完整的排列，然后从头和尾分别找到一个最长的部分可以作为一个排列的一部分，然后我们从头上开始$K$个一步跳，如果能跳到尾部的部分就说明可以，如果都不行就不行

第一小时：tyx和gyp开始想E，lxh开始想D，tyx先猜了一个结论但是WA，后来发现有问题并找到正解通过，lxh写出了一个版本D但是超时

第二小时：lxh开始想G，tyx开始想K，gyp连续通过了B和C题

第三小时：tyx写出了K但是WA，在找问题的时候lxh开始构造G但是一直WA，tyx找到了K的问题并通过

第四小时：tyx开始想J，gyp开始想H，tyx想出了J并开始写但是一直超时，后来发现因为多组数据有一个部分没有初始化，修改后通过

第五小时：gyp开始写H，lxh继续构造G但是没有通过，gyp最后没能写完H

• 要注意各种细节从而尽量避免罚时
• 多组数据一定要注意初始化