NOI2022题解

D1T1 众数

求绝对众数的经典做法是摩尔投票。

维护二元组代表答案和出现次数，合并二元组的时候如果答案相同，次数相加，否则取出现次数大的数作为答案，次数变为大的次数减小的次数。

然后用双向链表维护队列，并且因为总共只会用到 $O(n+m)$个元素，所以可以用垃圾回收。

每个序列的答案可以用值域线段树，合并队列时顺别合并线段树。
线段树的每个节点维护该节点管辖的值域内所有数的摩尔投票值。

然后加入/删除就直接修改线段树叶节点的值，然后自底向上$pushup$就行了。

最后摩尔投票出的值需要检验一下出现次数是不是大于总长度的一半。

时间复杂度 $O(nlogn)$

D1T2 移除石子

首先是$k=0,l=r$的部分。

设计一个dp，$dp[i][j][k]$表示前$i$堆石子，其中有$j$个操作二是从$i-1$以及以前开始的，$k$个操作二是从$i$开始的，是否可行。

然后转移就枚举在当前位置结束的，以及从下一位置开始的操作而数量就行了。

然后是通过一些分析，发现$j,k$的最大值只会取到$2$,并且$j=k=2$的情况是不存在的，证明的话就是这些情况都可以被其他更小的情况覆盖掉。

然后考虑$k!=0$

把状态从可不可行改为最少需要填多少个。

可证明大多数情况下，只要最少需要填的小于等于要求的，那么就一定存在一种方案，把剩余的石子放在不影响答案的位置上。

唯一的例外是 $k=1$时，数组全为0，或者$k=1,n=3,a=1,1,1$

特判就好了。

然后就很套路的dp套dp，首先搜出所有合法的状态，然后以状态进行dp，通过搜索我们发现有用的状态只有不到8000个。

询问的时候对于每个位置，虽然$r_i$很大，但是显然当$r_i>5$的时候都是重复的，所以只需要枚举到5就好了。

D1T3 树上邻域数点/[Ynoi2003] 雾雨魔理沙

建出这棵树的$toptree$，然后维护每个点的子簇内到界点的邻域信息。
然后用换跟$dp$即可求出每个点的子树外的邻域信息。
询问的时候可以$O(1)$合并。

大致是这，但是具体的细节很多。

D2T1 挑战NPC II

设$f(x,y)$表示第1棵树的$x$的子树和第二棵树的$y$的子树能否匹配。

然后有一个显然的性质是，如果存在$x$的某个子树和$y$的某个子树时一样的，那么我们让这两个子树匹配一定不会劣。

然后就把相同的子树匹配掉，剩下不超过$k$个子树。

然后直接写$k!$的暴力匹配好像就能过了。

就是枚举子树之间的匹配，那么对于一对匹配的子树，第一棵树上的子树代销要大于第二棵树上的，那么就保证了每次匹配的两个大小不会超过$k$，然后递归做就行了。

具体复杂度不知道。

树hash可能要写的比较优美，不然会被卡。

D2T2 冒泡排序

首先看$A$性质，我们可以想到做法是每次贪心的把0放前面，正确性略。

首先看B性质，很容易发现这个时候填的数是单调递增的。

因此用线段树维护选每个数时的贡献，然后因为填的数字之间互不干扰没所以取最大的就好了，也可以证明这样子选的数是最优的。

那么接下来看C性质就会很顺，把限制的元素放在开头，然后给区间内的剩余位置加上一个限制要$\geq $某个数，那么还是按照$B$性质做，只是从限制的值域范围内转移就行了。

正解就是A和C结合起来。

枚举$x$，把大于$x$的限制当1，等于$x$的限制当0，然后贪心的选出最靠前的位置，并给剩下的位置加个下界。

然后按照C做就好了。

D2T3 二次整数规划问题

首先显然，如果一个数可以选$2\to k-1$内的数，那么一定不会选$1,k$。

那么我们可以通过迭代求出每个数的取值范围，并把只能取$1,k-1$的贡献单独拿出来。

然后$k=3$的话，三种取值的数的个数直接就确定了。

$k=4$，贪心的把没确定取值的数全放在$2$或全放在$3$，可证明这样是对的。

$k=5$是最麻烦的。

我们设答案中取了$x$个2，$y$个4.

那么答案可以写成 $G(n^2-xy)+v_{2}x+v_3(n-x-y)+v_{4}y$的形式。

整理一下常数可以写成 $Ax+By-Cxy$的形式。

再画一下可以变成$-V(x-A)(y-B)+C$的形式。
也就是说我们要最小化$(x-A)(y-B)$的值。

我们把$(x,y)$看成二维的点，那么这就是平移过后的最小值。

首先答案一定在$[minx,maxx],[miny,maxy]$的矩形里。

并且可证明$(minx,miny),(minx,maxy),(maxx,miny)$是总可以取到的。

平移和的点如果不在第三象限，那么答案一定可以在上面三个点中取到。

否则，就是在第三象限，这是一个经典问题，最小乘积生成树。

求出所有点的右上凸包，可证明答案一定会在凸包中。

凸包的求法就类似最小乘积生成树的分治。

但是那个题里是要求最小生成树，这里则是要求：

某个数取2会有$A$的收益，取$4$会有$B$的收益，同时限制某些数不能取值相等，某两个数不能同时取$2,4$，求最大收益。

限制相等的数可以缩成一起，然后就是经典的切糕模型，可以用最小割求解。

复杂度证明可见Itst的解题报告。