抱歉,您的浏览器无法访问本站

本页面需要浏览器支持(启用)JavaScript


了解详情 >

比赛地址

A - Kenken Race

题意

\(N\) 个方格从左到右排列,编号 \(1\)\(N\)。有些位置上有障碍。

有两个不同的棋子,分别在格子 \(A,B\)。你可以执行以下操作若干次:

  • 选择其中一个棋子,向右跳一格或两格,要求目标位置不是障碍且没有其他棋子。

判断是否可以使得最后两个棋子分别在 \(C,D\)

\(N\le 2\times 10^5,A<B\)

题解

\(C<D\),那么我们显然可以先跳第二个棋子使得两个棋子互不影响。

此时显然只需要 \(A\)\(B\)\(C\)\(D\) 之间都没有连续两个障碍即可。

\(C>D\),此时我们需要让第二个棋子在某个位置停留,将第一个棋子跳到终点,再将第二个棋子跳到终点。

为了使第一个棋子顺利跳到终点,我们需要让第二个棋子停留的位置满足把该位置当做障碍后 \(A\)\(C\) 之间仍然不存在连续两个障碍。

那么只需要满足 \(B\)\(D\) 之间(包含 \(B\)\(D\))存在左右两边都是非障碍格子即可。

时间复杂度 \(O(N)\)

代码

B - ABC

题意

给定一个字符串 \(S\),只包含 ABC

你可以执行若干次以下操作:

  • 选择一个 \(s\) 的一个等于 ABC 的子串,替换为 BCA

求最多执行的操作次数。

\(|S|\le 2\times 10^5\)

题解

考虑对于一段 AA..AABC,假设 A\(c\) 个,那么可以操作 \(c\) 次使得这一部分变为 BCAA..AA

于是我们从前往后,有这样一段就操作。这样做一定是最优的,因为 A 仍然连续并且到了后面,可能会与后面的 AA..AABC 组成一个更长的段。

时间复杂度 \(O(N)\)

代码

C - Tests

题意

A 和 B 参加 \(N\) 场考试。对于第 \(i\) 场考试,A 可以规定一个 \(l_i\)\(u_i\) 之间的整数 \(c_i\) 作为该考试的价值。

已知 B 第 \(i\) 场考试的分数为 \(b_i\)。假设 A 第 \(i\) 场考试的分数为 \(a_i\),A 的目标是使得 \(\sum_{i=1}^{N}a_ic_i\ge \sum_{i=1}^{N}b_ic_i\)

A 可以花费一单位的时间来使得自己某场考试的分数加 \(1\)。已知考试的满分为 \(X\),A 不能将已经满分的考试分数加 \(1\)

求 A 达到目标最少花费的时间。

\(N\le 10^5\)

题解

假设 \(c_i\) 已经确定,那么 A 一定是按 \(c_i\) 从大到小依次加,直到比 B 的总分高。那么显然按 \(c_i\) 从大到小排序后一定是一个前缀满分,一个后缀没分,只有中间一个有部分分。

注意到对于 \(a_i > b_i\) 的考试,我们可以把 \(c_i\) 调整成 \(u_i\) 使得自己比 B 的优势更大;对于 \(a_i < b_i\) 的考试,我们可以把 \(c_i\) 调整成 \(l_i\) 使得自己与 B 的差距更小。

于是我们可以强制对于第 \(i\) 场考试,分数小于等于 \(b_i\) 的部分按价值 \(l_i\) 计算,大于 \(b_i\) 的部分按价值 \(u_i\) 计算,那么 B 的分数即为 \(S=\sum_{i=1}^{N}b_il_i\)

考虑二分答案 \(M\),枚举不是满分也不是零分的考试,该考试的分数是已知的;而满分的考试数量也唯一确定,所以只需要把剩余的考试按满分得到的价值 \(b_il_i+(X-b_i)u_i\) 从大到小排序后选取即可。

时间复杂度 \(O(N\log NX)\)

代码

D - Manhattan Max Matching

题意

在平面上有若干个红球和蓝球。有 \(N\) 个位置有红球,第 \(i\) 个位置为 \((RX_i,RY_i)\),有 \(RC_i\) 个红球;有 \(N\) 个位置有蓝球,第 \(i\) 个位置为 \((BX_i,BY_i)\),有 \(BC_i\) 个蓝球。保证 \(\sum RC_i=\sum BC_i\),令该值为 \(S\)

你需要将这 \(S\) 个红球和 \(S\) 个蓝球匹配,每个球最多被匹配一次。一对匹配的权值为这两个球的曼哈顿距离。

求每对匹配的权值之和的最大值。

\(N\le 1000,RC_i,BC_i\le 10\)

题解

考虑曼哈顿距离的式子,把两个绝对值分别拆开,共有 \(4\) 种状态,然后两个球的贡献独立。

因为最后求的是最大值,所以最终一定会取到两个都为正的情况。

对于一个匹配,若我们确定了红球的两个坐标的正负性,我们就可以唯一确定蓝球坐标的正负性。

于是可以建立费用流模型,源点向红球连流量为 \(RC_i\),费用为 \(0\) 的边,限制数量;在红球与蓝球中间建立四个点表示四种状态,每个红球向四种状态连对应流量为无穷大,费用为对应贡献的边。蓝球同理。

直接跑费用流即可。貌似可以用模拟费用流做到更优的复杂度。

代码

E - Complete Compress

题意

