[ CSP - S 2024 赛前集训] 20240930 模拟测总结

· · 个人记录

A - game

题目大意

（前面博弈的部分略，反正我会）\ 给定一棵 n 个节点的树，每条边都有一种颜色，求有多少条路径满足存在至少一种颜色使得其在路径中的出现次数为奇数。\ 对于 27\%（实测 44\%）的数据，n\leqslant5000；\ 对于 100\% 的数据，1\leqslant n\leqslant 5\times10^5。

模拟测概况

期望得分：27\ 实际得分：44\ 不会哈希，只打了第一档暴力分。

正解

用异或哈希存一下树上每个点到根节点的路径中每种颜色的数量是奇还是偶。如果一条路径上只有出现次数为偶数的颜色，那么这条路径所对应的两条到根节点的路径哈希后应该是相等的。开个桶（unordered_map）存一下每个哈希值的个数，最后再用组合数算一下就行了。

小结

B - jump

题目大意

给定长度为 n 的整数（可以为负）序列 a，初始时位于位置 1，贡献为 0。\ 令每回合开始时的位置为 x，在奇数次回合可以跳至位置 y (x\leqslant y\leqslant n) 并将贡献增加\sum\limits_{i=x}^ya_i；在偶数次回合可以跳至位置 y (1\leqslant y\leqslant x) 并将贡献增加\sum\limits_{i=y}^xa_i。要求任意时刻贡献不得为负。\ 求至多 k 回合后贡献的最大值。\ 对于 50\% 的数据，n,k\leqslant1000； \ 对于 100\% 的数据，1\leqslant n\leqslant1000,1\leqslant k\leqslant10^9。

模拟测概况

期望得分：50\ 实际得分：50\ 打了 50 分的 DP。

正解

最优的方案一定是，先用最少次数跳到最大子段和区间，再反复在最大子段和区间左右横跳。因为一次性跳可能会导致负贡献，所以为了跳到最大子段和区间，需要先向右跳到一个新位置，再在以这个位置为右端点的最大子段和区间左右横跳积累贡献，然后再向右跳下一步。DP求一下跳到每个位置所需的最少次数和最少次数下贡献的最大值即可。\ 另外，考虑到 k 可能很小导致跳不到最大子段和区间，所以最后的答案应该是【跳到每个位置最小次数下的最大贡献加上在这个位置左右横跳的贡献】的最大值。\ 时间复杂度 \text{O}(n^2)。

小结

模拟测概况

期望得分：100\ 实际得分：100\ 一道很简单的构造题，干脆不写解法了吧，反正我会。

D - permutation

题目大意

给定一个长度为 n 的序列 a 和 q 次操作，每次操作会将序列中的子段 a_l\~a_r 循环右移 k 次（0\leqslant k\leqslant r-l+1，也就是将子段 a_l\~a_{r-k} 和 a_{r-k+1}~a_{r-l+1} 互换位置），求每次操作结束后序列中是否存在三元上升子序列（是否存在 i_1<i_2<i_3 使得 a_{i_1}<a_{i_2}<a_{i_3}）。\ 对于 40\% 的数据，n,q\leqslant400；\ 对于 100\% 的数据，1\leqslant n,q\leqslant1.2\times10^5。

模拟测概况

期望得分：40\ 实际得分：40\ 只写了 40 分的暴力。

正解

使用下标平衡树（文艺平衡树指的就是下标平衡树吗？）处理交换操作（使用 \text{FHQ-Treap}，先分裂再换个顺序合并就行了），并维护每个子树内的最大值、最小值、最大的二元上升子序列首元素、最小的二元上升子序列尾元素（分别记作 max1,min1,max2,min2），以及是否存在三元上升子序列。\ 解决问题的关键在于实现维护 max2 和 min2。\ 以维护 min2 为例，首先先用左右子树内的 min2 和根节点更新答案，如果此时整个子树内不存在三元上升子序列，那么右子树内比左子树的 min1 大的所有元素必然单调不增，因此只要不断往右找，找到 max1 大于原左子树 min1 的最靠右的子树就可以更新答案了。维护 max2 同理。这么做可以将更新的复杂度降到 \text{O}(\log n)。\ 最后输出整棵树的答案即可。\ 时间复杂度 \text{O}(n\log^2 n)。

小结

总结

这次模拟测尝试先打暴力，取得了良好的成效。以后也要继续优先打暴力。