NOI2022 题解

Larunatrecy · 2022-09-11 19:49:14 · 个人记录

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的话，三种取值的数的个数直接就确定了。