# Discount 按题意计算每种充值方案的折扣，取最值即可。 # Game 当 p > 1 时，alice 拿到的一定是大的那部分，所以一定不换； 否则，alice 交换以后有一半概率翻倍，一般概率减半，0.5*2+0.5*0.5=1.25，所以一定换。 # Permutation 当 $m \geq \lfloor n / 2 \rfloor$ 时，一定能变成 n...1，这时逆序对数最大。否则我们依次交换 1 和 n，2 和 n-1，.....，一共交换 m 对。 # Intersection 如果不考虑撞车，那么所有车一定是走左右向靠下的车道最优。假设所有车都按这个方案走，现在考虑撞车的情况，撞车只会发生在十字路口的右下角，在这种情况下，靠外的车要走靠上的车道，相应的时间会加一，此题得解。 # Fight 枚举 Left、Mid，Left、Right 之间打了多少轮，那么 Mid、Right 还要打几轮是可以直接算出来的，求最值即可。 # Ant 第一只蚂蚁走的路要不是直接走向石榴，要不最多在一个点有一个分叉，那么我们只要把石榴到根的路径记下来，枚举一下分叉在哪里，然后把概率算出来就可以了。 # Graph 首先我们把题目转换为，给你 $\lfloor\frac{m+1}{2}\rfloor$个$1$ , $\lfloor\frac{m}{2}\rfloor$ 个 $0$ ，把它们填在边上，使得没有一个环的边权 $xor$ 值为 $0$，之后将答案乘上 $\lfloor\frac{m+1}{2}\rfloor!*\lfloor\frac{m}{2}\rfloor!$ 就是本题的答案了。考虑如果存在一条边出现在两个环里，那么不妨设这条边边权为 $x$，第一个环除了这条边以外的边的异或值为 $y$,另一个环除了这条边的异或值为 $z$，那么由题意得，x^y = 1,x^z = 1，同时我们发现，这两个环去除这条边之后也能得到一个新的简单环，通过上面的式子，我们发现 x^y = 0。由此可得，合法的图是一颗仙人掌。对于一颗仙人掌而言，对于树边，我们可以选择填任意的数字，而对于图中的每一个环$S$，我们只能在里面填入奇数个1。这样我们可以设 $f_i(x) = \sum_0^{|S|} a_ix^i$,$a_i$表示环内放入 $i$ 个 $1$ 的方案数，即$\binom{|S|}{i}$$[i%2 == 1]$。将每个环的多项式乘起来就是所求的答案了，std 采用的是启发式合并 NTT。 # Chess 考虑如果棋盘上连续放置了 $11$ 个传送器，那么这个区域就是无法通过骰子跨过的。而对于一个区域而言，只要上面没有连续 $11$ 个传送器，我们就可以通过控制骰子而成功达到每个可达到的点。由此可以得到一个 dp 方程：设 $f[i][j][k]$ 表示当前考虑到第$i$个格子，已经用了 $j$ 个传送器，包括 $i$ 号位置有连续$k$个传送器。那么我们的决策就是第 $i$ 号位置是否放传送器。

