ZJUT夏季考核8.16题解
声明
此文章为ZJUT暑期考核的题解,和我队友qinye_leaf一起整理编写而成,之前一直没发,现在发
补题链接:20260816 ZJUT暑期考核 补题 - Codeforces
不想写题了,所以来写题解了,参考代码可以看我补题里面的提交
A. A&B problem
知识点
博弈论,模拟
观察
虽然说看似Alice搬运1到最前面是一个不错的策略,但是仔细想一下的话会发现,Bob可以直接在你正前方拦截,这样就没法实现搬运了,所以这个策略并不是最优解 (样例因为数据规模较小,所以给人一种错觉,认为搬运1是正确的)
操作的实质我认为是拦截,因为一旦交换,前面的数就无法再到后面去了,所以对于Alice来说,把一个小的数字交换到前面是有效的,因为这个小的数字相当于被锁死在了前面,不会再换到后面了
既然没有办法通过搬运较小值使得前面的存在值更小,那么我们得换一个思路
我们的目标是让字典序更小,这说明,开头的数字更加重要,那么很显然,我们应该优先保证开头的数字更小,那么我们是否应该优先选择保证开头数字更小而暂时不考虑后面呢?
简单证明一下:
要是你不考虑前面的,而优先考虑后面的,那么Bob必然会把前面字典序变大,显然不如优先考虑开头更优,所以优先考虑开头是更优的
接下来,我们来考虑怎么让开头的数字更小
手玩小样例找规律
当n比较小的时候,比如n等于1,2,3时,答案是显然的,当n>=4时,就需要博弈了
n=3时,结论是先看后面两位,要是后面两位交换更优,先交换后两位,否则先前两位
比如数组是1 2 3 4
可选位置是1,2,3,如果我先选择了3,对手就会选择2,最后剩下1,得到4 1 2 3,最劣
如果我先选择2,对手就会选择1,剩下3,得到3 1 4 2,比刚才略好一点
如果我先选择1,对手就会选择2,剩下3,得到2 3 4 1,最优
(当第一步确定后,剩余数组长度小于3,结论已给出,所以后手操作确定)
可以看出,我们通过选择1,锁定了2在开头,从而保证了第一个位置最优
又比如,数组是1 3 2 4
如果我先选择3,显然最劣,跳过
如果我先选择1,对手会选择3,得到3 4 1 2
如果我先选择2,对手会选择3,最后得到2 1 4 3,显然是最优决策
所以当p3<p2时,直接选2更优
双比如,数组是3 2 4 1
此处显然先选择3最优,之后对手只能选择1,所以得到2 1 3 4
叒比如,数组是4 2 3 1
此处依然是选择3更优,要是先选择了1,4就到第二位了,显然也不如先选3更优
上面两个情况一起看,就能看出什么时候选3了:
在双这个例子中,选3是因为我把一个小的数字交换到前面了,对手只能采取防御性操作,否则将留下大优势给我,所以被迫选择1
在叒这个例子中,即使选1看着不坏,但是不如先操作后面的,把劣势留给后手让其被迫防御,做出不优选择
因此当p4<p2时,选3更优
结论
只要看前四位就能决定当前第一位的值,因为再往后的博弈影响不到第一位,
简单证明:
当我选择第4位去操作时,前三位的状态相当于先后手互换,变成Bob先手,那么前四位将变成字典序最大,显然不优
前四位的决策总结起来是:
假设先手是Alice
设前四位为p1,p2,p3,p4
若p3<p2小 操作2 则一定最优 否则后手可以先操作1 直接截断优势
若p3>p2大 但是p4<p2 则操作3 后手必须操作1 不然大劣势
否则只能操作1 不然后手换大的
进一步博弈
不知道你们有没有玩过围棋,下围棋常常是当你在某一片已经确定胜利或失败后(但是仍然还剩下几步时),直接放弃不管,去下别的地方,因为既然胜负已分,那么不如早些结束,去别的地方争抢地盘,等到最后再来走这些不得不走的棋
同样的,这一题也适用这个方案.
当你交换完某些部分后,当某一段只剩下长度为1的博弈了,直接放弃就行,选择继续操作后面创下优势,最后回头再处理这些位置
比如1 3 2 4 这个例子中,假设Alice先手,那么她选择2,但是Bob没必要跟上去选择1,因为这里的局面已经固定了,不如选择1,直接去操作后面的,这样先后手交换,对Bob反而更有利
这样完整逻辑就齐了,代码实现注意先后手交换的问题和边界len<4的情况就行
时间复杂度O(n)
B. Entangled dots
知识点
dp,树状数组,线段树
观察
这种可满足性的问题显然会令人想到二分图或者并查集,但是注意到一个约束可能和很多个约束相矛盾,不适合建图,因此需要其他的方法
既然不能考虑和当前约束违背的约束,那么反过来,考虑和当前约束不违背的约束呢?
分析一下什么情况是不矛盾的,一共有三种情况(为什么还是比较好理解的):
第一种,他们宣称的最大值一样; 后面两种,他们宣称的最大值不在区间的交集内部
题目提到,l和r是单调递增的,所以如果约束A和B不矛盾B又不和C矛盾,那么A和C也不矛盾
证明不会,可以问问AI,这里就不证明了
结论
所以可以考虑不矛盾的情况,那么这说明我们可以采取dp来完成这一道题,每次看前面合法的约束来进行转移就行
转移方程:
维护转移
注意到需要求的是前面满足某个条件的最值,而且求的都是区间最值,那么显然适用树状数组或者线段树维护,因为不然需要O(n)的查找,会爆
开一颗大小为n的树状数组,然后每个位置上放的是dp值,最后再维护最大值就行了
比如要加入当前的dp值,那么在p_i位置上放入dp_i,然后再做一遍树状数组或者线段树的更新,这样查询[1,p]就能得到不超过p的所有约束的最大dp值了,符合状态转移方程,另外几个值也是一样的维护方式(没有见过这个方法的,可以先试试先用树状数组写最长不下降子序列,会更好理解)
时间复杂度O(nlogn)
当然有更快的双指针法,时间复杂度可以O(n)(我不会,璃歌学长会)
另外,这题可以被解答的关键条件是递增,否则无解
C. Tree kx+b
知识点
树,dp,数学
观察
假设这棵树就只有两个点,那么根节点的取值显然是有一个最优区间的,
比如:假如树是 3—10
根为3,那么根取[3,10],得到的答案都一样
假设这颗树只有三个节点:
1 | 6 |
那么6调整到[1,5]都是最优的
因此可以发现,调整后的值存在一个最优区间,只要都在这个区间内,都是最优的
那么考虑每个节点的最优区间怎么计算
合并最优区间,计算最优区间
对于叶子节点,最优区间显然是[x,x]
对于非叶子节点,考虑怎么计算当前的最优区间,此时问题抽象成:
你有一堆区间,每个区间内有一个点,可以在自己的区间内移动,如果移出去了,那么会付出额外代价;你还有一个点,可以移动这个点,然后你要找一个新区间,使得这个区间内取的点,到所有区间内的点的距离加上移动这个点的代价之和最小
对于父节点,考虑父节点取值到子节点最小距离累加,若子节点取了超越最优区间的值,要付出额外代价
与父距离-1,自己与其子节点距离增加>= 1,显然付出的代价增加,不如让父节点靠近区间
因此,只要考虑父节点的移动就行了,子节点的点必然是不会移出自己的区间的
那么问题可以化简为:
你有一堆区间,加上区间[x,x],你要找一个新区间,使得这个区间内取的点,到所有区间的距离之和最小且相等(距离定义为到区间上所有点的最短的那个距离)
设每个区间的取值为[l,r]
对于这种距离函数,<l_i时 斜率=-1,l,r斜率0,>r 斜率+1
那么这个距离函数就是一条折线,斜率初始为-x,每经过一个点斜率+1,当斜率为0时最优,也就是中位数
故把所有端点排序 2 * m个端点,此时父节点最优区间为m~m+1 将新值(新区间内随便取一个就行)然后带入回原来的式子算总代价即可
时间复杂度为O(nlogn)
D. Sliders (easy version)
技巧
对于滑块位置$p_j$,如果前后有滑块顶过来,他们的连续段位置是等差为1的
我们可以通过构建新数组$c_j$,含义是滑块j此前的空位数量 满足$p_j = c_j + j$这样对于连续段,他们的取值都是一样的值,对于后面的处理更加方便
同时由于是线性操作,根据期望线性性质,对于期望计算简化为
这个技巧不使用也能正常解决问题,但是使用会方便很多,下面的计算是建立在这个技巧之上的,没使用的版本不做讲解
对于每次询问的j号滑块,我们要计算$c_j$最终取值的期望,自然考虑$c_j$位置的取值
讨论操作影响
对于$c_j$,第i次操作$(id_i,r_i)$下:
- 若$id_i == id_j$,则$c_j = r_i$
- 若$id_i < id_j$即本次操作在其左侧,则$c_j = max(c_j,r_i)$
- 若$id_i > id_j$ 即在右侧,则$c_j = min(c_j,r_i)$
故$c_j$最终的取值只可能在所有r的取值和$c_j$初始值处 对其升序排序
期望
v为所有可能取值 故我们需要知道最终落在每个位置的概率
转换概率计算方式
难点2:转换间接法计算概率方式 直接计算不容易处理 故通过间接法计算
现在子问题变成 如何计算$P[c_j > v]$
子问题
讨论操作种类(对应上文):
我们要考虑是不等式:
是否成立
- 若$r_i > v \rightarrow 1$ (不等式值必定为1 即1-设置器)
- 否则 $ri <= v \rightarrow 0$ (即0-设置器)
- 左侧:若$ri > v \rightarrow 1$ 否则不等式值保持不变
- 右侧:若$ri <= v \rightarrow 0$ 否则不等式值保持不变
经过讨论分类,那么我们需要统计的实际上是:
- A种1-设置器
- B种0-设置器
- m-A-B种保持不变
在随机排列中,不改变操作虽然会插在序列的各个位置,但它们不影响状态
真正决定最终状态的是:最后一个设置器是1设置器,还是0设置器
因为所有 m 个操作随机排列,那么只看这 A+B 个设置器的相对顺序,它们也是完全随机均匀的(不改变操作没有影响这个相对顺序)
故若不等式成立 则A+B序列的最后一个位置一定是A操作
这里需要注意一个特判
若A+B = 0 则全为不改变操作 所以取决于初始状态$c_j$是否>v
至此概率计算公式推导完成
如何快速计算所有概率P
这里的意思实际上是,为了计算所有概率,方法是对于每一个可能的位置计算一下概率,所以需要有一个递推关系计算当前询问的所有概率
怎么才能实现相邻P之间的转移呢
首先边界P[cj > -inf]为1 所有1,2操作都是1设置器,3操作都是不改变操作
数学归纳法P[cj > v-1]已知,求P[cj > v]即处理r = v的情况:(操作种类对应上文)
r = v从1(设置器) -> 0- 左侧:
r = v从1 -> 不改变操作 - 右侧:
r = v从不改变操作 -> 0
O(m)处理即可算出所有取值的对应概率P,带回式子计算即可得到最终期望
最终时间复杂度:O(qmlogm)