省选/NOI-

P15301 [ROI 2012 Day 2] army 汗国军队 思路 首先直接做是不太好做的，因为要同时满足两个限制： 最长的 LIS 长度为 $k$； 给定的长度为 $k$ 的 $g$ 数组必须在序列里按顺序排列。 考虑拆分这两个问题。 首先忽略第二部分，考虑第一部分。 我们发现，从大到小地在数组任意位置插入所有数就可以构成所有排列。 那模拟这个插入的过程。 容易发现 LIS 数组的每个位置相比上一个位置最多增加 $1$，这是显然的，不然你每次都只加了一个数还能多更多不成。 那就考虑对整个 LIS 数组进行一个差分，这样每一位都是 $1$ 或是 $0$，整个数组可以用状压表示。 因为此时插入的数比已有的其它数都要大，所以它后面的数无法接在它自己后面使得 LIS 变长，而它一定可以接在它前面的任意数后面使得 LIS 变长 $1$。 插入的过程就相当于在插入的位置加上一个 $1$，然后删掉后面最近的一个 $1$（在本位多一，后面自然就要少一，但是原本的 $0$ 可以继承本位，所以不变），这一步可以通过位运算轻易地得出。 考虑一个 $f_{i,j}$，$i$ 表示要插入的数，...

P15939 [JOI Final 2026] 传奇团子吃家 题解 思路 考虑前缀和 $P_i$ 表示前 $i$ 段甜减辣的净甜度。则对于固定的左端点，贪心策略为：每口都恰好吃到净甜度增加量 $\ge K$ 的最早位置。这等价于在模 $K$ 意义下推进状态。 我们离线处理询问，按右端点扫描。维护一棵模 $K$ 的权值线段树，存储每个余数状态对应的答案，并利用并查集合并等价状态。遇到奇数段（甜）时执行区间加操作；遇到偶数段（辣）时执行区间合并与删除。 动态开点线段树维护区间加法与单点查询，下标域 $[0, K-1]$。 用 set 维护当前仍有效的模余数集合。 带权并查集维护状态间的差值关系。 扫描 $i$： 若 $i$ 为奇数，计算甜团子带来的增量，执行线段树区间加，并尝试与已有代表合并。 若 $i$ 为偶数，将受辣团子影响的一段余数全部合并到新余数上，并从集合中删除旧余数。 回答所有右端点为 $i$ 的询问。 时间复杂度 $O((N+Q)\log K)$，空间 $O(N\log K)$，可以通过本题。 代码 ...

P15819 [JOI 2015 Final] 舞会 / Ball 思路 首先我们发现直接做是困难的，所以考虑二分最后一个贵族的 $d_i$ 大小大于等于多少。 有一个很经典的 trick：将所有 $\ge d_i$ 的贵族改为 $1$，其他改为 $0$。 考虑到我们最后若想要此种情况成立，需要最后留下来的贵族是 $1$ 才行。 我们观察题目的操作，容易得出当知道所有数时，可以用 deque 来维护。 定义 deque 中的每一位是当前局面下使得这一位为 $1$ 的最小值。 那么对于初始固定的位置，若它对应的贵族是 $1$，则值是 $0$，若是 $0$，则设为极大值。 若这个位置没有初始值，则设为 $1$，因为需要往这里填入一个是 $1$ 的贵族。 按照题意模拟，每次取出前三个，若要使得加到最后的是 $1$，则前三个中必须至少有两个 $1$，枚举三种情况，取最小值，将其加到末尾。 最后因为每次会删除三个，增加一个，所以就是减少两个，又因为初始是奇数，所以相当于最后一定只剩一个。 将最后这一个提取出来，并判断它为 $1$ 时所需要的 $1$ 数量是否小于等于总的 $1$ 数量即可。...