# Poker 观察到小沃沃每次只会投入 m 块钱，当他手上的钱大于等于 m 时，他可以继续玩，每次会被拿走 $\lceil m*p\% \rceil$ 这么多钱。那么就很好算了。 #distance 最优情况下，所有人必然在由小沃沃出发的在一条射线上（任意两个人的距离都最小）。我们把 a 排序以后，算距离和就比较简单了。 # Car 二分答案，用 $f[i][j]$ 表示存不存在到了第 i 天，二进制表示为 j 的尾号组（对于某一个尾号，被限制为 1，不被限制为 0）已经被限制过的情况；对于第 i + 1 天，枚举剩下尾号的子集，判断可不可行，即可以进行转移。因为枚举所有集合子集的复杂度为 $3^{10}$，所以总体复杂度为 $log(10000)*10*3^{10}$。 # Covid 用小根堆，按时间从小到大，维护有病毒的 <时间，地点> 二元组。 每次取出堆顶的元素，对于此时在此地的人，都会被沾上荧光粉，把这些人里的每个人，把他在之后<什么时间，到什么地点>的二元组放入小根堆。这里每个人只需要执行一次，因此复杂的是 $\sum len*(log \sum len)$。 # Solo 观察 1：对于一道题， Bob 可以写完后把题屯着，恰好等到 Alice 写完这个题再交，这样可以“耽误” Alice 尽可能多的时间。因此有：Bob 可以让 Alice 把每个题都写完。 观察 2：Bob 如果在 $\sum_{i=1}^{p}a_i$ 的时间内写完第 $p$ 道题，则可以拿到此题一血。 观察 3：设 Bob 最终拿到一血的集合为 S，那么从按编号小到大的顺序做 S 中的题，一定是最优的。 因此可以提出如下 dp 状态：$f[i][j]$ 考虑前 $i$ 道题，Bob 拿到了 $j$ 分，Bob 完成这 j 个题最小耗时。 考虑从 $f[i][j]$(有 $j \leq \sum_{k=1}^{i} a[k]$) 出发的转移，决策第 $i+1$ 道题，写还是不写即可。 # Drink 可以转化成最大费用最大流问题。统计 "012","021","102","120","201","210" 每个字符串出现几次。源点向"012","021","102","120","201","210"连流量为出现次数费用为 0 的边。"012","021","102","120","201","210"的每个字符串，向最喜欢的饮料连流量为正无穷费用为 3 的边，第二喜欢的连流量为正无穷费用为 2的边，向最不喜欢的连流量为正无穷费用为 1 的边。每种饮料向汇点连流量为饮料个数，费用为 0 的边。 # Cloth 可以观察到必存在最优解满足有一个衣服放在 `U`型的最高点上。因为我们可以选任意最优解，把某个高度最高的点移动到 'U' 型最高点。以最高点为圆心 x 为半径画圆，圆内的（不含边界）不能放衣服了。不考虑这些点，我们又可以发现必存在最优解满足有一个衣服放在 `U` 型的最高点上....... 根据上面做出的观察，我们便能构造出一组最优解。在构造的过程中，我们发现，左右两侧的杆子上，隔一个点一定是等距的。`xoxoxoxox`（`x` 和 `o` 都是等距的），放完两侧后考虑底部的杆子，如果还有能放的位置，我们等距的放一定是最优的。 # Hanoi 对任意两个合法的起始状态 $s$ 和终止状态 $t$，如果它们最大的盘子所在的柱子相同，那么不需要移动，可继续考虑第二大的盘子。下面讨论最大的盘子所在柱子不同的情况。不妨设 $s$ 中最大盘子（编号为 $n$）在 $0$ 号柱，$t$ 中最大盘子在 $1$ 号柱。留意到最大的盘子在移动过程中一旦离开一个柱子就不会再回到它，所以最大盘子至多移动两次（要么直接从 $0$ 移到 $1$；要么从 $0$ 移到 $2$ 再移到 $1$）。这样就规约成如下子问题：如何让所有盘子通过一系列步骤聚拢到某一个柱子上。只要求解这个子问题，那么最优方案为下面两种方式中步数最少的方式： a) 编号 $1...(n-1)$ 的盘子从 $s$ 状态聚拢到 $2$ 号柱；最大盘子从 $0$ 号柱移到 $1$ 号柱；编号 $1...(n-1)$ 的盘子从 $t$ 状态聚拢到 $2$ 号柱的逆过程 b) 编号 $1...(n-1)$ 的盘子从 $s$ 状态聚拢到 $1$ 号柱；最大盘子从 $0$ 号柱移到 $2$ 号柱；编号 $1...(n-1)$ 的盘子全部从 $1$ 号柱移到 $0$ 号柱；最大盘子从 $2$ 号柱移到 $1$ 号柱；编号 $1...(n-1)$ 的盘子从 $t$ 状态聚拢到 $0$ 号柱的逆过程 下面求解子问题。不妨设最大盘子（编号为 $n$）所在柱子为 $r_n$ 号柱，需要把所有盘子移动到 $b$ 号柱。注意到最大盘子至多移动一次，它只能从 $r_n$ 号柱直接移到 $b$ 号柱。如果 $r_n=b$，那么它不需要移动，编号 $n-1$ 的盘子目的地 $k_{n-1}$ 也是 $k{n}$；否则编号 $n-1$ 的盘子目的地 $k_{n-1}$ 为 $3-k_n-r_n$（即除 $k_n$ 和 $r_n$ 之外的第三根柱子，否则盘子 $n$ 无法移动）。这样可以计算出每个盘子的预期目的地 $k(·)$。移动方案按盘子大小从小到大进行移动：如果盘子 $i$ 所在位置 $r_i$ 与 $k_i$ 相同，不需要移动；否则将编号为 $i$ 的盘子从 $r_i$ 号柱移到 $k_i$ 号柱，再将编号为 $1...(i-1)$ 的盘子全部从 $k_{i-1}$ 移到 $k_i$ 号柱。所有步数可以通过递归计算。

