真实排名

假如现在在算第 $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

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


版权属于:小宇宙

转载时须注明出处及本声明

最后修改:2019 年 12 月 16 日 11 : 20 AM