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]$如何处理：