真实排名

假如现在在算第 $i$ 个人的答案，分两种情况求方案数：

  1. $a_i$ 没有翻倍。
  2. $a_i$ 翻倍了。

第一种情况比较容易。设 $a_j$ 翻倍后 $i$ 排名不变，则应有 $2a_j<a_i\lor a_j\geq a_i$。假设这样的 $j$ 共有 $m$ 个，则方案数为 $m\choose k$。$m$ 可以通过二分求出。

第二种情况可以如此考虑：先将所有数翻倍，再将某些数除以 $2$。假设 $a_j$ 除以 $2$ 后 $i$ 排名不变，则应有 $a_j<a_i\lor a_j\geq 2a_i$。假设这样的 $j$ 共有 $m$ 个，则方案数为 $m\choose n-k$。$m$ 同样可以通过二分求出。

总方案数即为两部分之和。

一个例外：当 $a_i=0$ 时答案为 ${n\choose k}$。

代码

最大前缀和

考虑一个序列 $a_{1..n}$ 的一段前缀 $a_{1..i}$ 怎样才能是一个极大的最大前缀。要满足两个条件：

  1. 不存在 $j\in [1,i]$，使得 $\sum_{k=j}^i a_k<0$。
  2. 不存在 $j\in[i+1,n]$，使得 $\sum_{k=i+1}^j a_k\geq 0$。

显然两部分是独立的，因此可以分开处理。

并且注意到数据范围相当小，因此容易想到状压 DP。

设 $f_S$ 表示集合 $S$ 中的数组成的满足最大前缀和等于 $\sum_{i\in S}a_i$ 的方案数，$g_S$ 表示集合 $S$ 中的数组成的满足所有最大前缀和都 $<0$ 的方案数。

首先考虑 $g$ 的转移。容易写出
$$
g_{S}=\begin{cases}0,&\sum_{i\in S}a_i\geq 0\\\sum_{i\in S}g_{S-\left\{i\right\}},&\mathrm{otherwise}\end{cases}
$$
接着考虑 $f$ 的转移。考虑在 $S$ 中插入一个数 $i\;(i\notin S)$：若 $\sum_{i\in S}a_i\geq 0$ 则 $f_S$ 可以转移到 $f_{S\cup\left\{i\right\}}$。

答案即为（这里的 $U$ 为全集）
$$
\sum_Sf_Sg_{U-S}\sum_{i\in S}a_i
$$
代码

主斗地

比 「PKUWC2018」斗地主良心的搜索题。

首先可以爆搜出九条可怜的所有可能的牌型，然后爆搜出两人打三带和四带的情况。

假设打了 $x$ 个三带、$y$ 个四带，我们需要判断两人的牌能否打拆成 $x$ 张单牌或对子、$2y$ 张单牌、剩下的单牌，使得这个方案合法。

考虑到九条可怜的牌应该越小越好，所以她打的前面两类牌应该尽量大，同理网友打的前面两类牌应该尽量小。

于是我们只需要枚举打的对子的数量，然后贪心扫一遍就好了。剩下的单牌合法性的判断就很简单了。

可以结合代码理解一下。

代码

星际穿越

考虑差分。我们尝试求出一个 $sum(x,p)$ 表示 $x$ 到 $[p,x)$ 中所有点的最短路之和，这样子答案即为
$$
\frac{sum(x,l)-sum(x,r+1)}{r-l+1}
$$
考虑如何快速求解 $sum(x,p)$。

设 $L(i)=\min_{j=i}^n l_j$。假设当前在点 $x$，那么往左一步可以到达的点为 $[l_x,x)$，往左两步可以到达的点为 $[L(l_x),l_i)$，往左三步可以到达的前为 $[L(L(l_x)),L(l_x))$，以此类推。

这个东西显然可以倍增优化。设 $f_{i,x}$ 表示 $x$ 往左 $2^i$ 步可以到达的点，$g_{i,x}$ 表示 $x$ 走到 $[f_{i,x},x)$ 中所有点的最短路之和，求 $sum(x,p)$ 时直接从 $x$ 开始往左跳并累加贡献即可。

代码

神仙的游戏

考虑一个字符串存在一个长为 $len$ 的 border 的条件：$\forall i\in[1,len]$ 有 $s_i=s_{n-len+i}$。

这个条件等价于：如果 $i\equiv j\pmod{n-len}$，则 $s_i=s_j$。

考虑如何利用这个条件。假设在 $x$ 位置有一个 0，$y$ 位置有一个 1，设 $d$ 为 $|x-y|$ 的约数，则一定不存在长为 $n-d$ 的 border。

一个暴力做法是枚举所有 01 对，这个是 $\mathcal{O}(n^2)$ 的。

考虑如何快速枚举 01 对。我们实际上想要知道的是对于每个 $i$，是否存在一个位置相差 $i$ 的倍数的 01 对。

构造多项式
$$
F_i=[s_i=0],G_i=[s_i=1]
$$
我们希望对于每个 $k$ 求出
$$
\sum_{i-j=k}F_i\times G_j
$$
这长得很像一个卷积的形式。事实上直接将 $G$ 翻转一下就好了。

求出这个东西之后只需要对于每个 $i$ 枚举倍数判断是否合法即可。

代码

PKUSC

非常抱歉，这道题鸽掉了。

最后修改：2021 年 03 月 22 日 09 : 43 PM
© 允许规范转载