# Drink 对于每一种饮料，都可以算出最少需要多少瓶，从而知道最少摄入多少卡路里，从中找个最优值。 # GPA 暴力做法：枚举四门课的成绩，按规则算算GPA。 优秀做法：对于每一档绩点，分数取最低一定是最优的，那么我们就可以用枚举分数的档次取代枚举具体的分数。 # Dec 用 $f[i][j]$ 表示第一个数字从 $i$ 开始减，第二个数字从 $j$ 开始减的情况下最多有多少对互质的数字，$f[i][j]$ 从 $f[i-1][j]$ 或 $f[i][j-1]$ 转移过来。 # Civilization 枚举去哪个位置建设城市，人口一定放在食物多的地方，剩下的只要算下人口增长情况就可以了。 # Rotate 考虑 $a_i$ 递减，那么不会出现一个黑块向内连接两个黑块的情况，那么这些联通块构成了一个森林。对于森林而言，联通块的个数 = 点数 - 边数，那么$E($联通块的个数$) = E($点数$) - E($边数$)=\sum a_i-E($边数$)$。那么可以算出来除了最外层，每层贡献是$\frac{a_{i-1}-a_i}{4}$，最外层的贡献是$\frac{a_n}{2}$，所以总贡献是$\frac{a_1+a_n}{4}$。 # Matrix 因为总权值越小越好，我们可以二分最后选的点的最大权值，然后对于每一块区域，分情况讨论、计算。 # Mosquito 二分答案，然后用网络流判断。 用 $f[t][status]$ 表示时刻 $t$ 二进制状态为 $status$（第 $i$ 位为1表示可以在 $t$ 时刻内从 $i$ 号窗户飞过来，0表示不可以）的格点有多少个，这个可以预处理。然后我们把窗户放到左边一列，把二进制状态放到右边一列，$S$ 到左边第 $i$ 个点连流量为 $a[i]$ 的边，右边第 $j$ 个点向 $T$ 连流量为 $f[t][status]$ 的边，如果 $j$ 的第 $i$ 位为1，则连一条左边第 $i$ 个点到右边第 $j$ 个点流量为无穷大的边。如果最大流等于 $a[i]$ 的总和，则当前二分的值 $t$ 是可行的。 # Function 给一个普通积性函数$f$，现在希望求它的前缀和：$F(n)=\sum_{i=1}^n f(i)$。对任一积性函数$g$，都存在一个积性函数$h$满足$f=g \ast h$（方便起见，可以用除号表示$h$，即$h=f/g$）。将式子展开，有$f(p^e)=\sum_{i=0}^{e}g(p^i)h(p^{e-i})$（$p$为素数，e为正整数）。特别的，有$f(p)=g(1)h(p)+g(p)h(1)=g(p)+h(p)$。 记$g$的前缀和为$G(n)=\sum_{i=1}^{n}g(i)$，那么有$F(n)=\sum_{i=1}^n f(i)=\sum_{i=1}^n\sum_{j|i}h(j)g(\frac{i}{j})=\sum_{j=1}^{n}\sum_{k=1}^{\lfloor \frac{n}{j} \rfloor}h(j)g(k)=\sum_{j=1}^{n}h(j)G(\lfloor \frac{n}{j} \rfloor)$。如果我们能构造一个$g$，使得相对应的$h$在素数处的取值都为$0$（即对任意素数$p$，$f(p)=g(p)$），那么我们只需要求$1$到$n$中所有[幂数](https://zh.wikipedia.org/wiki/%E5%86%AA%E6%95%B8)（[powerful number](https://en.wikipedia.org/wiki/Powerful_number)）处的$h$和$G$的值即可。（一个数$n$是幂数，当且仅当对$n$的所有素因子$p$，$p^2$都能整除$n$）（$h$在素数幂处的值可由上面$f=g \ast h$表达式展开求出） 对于此题，取$g(x)=\sigma_1(x)$可满足要求。更进一步，可发现$h(p^e)$仅在$e=2$时取值为$-p$，当$e>2$时皆为0。联想到莫比乌斯函数性质，即得$F(n)=\sum_{i=1}^{\sqrt{n}}\mu(i)\cdot i \cdot G(\frac{n}{i^2})$。复杂度为$O(\sqrt{n}\log(n))$。

