CVBB ACM Team

题意:水。

题解:摸。

题意:给出$n$，求$a,b$使得$a + b = n$且$LCM(a, b)$最小。$(2 \leq n \leq 10^{9})$

题解:显然$LCM(a, b) \geq max(a,b)$，盲猜一手$a,b$成倍数关系时最小，$O(\sqrt{n})$枚举$n$的约数即可。

题意:给定一个$1$到$n$的排列，每次可以选择一个连续的子区间对其进行错位排序，问最少进行几次错位排序可以使得序列有序。

题解:如果本身就是有序的需要零次。否则，首先把有序的前缀和后缀全扔掉，中间部分如果本身就是一个错位的，那么只需一次，否则如果有在正确位置上的，就要两次。

题意:给出一个长度为$n$的环，保证$n$为奇数，每个位置有一个元素，每次操作选定一个元素，将其替换为相邻两个元素的和并删除相邻的两个元素，直到只剩一个元素。求最后剩下这个元素的最大值。$(1 \leq n < 2 \cdot 10^5)$

题解:一开始用合并果子的方法优先队列各种限制（甚至pair套pair套pair）直接wa飞了。后来发现每次最少会删掉$\dfrac{n-1}{2}$个互不相邻的数，因此分类讨论dp一下就可以。

题意:给出一个$n \times m$的方格，每一行被分为了$k_i$个连续的区域，每个区域只能放一个物品，现在设$a_i$为第$i$列的物品个数，求$\sum_{i=1}^{m}{{a_i}^2}$的最大值。$(1 \le n,m \le 100)$

题解:区间dp，设$f_{i,j}$为区间$[i,j]$的物品数量平方和最大值，转移时考虑将尽量多的物品放到同一列上：$f_{i,j}=f_{i,k-1}+x+f_{k+1,j}$，其中$x$为所有包含第$k$列的区域中被完全包含于$[i,j]$的数量。

题意:交互题。一个未知的长度为$n$的排好序的序列，一共有$k$个不同的数（$k$未知），你需要经过不超过$4k$次询问得到这个序列。每次询问一个区间，返回这个区间中出现次数最多的数及其出现的次数，如果有多个数满足条件，返回最小的那个。$(1 \le n \le 2 \cdot 10^5,1 \le k \le \min(25000,n))$

题解:考虑先处理$[1,n]$里出现次数最多的数，设其所处区间为$[l,r]$，则再分别处理$[1,l-1],[r+1,n]$，以此类推，直到所有区间都处理完毕。我们只需保证对每一种数字做$4$次询问得到其出现的准确区间即可保证最多进行$4k$次询问。

设现在来到了区间$[l,r]$，考虑如何处理：首先询问一次$[l,r]$，设返回值为$(x,y)$，设$z$为最大的满足$z \le y$的$2$的次方，考虑所有$z$的倍数$i$，由上述$z$的性质可得只有一个或两个处于$[l,r]$中且满足$a_i=x$。若只有一个$i$满足上述条件，那么询问$[i-z+1,i]$和$[i,i+z-1]$，其中必有一个最多的数也是$x$，因此我们可以得到数字$x$所处区间的左边界或右边界，我们已经知道$y$因此可以知道另一个边界值；若存在$i,j(i < j)$均满足上述条件，那么询问$[i-z+1,j]$即可获得数字$x$所处区间的左边界，我们已经知道$y$因此可以知道右边界值。

在查找所有所有$z$的倍数$i$是否满足条件时，我们可以直接暴力地枚举$[l,r]$内所有$z$的倍数，如果对应下标被查找过则直接判断，否则查找一下即可。可以发现因为我们所查找的数字的出现次数是不增的，$a \cdot 2^b$同时也是$2^{b-1},2^{b-2}, \cdots$的倍数，因此所有查过的下标一定会被用到。所以，对于上述第一种情况，我们最多询问了$1+1+2=4$次，对于上述第二种情况，我们询问了$1+2+1=4$次，满足题意。