A.带余除法

我们不难考虑找出 \(q\) 的上下界，不难发现范围是 \([\lfloor\frac{n}{k+1}\rfloor+1,\lfloor\frac{n}{k}\rfloor]\)。当然这个区间可能为空。只需算出区间长度即可。

B.奖牌排序

不难考虑到分别按照三个关键字排序，然后对于每个小朋友找到每个关键字下的排名（同分取第一个），取一个最小值就做完了。

C.三目运算

每年必出的大模拟，但这题好像还有图论？我们考虑找出每个 ? 匹配的 :，这个是不难做的，用一个栈就行。

接下来考虑把一个分段常数表达式看成三部分：? 前面的，? 和 : 之间的，: 后面的，记为 \(u,a,b\)。

接下来考虑 \(u\) 对 \(a,b\) 分别连边，就形成了一棵树。于是暴力就是好想的了，每次询问遍历一遍树。但是这样很容易被卡，例如下面这样：

这种结构会导致每次遍历是 \(O(n)\) 的，直接超时。于是考虑怎么优化。

发现慢的原因是每次询问都要遍历一次树，那么考虑所有询问一起遍历。

具体地，把所有询问离线下来，扔到一个序列里排序去重，每个树上的点必然把一部分分到左子节点，另外一部分分到右子节点。只需要记录这个点处理的是序列中的 \([l,r]\) 部分就可以完成划分操作。到达叶子节点直接赋值即可。其实上面的过程就是整体二分。

D.配对序列

看到最优化问题，不难想到贪心或者动态规划。仔细构造几组样例就可以发现贪心假了，于是考虑动态规划。

设 \(f_{i,0}\) 表示第 \(i\) 个位置作为一个子序列的开头，已经凑出来的配对子序列的长度最大是多少；\(f_{i,0}\) 表示第 \(i\) 个位置作为一个子序列的结尾，已经凑出来的配对子序列的长度最大是多少。

不难得出转移方程：\(\displaystyle f_{i,0}=\max_{j<i}(f_{j,1})\)，其中 \(a_j\ne a_i\)；\(\displaystyle f_{i,1}=\max_{j<i}(f_{j,0})+2\)，其中 \(a_j=a_i\)。

暴力转移时间复杂度是 \(O(n^2)\) 的，考虑数据结构。发现最值可以使用线段树维护，只需要把原序列离散化然后使用线段树转移即可。第 \(j\) 棵线段树的 \(i\) 节点存的值为 \(f_{i,j-1}\)，其中 \(j=1\) 或 \(j=2\)。