## 1001 度度熊与数字 **难度 0/5** 定位为签到题。令 $V$ 的所有位数的数字和为 $d$，且 $V$ 和 $d$ 的最大公因数为 $g$，则把 $g$ 的所有因数由小到大输出就是答案。 顺带一提，若 $V$ 的限制改为位数可高达 $10^6$ 也是能做，不过由于是签到题，就不这样搞了。 ## 1002 度度熊与排列 **难度 1/5** 若 $p[i] = j$，那么把丢进去的 $N$ 个字符串的第 $i$ 个字符按照顺序衔接起来的字符串，会和输出的 $N$ 个字符串的第 $j$ 个字符按照顺序接起来的字符串一模一样。 所以对于 $i$ 从 $1$ 至 $M$，只要依序找出最小的还没配对过且满足上述条件的 $j$ 即可，若某个时刻找不到可配对的 $j$ 就是无解。 ## 1003 度度熊与运算式 1 **难度 3/5** 观察 $1$：运算结果的奇偶性和 $n+1$ 的奇偶性一样 观察 $2$：若把最终的运算式用 $\oplus$ 符号切成很多段，定义一段的长度为该段中 $1$ 的个数。若某一段长度 (假设是 $k$) 不是 $2$ 的幂次方，那么我们可以把该段的一些 $+$ 号改成 $\oplus$ ，也就是切成更多段，使得每一段长度都是 $2$ 的幂次方且运算结果不变，例如说：$1+1+1+1+1+1+1 = 1+1+1+1\oplus1+1\oplus1$。(简单来说就是把 $k$ 用二进制的每个 bit 所代表的数拆开。) 观察 $3$：假设最终的运算式有多个长度为 $2^i$ 的段落 ($i\ge 1$)，那么我们可以只保留当中 $1$ 个段落，剩下的段落都切成长度为 $1$ 的小段落，如此变更后，最终的运算结果只会增加不会减少。所以运算结果最大的可能列式中，存在有一种列式方法是：对于所有非零的 $i$，至多存在一个长度为 $2^i$ 的段落，且不存在任何长度为非 $2$ 的幂次方的段落。 有了这些观察后，一个贪心的做法已经呼之欲出了：枚举 $i$ 从大到小，尝试能不能切出某个段落长度为 $2^i$。 把原始的输入一样用 $\oplus$ 来分段。假设我们正在枚举 $i$，若存在两个以上段落长度 $\ge 2^i$，这代表对于每个 $\le i$ 的正整数 $j$，我们一定能切出一段长度为 $2^j$ 的段落，若只有恰一段长度为 $x$ 满足 $x \ge 2^i$ 那我们可以先把该段切两段长度分别为 $2^i$ 和 $x-2^i$，其中 $2^i$ 那段之后已经不需要再考虑，接着我们就继续枚举 $i-1$，重复同样的步骤。 ## 1004 度度熊与组题 **难度 3/5** **引理： 在满足沃老师对两套题的要求下，对于任意整数 $v$，在第一套题中难度 $\le v$ 的题数与在第二套题中难度 $\le v$ 的题数差的绝对值不超过 $1$ ** 证明：若题数差的绝对值超过 $1$，那么只要把难度 $\le v$ 的题目比较多的那套题中，任选一个最高难度且难度值 $\le v$ 的题，和题目比较少的那套题中， 任选一个最低难度且难度值 $> v$ 的题交换，即可找到更优的组题方式，故产生矛盾。 有了这个引理后，我们只要采用动态规划，状态 dp[v] 代表已经决定好所有难度 $\le v$ 的题要放在哪一套的方法数。转移可分为四种情形：难度 $\le v-1$ 的题数的奇偶性搭配难度 $\le v$ 的题数的奇偶性。 举例来说：若难度 $\le v-1$ 的题数和难度 $\le v$ 的题数都是偶数，且前者比后者少 $2k$ 题，那么转移就是 $dp[v] = dp[v-1]\ \times$ $2k\choose k$。 若难度 $\le v-1$ 的题数是偶数，但难度 $\le v$ 的题数都是奇数，且前者比后者少 $2k+1$ 题，那么转移就是 $dp[v] = dp[v-1]\ \times 2\ \times$ $2k+1\choose k$。 剩下两种情况请大家自己尝试看看 :p ## 1005 度度熊与整数集合 **难度 3/5** 首先，我们能发现游戏过程可以对应到一个 $n$ 个叶子的二元树，且每个非叶子节点都恰有两个子节点，由左至右数来第 $i$ 个叶子的深度就是 $a[i]$，游戏的每个步骤，恰好对应到某个节点，把子树的所有叶子分到左子树和右子树。实际上，每个合法的 Input 可以对应到唯一的二元树，若我们能得到对应的二元树，就可以用 dfs，先往左子树走来得出字典序最小的游戏步骤。 思考过程略过，就结论而言，我们可以借助 stack 用 $O(n)$ 的时间复杂度来找到 Input 对应到的二元树。 依序把叶子由编号小至大加入 stack，stack 里保持点的深度为非递减数列。若要加进的叶子深度比 stack 顶端的深度还要小，就代表 stack 当前顶部的两个点是同一个节点的子节点，且深度必须一样，若不一样就代表无解，否则我们就把该两点移除 stack，并把他们的父节点试图加入 stack (使用试图两个字，是因为要把他们的父节点加入 stack 时，可能引起其他点也再度合并的连锁反应) ，直到最后 stack 里还会剩一些点，再持续把顶部的两个点合并最后会只剩下一个点，也就是树根，如此一来我们就还原出二元树了。 此方法时间复杂度为 $O(n)$。 ## 1006 度度熊与运算式 2 **难度 4/5** 这题是出题者自认为能排进至今生涯出过的题中前十名的好题之一。标程的做法是常数极小的 $O(n \log n)$。 首先，算式的最大值一定是 $n+1$，只要把所有问号取代为加号即可，并且由于按为异或其实就是不进位的加法，所以含有 $\oplus$ 的算式得到的结果一定不会高于全部都是加号。 接着不难观察出，所有使得算式达到最大值的问号取代方式一定满足以下条件： 令由左边数来第 $i$ 个 $\oplus$ 符号左边的 $1$ 的个数有 $a_i$ 个，其中共有 $m$ 个 $\oplus$ 符号，并且令 $a_{m+1} = n+1$，那么对于任意 $\le m$ 的正整数 $i$ 都必须满足 $a_i\ \&\ a_{i+1} = a_i$ (这里的 $\&$ 是按位与符号)，换句话说，序列 $a$ 中相邻的两个数都必须满足：前一个数的二进制表示法中，是 $1$ 的位元必须是后一个数的子集。 于是至此我们可以把问题转化为：给你一个所有元素范围在 $1$ 至 $n$ 的正整数集合 $A$，请问他有多少个子集满足：把子集元素再加上 $n+1$ 由小到大排序后，相邻两个数中，前一个数的二进制表示法中的 $1$ 的位置是后一个数的子集。 令 $dp[x]$ 代表有多少满足上述条件的子集，其中最大的数字是 $x$，那么此问题列出的动态规划关系式为：$dp[0] = 1$，对于 $x > 0$ 且 $x \le n+1$，若 $x$ 不在集合中且 $x \ne n+1$，$dp[x] = 0$，否则 $dp[x] = \sum_{j \ge 0 \ \land\ (j\&x)=j}dp[j]$。 于是我们得到了一个直接计算上述式子 + 枚举位元子集时间复杂度为 $O(3^k)$ 的方法( $k$ 为 $n+1$ 的 最高非 $0$ 的 bit 位置)。 接着我们来优化这个 dp 式。 优化方式其实和高维前缀和的概念是几乎一模一样的，差别只在于，流传于大众的高维前缀和可以只使用 $O(n)$ 的空间，但这题估计是一定得用 $O(n \log n)$ 的空间才能完成。 我们设计新的动态规划状态如下： 首先定义集合 $S(x,k)$。 假定 $x = 2^{b1} + 2^ {b2} + 2^{b3} + \ldots + 2^{bm}$ ($0 \le b1 < b2 < b3 < \ldots < bm$，也就是说 $x$ 的二进制表示法有 $k$ 个 bit 是 $1$)。 若 $y \in S(x,k)$ 当且仅当 $y$ 能表示为 $\sum_{i=1}^{m} t_i \times 2^{bi}$ ，若 $i > k$ 则 $t_i = 1$，否则 $t_i$ 可以是 $0$ 或 $1$。 举例来说，若 $x = 21 = (10101)_2$ ，那么 $S(x,0) = \{21=(10101)_2\}$ $S(x, 1) = \{20 = (10100)_2, 21 = (10101)_2\}$ $S(x, 2) = \{16 = (10000)_2, 17 = (10001)_2, 20 = (10100)_2, 21 = (10101)_2\}$ 接着我们基于前面所定义的动态规划状态，在新定义 $dp2[x][k] = \sum_{y \in S(x, k)}dp[y]$ 那么我们可以得到以下关系式： 1. 当 $k=0$ 时，若 $x \in A$ 或 $x=n+1$ ，有 $dp2[x][k] = \sum_{i=1}^m dp2[x-2^{bi}][i]$ ($bk$ 就是 $x$ 由最低位数来第 $k$ 个是 $1$ 的 bit 的位置，$m$ 是是 $1$ 的 bit 数 )，否则 $dp2[x][k] = 0$。 2. 当 $k > 0$，$dp2[x][k] = dp2[x][k-1] + dp2[x - 2^{bk}][k-1]$ 最终答案就会是 $dp2[n+1][0]$。 参考代码如下： [Gist](https://gist.github.com/Herobs/5562c2ebf8d4ed757f4eb5354d51d928) [Ubuntu Paste](https://paste.ubuntu.com/p/hWJt7WrsFy/)

