2024.10.1 题目

热烈祝贺新中国成立 $75$ 周年！题解：2024.10.1 模拟赛

博弈

找规律 树 哈希 位运算

有 $n$ 点的树，每条边都有边权 $w_i$。对于任意不相邻的无序点对 $(u,v)$，都要将 $u$ 到 $v$ 的简单路径上的所有边权 $w_i$ 取出来组成序列 $l$，接着有两个人在 $l$ 里面取数。要求后一个取的数要不大于前一个人取的数。现让你求出 $(u,v)$ 的数量，满足取数时第一个人有必胜策略。$T$ 组数据。

跳跃

序列dp 前缀和

有长度为 $n$ 的序列 $a$，现有人在位置 $1$ 跳跃最多 $k$ 次，第一次跳跃向右，第二次跳跃向左……设从 $i$ 跳到了 $j$（$i$ 可以等于 $j$），那么分数就记上 $\sum _{i=1}^j{a}_i$ 分，分数在任何情况下都不能为负，问你跳完后最大分数是多少。$T$ 组数据。

大陆

构造 树

有 $n$ 个点的树，要你分成若干块，使得每一块的点数都在 $[B,3B]$ 之间。每一块要指定块的头，对于任意点 $x$，若 $x$ 的头为 $y$，那么需要满足 $x\to y$ 的简单路径上面所有的点都要和 $x$ 在同一个块。输出方案。

排列

平衡树 三元上升子序列

有长度为 $n$ 的排列 $a$，需要进行 $q$ 次操作，每次给定 $(l,r,k)$ 将 $a_l\sim a_r$ 循环右移 $k$ 次，然后判断是否满足 $(i,j,k)$ $(1\le i<j<k\le n)$ 满足 $a_i<a_j<a_k$。