给定一个 \(N\) 个点的树,有些节点上有一个棋子。每次可以执行以下操作:

  • 选择两个有棋子且距离不小于 \(2\) 的点 \(u,v\),在这两个点上各取一个棋子向靠近另一个点的方向移动一条边。

求使得所有棋子到同一个点的最少操作次数。

\(N\le 2000\)

题解

枚举最后棋子到达的点 \(t\),将 \(t\) 作为该树的根。

显然对于两个棋子,如果操作这两个棋子后其中一个深度变大了,那么一定不优。所以若合法,操作次数一定是所有棋子深度之和除以 \(2\)。接下来考虑如何判断合法。

对于 \(i\) 的子树,我们分别维护 \(L_i\)\(R_i\) 表示对 \(i\) 的子树内的棋子执行若干次操作后,这些棋子到 \(i\) 的距离之和的最小值和最大值。那么可以取到的距离之和一定是在 \([L_i,R_i]\) 之间与 \(L_i,R_i\) 奇偶性相同的数。为方便描述,我们令 \(C_i\)\(i\) 子树内棋子数量。

显然最大值为子树内的棋子到 \(i\) 的距离之和。考虑如何求出最小值。

我们先把每个子树内部的操作处理完,然后考虑子树之间的操作。假设每个儿子子树内的棋子到 \(i\) 的距离之和分别为 \(d_1,d_2,\ldots,d_k\)。现在的操作相当于每次选两个 \(d_j\)\(1\)。我们要使得最终的 \(\sum d_j\) 最小。

令最大的 \(d_j\)\(d_{\max}\)\(S\) 为所有 \(d_j\) 之和减去 \(d_{\max}\) 的值。那么可以证明最终 \(\sum d_i\) 的最小值为 \(\max(d_{\max}-S,0)\)

\(i\) 的儿子 \(v\)\(R_v+C_v\) 最大的为 \(x\)。若 \(L_x+C_x\) 小于等于除 \(x\) 以外儿子的 \(R_v+C_v\) 最大值,那么我们可以将除 \(x\) 以外的 \(d_j\) 置为 \(R_v+C_v\),将 \(x\) 对应的 \(d_j\) 置为除 \(x\) 以外的 \(R_v+C_v\) 最大值,此时显然有 \(d_{\max}-S\le 0\),所以最小值就是 \(0\)

否则,无论 \(d\) 取何值,\(x\) 对应的 \(d_j\) 一定是 \(d_{\max}\),那么我们一定会将 \(x\)\(L_x+C_x\),其他儿子 \(v\)\(R_v+C_v\),这样才能使 \(d_{\max}-S\) 最小。

综上,最小值即为 \(\max(L_x+C_x-((\sum (R_v+C_v))-(R_x+C_x)),0)\)。注意判断该值与最大值奇偶性不同的情况。

最后只需要判断根节点的最小值是否是 \(0\) 即可。

时间复杂度 \(O(N^2)\)

代码

F - RNG and XOR

题意

有一个随机数生成器,可以生成 \(0\)\(2^N-1\) 之间的整数,其中生成 \(i\) 的概率为 \(\frac{A_i}{S}\),其中 \(S=\sum A_i\)

有一个变量 \(x\),初始为 \(0\),每次会异或一个用上述随机数生成器生成的整数。

对于每个 \(0\le i < 2^N\),求 \(x\) 第一次变成 \(i\) 的期望次数。对 \(998244353\) 取模。

\(N\le 18\)

题解

考虑倒着做,求 \(i\) 第一次得到 \(0\) 的期望次数,显然与原答案相等。那么有 \[ f_i= \begin{cases} 1+\sum\limits_{j=0}^{2^N-1}f_jp_{i\oplus j} & \text{ if }i>0 \\ 0 & \text{ if }i=0 \end{cases} \]

我们可以把上式写成卷积的形式: \[(f_0,f_1,\ldots,f_{2^N-1})\oplus(p_0,p_1,\ldots,p_{2^N-1})=(c,f_1-1,f_2-1,\ldots,f_{2^N-1}-1)\] 其中 \(c\) 是一个未知的常数。

注意到上式要满足条件,必须有 \[\left(\sum_{i=0}^{2^N-1} f_i\right)\left(\sum_{i=0}^{2^N-1} p_i\right)=c+\sum_{i=1}^{2^N-1}(f_i-1)\]

所以有 \(c=f_0+2^N-1\)。那么上面的卷积式子可以写成 \[(f_0,f_1,\ldots,f_{2^N-1})\oplus(p_0,p_1,\ldots,p_{2^N-1})=(f_0+2^N-1,f_1-1,f_2-1,\ldots,f_{2^N-1}-1)\]

可以把 \(p_0\)\(1\) 去掉等式右边的 \(f_i\),即 \[(f_0,f_1,\ldots,f_{2^N-1})\oplus(p_0-1,p_1,\ldots,p_{2^N-1})=(2^N-1,-1,-1,\ldots,-1)\]

那么只要将 \((2^N-1,-1,-1,\ldots,-1)\)\(p\) 做 FWT 后对应位置做除法,再 IFWT 回去即可。

注意 \((2^N-1,-1,-1,\ldots,-1)\)\(p\) 做 FWT 后有且只有 \(0\) 位置的值为 \(0\),不能直接做除法。可以先取任意数,最后根据 \(f_0=0\) 对所有数整体加即可。

时间复杂度 \(O(2^N(N+\log P))\)

代码

评论