# 2018 Astar复赛 题目分析 本套题目略微有点卡常，非常抱歉！ ## A 没有兄弟的舞会 定位为签到题，难度1.5分。 不妨用贪心解决，对于每个点$i$，找出他所有儿子中，权值最小和最大的是多少；先判断这些点是否选择。 因为点集中至多只有一对兄弟，所以再对每个点$i$，找出他所有儿子中，权值次小和次大的是多少。挑一个最优秀的选上。 时间复杂度$O(n)$。 也可以用树形Dp解决，复杂度不变。 ## B 序列期望 比较简单的数学期望题，难度2.5分。 总的情况数有$\prod_{i=1}^{n} (r_i - l_i + 1)$种，这个数目太大了；不妨利用期望的线性性质，对于$h=1,2,....,10000$，分别计算出它对答案的贡献，全部相加即可。 假设已确定好$h$，对于每个变量$x_i$，如果$l_i \le h \le r_i$，则$x_i$的取值可以是$l_i,l_i+1,...,h$，如果大于$h$，则最大值就不是我们枚举好的$h$了！同理，如果$r_i < h$，则$x_i$取值为$l_i,l_i+1,...,r_i$；如果$l_i > h$，则显然枚举的$h$是不可能的。 对于枚举好的$h$，如果$h$可能出现，则最大值小于等于$h$的贡献为： $$(\prod_{l_i \le h \le r_i} \sum_{x_i = l_i}^{h} h - x_i) (\prod_{r_i < h} \sum_{x_i = l_i}^{r_i} h - x_i)$$ 容易发现这就是$n$个等差数列的乘积，可以在$O(n)$时间内计算得到。 然而此时只计算出了最大值小于等于$h$的，而我们需要的是最大值恰好为$h$的贡献，这该如何是好呢？哈哈，只需要再算出最大值小于等于$h-1$的，两者相减就是啦！！ 时间复杂度为枚举$h$的复杂度乘上$n$，为$O(10000 \times n)$。 ## C 带劲的and和 比较简单的数据结构题，需要掌握位运算每一位是独立的性质，难度3分。 因为是无向图，所以有$f(i,j) = f(j,i)$，不妨用**并查集**得到图上各个连通块，连通块中每对点的$f$均为1，而不同连通块的点对互不影响。 求和的式子中有$\max$一项，不妨对于每个联通块中的点，将它们的权值$v$从小到大排序，这样枚举到一个点，计算它和前面点之间的贡献时，$\max$就是当前点的权值。 还需要处理$\&$运算符，这是一个经典的套路，只需要对于二进制的每一位统计出有多少个点在这一位上是1，对于每一位分开计算贡献即可。举个例子，如果要计算权值11和权值7的贡献，则有 $$max(7,11) \times (7 \& 11) = 11 \times ((1 + 2 + 4) \& (1 + 2 + 8)) = 11 \times 1 + 11 \times 2$$ 复杂度为$O(n \log n + n \times 30)$，因为二进制位有30个。 ## D 公共子序列 这本是一道看起来很假的题，但是在数据随机的情况下，一切都变得明朗起来。难度3.5分。 假设$k=5$,则有一个非常朴素的$O(n^{2k})$的方法。动态规划，记$F[a][b][c][d][e]$表示目前找到的公共子序列在五个序列中的最后一个位置分别在$a,b,c,d,e$。枚举$a',b',c',d',e'$，如果满足$(a',b',c',d',e')$的每个数都分别小于$(a,b,c,d,e)$，则令$F[a][b][c][d][e]$加上$F[a'][b'][c'][d'][e']$。这个方法复杂度太爆炸了。 容易发现，$F[a][b][c][d][e]$不为0的前提，是$A[a]=B[b]=C[c]=D[d]=E[e]$，此处$A,B,C,D,E$分别表示读入的五个序列。最差情况下，这5个序列的每一个字符都相同，此时状态数为$n^5$。然而在数据随机的情况下，每个序列都近似于是一个排列，而状态数的**期望**也是$O(n)$级别的（可以用严格的数学式子推导）。 设$S$为状态数，则时间复杂度为$O(S^2)$。 ## E 棋盘游走 前两天为了缩短时限，改小了标程的随机次数，结果就出锅了，非常抱歉！ 难度4.5分。 考虑本题的一个简化版本，如果棋盘上恰好只有$k$种颜色，则有一个$O(2^k nm)$的动态规划。定义$F[s][x][y]$，其中$s$是一个$0$到$2^k - 1$之间的数，状压表示每种颜色是否已经走过；而$x,y$表示当前在$(x,y)$点。用一个BFS就可以得到$F$。 当颜色数大于$k$怎么办呢？有一个显然的性质：答案的行走路径**带劲值**肯定恰好为$k$，不可能大于$k$；否则不优嘛。于是有一个乱搞的方法，我们给初始的每种颜色赋值为$1$到$k$之间的**随机数**，再用上述简化版本的方法求解。假设答案的行走路径$k$种颜色为$p_1,...,p_k$，当$p_1....,p_k$随机到$1$至$k$的某个排列的时候，BFS求出的就是最后的答案！ 通过计算，单次正确率为$\frac{k!}{k^k}$，当$k=7$时约为$0.006$；若进行1000次随机，正确率为$99.8 \%$。 ## F 带劲的多项式 题意笼统地说，就是要对给定的多项式，求出其所有根以及根的重数。这是个经典问题，但是不太可做；然而本题有一个条件，即保证所有根的重数互不相同；于是一切都明朗起来了！难度5分。 假设$f(x) = \prod_{i=1}^{m} (x - \lambda_i)^{l_i}$，则$f(x)$的导函数有$f'(x) = \sum_{i=1}^{m} l _i (x - \lambda_i)^{l_i - 1} \prod_{j \neq i} (x - \lambda_j)^{l_j}$。 则$\gcd(f(x), f'(x)) = \prod_{i=1}^{m} (x - \lambda_i)^{l_i - 1}$。 我们发现，每次拿当前的多项式和它的导函数求个$\gcd$，就可以把重数全部减1！因为$l_i$互不相同，首先会把$l_i$最小的根重数变成0，以此类推，最后所有根及其重数都能求出来！ 复杂度计算需要考虑辗转相除求$\gcd$的均摊复杂度，为$O(n^2)$。