热烈祝贺新中国成立 $75$ 周年！题目：[[2024.10.1 题目]] ![[LZH使用文明用语经典咏流传.webp]] ## 博弈 有 $n$ 点的树，每条边都有边权 $w_i$。对于任意不相邻的无序点对 $(u,v)$，都要将 $u$ 到 $v$ 的简单路径上的所有边权 $w_i$ 取出来组成序列 $l$，接着有两个人在 $l$ 里面取数。要求后一个取的数要不大于前一个人取的数。现让你求出 $(u,v)$ 的数量，满足取数时第一个人有必胜策略。$T$ 组数据。 --- 首先，我们来思考一下什么时候有必胜策略，什么时候又没有必胜策略。显然，当最小的数的数量为奇数时，我们直接选择最小值就行了，因为肯定是对面选不到数。那当最小数数量为偶数时呢？ 经过周密的考虑，我们发现数字数量只要有一个奇数就是有必胜策略的。为什么呢？我们可以选择最小的那个奇数次数的数，此时对面肯定会选择这个数或者选择更小的数。如果对面选择更小的数，那我们我们就赢了，因为我们会出最后一个最小的数；如果对面跟着选同样的，那么我们也能赢，因为一直这样子当该数出完了后，我们又能出到最后一个最小的数。 现在我们来考虑统计答案。发现统计含有奇数数量的路径数量不好统计，因此我们可以反向思考，用所有方案的数量减去只含有偶数数量的路径数量。 看到偶数，我们可很容易想到异或运算，因为偶数个相同的数异或起来答案为 $0$，这就代表着一条路径如果异或值为 $0$，那么这条路径上任意数的数量都为偶数。 同样地，我们统计 $p_i$ 表示为 $1$ 到 $i$ 路径上的数的异或值，对于两个不相等的数 $i$ 与 $j$，如果 $p_i=p_j$，那么 $(i,j)$ **可能** 是满足条件的。为什么是可能呢？例如 $2\oplus 1=3$，那么难道就以为着 $(2,1,3)$ 这条路径满足条件？显然不是，因此我们需要减少异或冲突的概率。 将边权离散化一下，然后对于离散后的值 $r_i$，用 $b^{r_i}$ 替换，其中 $b$ 是一个大质数，使用无符号 $64$ 位整数的自然溢出，再加上亿点点运气，就可以成功求出答案。 ## 跳跃 有长度为 $n$ 的序列 $a$，现有人在位置 $1$ 跳跃最多 $k$ 次，第一次跳跃向右，第二次跳跃向左……设从 $i$ 跳到了 $j$（$i$ 可以等于 $j$），那么分数就记上 $\sum\limits_{i=1}^{j} a_i$ 分，分数在任何情况下都不能为负，问你跳完后最大分数是多少。$T$ 组数据。 --- 对于这道题，我们可以很容易写出 $\mathcal O(n^3k)$ 的 dp。令 $dp_{i,j}$ 表示为花费 $i$ 次跳跃到 $j$，最多获得多少分数。对于 $j$，我们枚举它从 $k$ 跳过来的，那么 $dp_{i,j}=\max dp_{i-1,k}+\sum\limits_{l=k}^j a_l$。对求和分使用前缀和优化，即可将时间复杂度缩至 $\mathcal O(n^2k)$。 接下来考虑优化。不难发现，$k\rightarrow j$ 的路径可以转化成 $k\rightarrow j-1$ 的路径在加上 $a_j$，因此我们可以将枚举 $k$ 的部分省去，时间复杂度变为 $\mathcal O(nk)$，可以获得 $50$ 分。 下面就是玄学的地方了。观察样例，我们发现这个人到后期基本上都会跳到最大字段和，然后来回刷分，前面则是攒分跳到那里。因此，我们预处理每个点左右的最大字段和，然后 $i$ 只枚举到 $5000$，统计答案的时候就在那里刷分就行了。时间复杂度 $\mathcal O(n)$。 ## 大陆 有 $n$ 个点的树，要你分成若干块，使得每一块的点数都在 $[B,3B]$ 之间。每一块要指定块的头，对于任意点 $x$，若 $x$ 的头为 $y$，那么需要满足 $x\rightarrow y$ 的简单路径上面所有的点都要和 $x$ 在同一个块。输出方案。 --- 不会做，文件都没有创建，$0$ 分。 ## 排列 有长度为 $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$。 --- 使用暴力。修改 $\mathcal O(n)$，判断是否有三元上升子序列 $\mathcal O(n^3)$，考虑优化后面的算法。设 $m_i=\max_{j=i}^n a_j$，可以预处理出 $m$，然后只枚举 $\mathcal O(n^2)$，$k$ 是否存在可以直接判断。总时间复杂度为 $\mathcal O(n^2q)$，成功获得 $40$ 分。 ## 总结 - **排名**：$2$； - **比赛分数**：$240/400$； - **情况**：相比与 [[2024.9.29 模拟赛]]，一般； - **问题**：不愿意骗分（第三题）。