WF 2014

Baggage

设 $(BA)$ 表示 $BABA\cdots BA$,$(AB)$ 表示 $AAA\cdots ABBB\cdots B$。

首先爆搜一下 $n=3,4,5,6,7$,可以发现都存在一种从 $\_\_(BA)$ 变成了 $(AB)\_\_$ 的构造。

考虑 $n\geq 8$ 的情况。我们可以做如下操作:

$$ \begin{matrix} \_\_BABA(BA)BABA\\ ABBABA(BA)B\_\_A\\ ABBA\_\_(BA)BBAA \end{matrix} $$

中间那个 $\_\_(BA)$ 可以直接递归处理,处理完后再做如下操作:

$$ \begin{matrix} ABBA(AB)\_\_BBAA\\ A\_\_A(AB)BBBBAA\\ AAAA(AB)BBBB\_\_ \end{matrix} $$

这样子整个序列就变成了 $(AB)$。

Maze Reduction

这种题看着就是要对每个点求一个哈希值,所以关键在于如何设计哈希函数。

设 $h_{i,j,k}$ 表示从 $j$ 的第 $k$ 扇门进去走 $i$ 步的哈希值。假设从 $j$ 的第 $k$ 扇门走进去是 $v$,那么可以从 $j$ 开始绕着 $v$ 走一圈,把所有的 $h_{i-1,v,x}$ 哈希起来表示 $h_{i,j,k}$。特别的,当 $i=0$ 时可以用 $j$ 的度数表示。

然后对每个房间 $i$ 求 $h_{n,i,j}$ 的最小表示,即可当做其哈希值。因为数据范围很小所以可以暴力求,时间复杂度 $\mathcal{O}(n^4)$。

Metal Processing Plant

不妨设 $D(A) \leq D(B)$。

从小到大枚举 $D(A)$,双指针从大到小枚举 $D(B)$,那么只需要考虑如何判断是否合法。

因为每个点要么在 $A$ 中要么 $B$ 中,因此考虑 2-SAT。对于边权在 $(D(A), D(B)]$ 中的边,其两端点需要满足不同时在 $A$ 中;对于边权 $>D(B)$ 的边,其两端点需要满足不同时在一个集合中。

使用压位 Kosaraju 算法找出强连通分量判断即可,时间复杂度 $\mathcal{O}(\frac{n^4}{\omega})$。

Pachinko

设 $f_{i, j}$ 为能够到达 $(i, j)$ 的概率,可以列出一个 $n\times m$ 元方程组。然而直接解时空都无法承受。

不妨把所有格子按照从上到下、从左往右的顺序编号,这样子矩阵是一个长度为 $m$ 的带状矩阵。

因从我们只需要对每行保存 $2m$ 个值,消元时也只需要往下消 $m$ 行再回代就可以了。

Sensor Network

直接随机贪心求最大团是可以过的。具体就是用 bitset 维护已经加入的点,然后随机一个加点排列,能加就加即可。

正解是枚举两个点 $A,B$,则其它点必定在分别以 $A,B$ 为圆心、半径为 $D$ 的两个圆的交内,我们要求最大团。转化成补图的最大独立集,可以发现补图中所有边的端点都在 $AB$ 的两侧,因此补图为二分图,从而很好求最大独立集。

Surveillance

把所有区间按左端点排序,则选了每个区间后下一个必选的区间可以直接双指针预处理出来。

然后预处理倍增数组,枚举起点,然后直接倍增跳一圈即可。

WF 2015

Evolution in Parallel

设 $A\subseteq B$ 表示 $A$ 是 $B$ 的子序列。

首先至少要有 $s_i\subseteq U$,判掉后 $U$ 就没用了。

考虑一条链上的串长度显然是不降的,于是我们把所有串按长度从小到大排序后依次加入,并维护两条链。我们称一个串 $S$ 能接在一条链的末端当且仅当链尾串 $T$ 满足 $T\subseteq S$。

  • 如果当前串不能接在任意一条链的末端,则无解;
  • 如果当前串只能接在一条链的末端,就接上去;
  • 如果当前串可以接在两条链的末端,发现不好处理。我们再维护一条待选链,那么

    • 如果当前串可以接在待选链末端,那么就接上去;
    • 否则一定是这个串和待选链分别接在两条链的末端,随便选择一种接法即可。

这样子总共只需要询问 $\mathcal{O}(n)$ 次 $A\subseteq B$ 是否成立,复杂度 $\mathcal{O}(n^2)$。

Qanat

可以证明,竖井一定会垂直往上运,底部一定会走左右两个竖井中近的那个往上运。

考虑确定最右边的竖井的位置,这样子加上最右边竖井右边部分的代价后即可转化为一个子问题,而这个子问题对应的三角形与原三角形是相似的,所以我们可以只求出原三角形中放 $n-1$ 个竖井的代价,乘上比例系数的平方就可以还原回去。

设最右边竖井到母井的距离为 $L$,我们要计算右边一个 L 状物的代价,即一个 U 状物的代价减去最右边竖井的代价。设 U 状物总长为 $a$,其代价为 $\frac{a^2}{4}$。设原三角形中放 $i$ 个竖井的代价为 $C_i$,于是有

$$ C_n=C_{n-1}\left(1-\frac{L}{w}\right)^2+\frac{\left(h+L+(1-\frac{L}{w})h\right)^2}{4}-\frac{\left[\left(1-\frac{L}{w}\right)h\right]^2}{2} $$

大力化简得到

$$ C_n=\frac{1-\frac{h^2}{w^2}-\frac{2h}{w}+\frac{4C_{n-1}}{w^2}}{4}L^2+\left(h-\frac{2C_{n-1}}{w}\right)L+\left(C_{n-1}+\frac{h^2}{2}\right) $$

是二次函数的形式,令 $L=-\frac{2a}{b}$ 即可求出最值。最后再倒推一遍把每条线段放到相似的三角形里去即可。

Weather Report

显然就是要我们求 $4^n$ 个串的 Huffman 编码,直接求复杂度是 $\mathcal{O}(n4^n)$ 的,无法承受。

但是注意到不同的概率只有 ${n+3\choose 3}$ 种,于是我们可以把概率相同的放在一起,每次批量合并即可。

Tile Cutting

设长、宽分别为 $w,h$,长、宽上切点到一个端点的长度为 $a,b$,则面积为 $wh-a(h-b)-b(w-a)$。

令 $c=w-a,d=h-b$,则面积为 $(a+c)(b+d)-ad-bc=ab+cd$。

设面积为 $x$ 的方案数的 OGF 为 $F$,约数个数的 OGF 为 $G$,那么有 $F=G^2$。

线性筛 $d$,NTT 后预处理 ST 表回答询问即可。

WF 2016

Balanced Diet

设 $s=\sum a_i$。当 $s|n$ 时,只有一种取值,否则有两种取值。

如果一个长度为 $s$ 的前缀合法,那么只需要不断重复它就可以构造出无穷长的合法序列,因此我们只需要判断能否到 $s$ 即可。

先只考虑下界限制,也就是要有 $c_i>nf_i-1$,即 $n<\lceil\frac{c_i+1}{f_i}\rceil$。也就是说,对于每个 $i$,我们都需要把它在这个时间之前加上 $1$。我们把这个时间叫做截止时间。

于是可以贪心,每次找一个截止时间最小的出来加 $1$ 即可。可以证明这样并不会超过上界限制。

Branch Assignment

先跑两遍最短路求出 $dis(i,b+1)$ 和 $dis(b+1,i)$。

设 $w_i=dis(i,b+1)+dis(b+1,i)$,可以求出一个集合的权值为 $W(S)=(|S|-1)\sum_{i\in S} w_i$。为了方便我们将 $|S|-1$ 看成 $|S|$,最后再减去 $\sum w_i$ 即可。

将 $w_{1..b}$ 从小到大排序,那么放在一个集合内的一定是连续的一段,从而可以考虑 DP。

设 $dp_{i,j}$ 表示前 $j$ 个数分成了 $i$ 段的最小权值和,转移为

$$ dp_{i,j}=\min_{0\leq k\leq j}\{dp_{i-1,k}+(j-k)(s_j-s_k)\} $$

这里的 $s$ 是 $w$ 的前缀和。

可以发现这个 DP 对于两维都具有决策单调性。具体的,设 $p_{i,j}$ 表示 $dp_{i,j}$ 是从哪个 $k$ 转移而来的,那么有 $p_{i-1,j}\leq p_{i,j}\leq p_{i,j+1}$。我们从小到大枚举 $i$、从大到小枚举 $j$,在 $[p_{i-1,j},p_{i,j+1}]$ 内枚举转移点,即可做到 $\mathcal{O}(n^2)$。

Clock Breaking

如果一个灯管一直都是 X 或者一直都是 .,那它就有可能恒亮或恒灭。

枚举起始时间,那么如果一个不可能恒亮或恒灭的灯管没有正常发光,那么这个起始时间就不合法。

如果对于某个起始时间,某个灯管都正常发光,那它就有可能是正常工作的。

如果一个灯管的可能性超过 $2$ 种,那么就输出 ?,否则输出对应的东西即可。

Longest Rivers

不妨先考虑只有一个询问 $u$ 时怎么做。显然 $u$ 到根应该都划给 $u$,设这一段长度为 $L$,那么我们希望 $>L$ 的河流数量尽量少。

这个可以直接在树上贪心。如果子树中有一个 $>L$ 的,那么就接它,否则接一个最短的。

后面那一部分和 $L$ 是没有关系的,所以我们考虑让每个节点都接上儿子中最短的,得到一组方案。设 $d_u$ 为这组方案中 $u$ 往下延伸的长度,则有

$$ d_u=\min\left\{d_v\right\}+w_{fa_u,u} $$

如果只统计 $d_u>L$ 的 $u$ 的数量,显然是会算多的。规定一个节点算了后它的祖先就都不能算了,这样子相当于满足了“如果自述中有一个 $>L$ 的就接它”,算出来的就是对的了。

进一步,如果我们把所有 $d_u\leq L$ 的节点删掉,答案就是叶节点个数 $+1$。

现在已经很好扩展到多组询问了。我们把所有叶节点按到根的距离从小到大排序,这样子 $L$ 是不降的,用堆维护所有叶节点即可。

String Theory

首先如果 $\sum a_i$ 是奇数则一定无解。

显然一个 $k$ 阶串左边一定是 $k-1$ 个引号、$k-2$ 个引号、……、$1$ 个引号,右边一定是 $1$ 个引号、$2$ 个引号、……、$k-1$ 个引号。

那么中间还剩下偶数个引号,我们可以直接把它们整成 $1$ 阶串。

于是可以直接枚举答案,然后从左往右、从右往左各扫一遍判断是否满足条件即可。

What Really Happened on Mars?

直接按照题意模拟即可,主要的问题在 Step 2,也就是如何算当前优先级。

这个东西实际上和最长路很类似,可以直接跑一遍 SPFA 求出。

WF 2017

Airport Construction

显然答案所在直线一定经过多边形的两个顶点。于是可以枚举这两个顶点,然后算长度。

算长度的话,先把所有被直线切开的边拿出来按照交点位置排序,然后扫一遍把所有合法段求个 $\max$ 即可。

Get a Clue!

可以直接爆搜,但是有更加高妙的做法。

我们先预处理出每种手牌集合是否可能是每个玩家持有的手牌。这个可以简单地通过输入数据判断。

注意到每种集合对每个人是独立的,因此可以直接做子集卷积,求出每种集合是否有可能是玩家的手牌。注意到后面我们只需要算缺三张牌的集合,只有三个人的集合两两无交时它们的并才可能恰好缺三张牌,因此可以直接做集合并卷积。

然后对所有可能缺三张牌的集合,判断它缺的三张牌是否每种类型都有一张,如果是说明这三张牌有可能是答案。

最后对每种类型扫一遍,如果答案唯一直接输出,否则输出 ?

Money for Nothing

可以发现我们要求的就是

$$ \max_{d_i<e_j}\left\{(e_j-d_i)(q_j-p_i)\right\} $$

可以猜测它有决策单调性,但是我们来尝试证一下。我们把所有东西按时间排好序,设 $i<j\leq k<l$,则应有

$$ (e_k-d_i)(q_k-p_i)+(e_l-d_j)(q_l-p_j)\geq(e_l-d_i)(q_l-p_i)+(e_k-d_j)(q_k-p_j) $$

大力拆开化简得到

$$ d_iq_k+e_kp_i+d_jq_l+e_lp_j\leq d_iq_l+e_lp_i+d_jq_k+e_kp_j $$

然而这个东西并不恒成立……

从头再分析一下。如果 $d_i<d_j,p_i<p_j$,那么我们一定不会买 $j$ 的零件。同理,如果 $e_i<e_j,q_i<q_j$,则我们一定不会卖零件给 $i$。我们可以直接把这些不满足条件的去掉。

那么现在有 $p_i>p_j,q_i>q_j$,根据排序不等式有

$$ \begin{cases} d_iq_k+d_jq_l\leq d_iq_l+d_jq_k\\ e_kp_i+e_lp_j\leq e_lp_i+e_kp_j \end{cases} $$

这样子上面那个东西就成立了,也就是有决策单调性了,直接分治即可。分治时有一些小细节需要注意。

Replicate Replicate Rfplicbte

注意到每次复制一定会向四周扩展一圈,也就是至多扩展了 $\max\left\{\frac{n}{2},\frac{m}{2}\right\}$ 次。

如果没有发生错误,我们可以直接递推出上一次的状态:

$$ b_{i,j}=a_{i-1,j-1}\oplus b_{i,j-1}\oplus b_{i,j-2}\oplus b_{i-1,j}\oplus b_{i-1,j-1}\oplus b_{i-1,j-2}\oplus b_{i-2,j}\oplus b_{i-2,j-1}\oplus b_{i-2,j-2} $$

问题是有错误。注意到一个错误 $(x,y)$ 会对 $(x+1,y+1),(x+1,y+2)$、$(x+1,y+4),(x+1,y+5)$、……造成影响,那么如果 $b_{i+1,m+1}+b_{i+1,m+2}>0$ 说明第 $i$ 行一定有错误,我们再按列推一遍就可以找到错误位置,然后改掉后再递推就好了。

如果错误数 $\geq 1$ 或者 $n=1$ 或者 $m=1$ 就是答案了。

Tarot Sham Boast

结论:把每个串满足 $2l-i\leq n$($l$ 是串长,$i$ 是 border 长度)的 border 求出来从大到小排序,字典序小的出现概率大。

官方证明

简化后的感性理解:

  • 长度为 $l$ 的串 $s$ 出现概率为(假设随机串是 $R$)

$$ \sum_{S\subseteq\{1,2,\cdots,n-l+1\}}(-1)^{|S|+1}\prod_{i\in S}P(R_{i..i+l-1}=s) $$

  • 不妨设

$$ F(x)=\sum_{S\subseteq\{1,2,\cdots,n-l+1\},|S|=x}(-1)^{x+1}\prod_{i\in S}P(R_{i..i+l-1}=s) $$

  • 可以发现 $F(1)$ 恒等于 $3^{-l}$,且 $F(i+1)\ll F(i)$,所以我们可以只比较 $F(2)$ 的值。
  • 假设 $S=\{x,y\}$,那么

$$ F(2)=\begin{cases}-3^{-2l},&i+l-1\leq j\\-3^{-2l+(i+l-j)},&\mathrm{otherwise}\end{cases} $$

  • 后面那种情况会出现当且仅当 $s$ 有一个长度为 $i+l-j$ 的 border,而且 border 越长贡献越大。又因为前面的系数是 $-1$,所以要按字典序从小到大排序。
  • 需要注意的是 $2l-i>n$ 的 border 是没有贡献的,所以并不能把它们算进去。

Visual Python++

假设有解,先考虑如何找到这组解。

从左往右扫描线,并用一个 set 维护纵坐标,那么对于一个右上角,拿 set 中纵坐标最大的左下角和它匹配即可。

问题是可能无解,所以上面求出的解不一定是合法的。我们再从左往右扫描线,那么每次加入或删除一个矩形时上下边中间不能有任何其它边界,同样可以用 set 维护。

因为边界重叠也不合法,所以还有许多细节要考虑。

WF 2018

Conquer the World

考虑反着看整个过程,那么相当于每个点有 $y_i$ 只老鼠和 $x_i$ 个洞,所有老鼠都必须进洞。

$u,v$ 匹配的代价是 $dep_u+dep_v-2dep_{\operatorname{LCA}(u,v)}$。因此我们开两个堆维护子树中老鼠和洞的 $dep$,每次把儿子的堆合并,然后取堆顶匹配,再把反悔操作加入堆中即可。

然而这样并不能保证所有老鼠都进洞,所以我们把老鼠的 $dep$ 减去 $+\infty$,最后再把答案加上 $+\infty\times\sum y_i$ 即可。

这样子当匹配的老鼠和洞来自同一棵子树答案可能会不对,但是这样子一定不会是最优解,所以不会有问题。

因为一对匹配的老鼠和洞不会同时反悔,所以只会操作 $X=\sum x_i$ 次,所以时间复杂度 $\mathcal{O}(X\log X)$。可以记一个 pair 表示代价和出现次数从而做到 $\mathcal{O}(n\log n)$。

Gem Island

可以证明,每种最终局面出现的概率是相等的。

于是可以考虑 DP。设 $f_{i,j}$ 表示 $j$ 枚宝石分给 $i$ 个人的方案数,$g_{i,j}$ 表示 $j$ 枚宝石分给 $i$ 个人的所有方案中前 $r$ 多的和,枚举有宝石的人数可以得到转移

$$ \begin{aligned} f_{i,j}&=\sum_{k=0}^{\min\left\{i,j\right\}}{i\choose k}f_{k,j-k}\\ g_{i,j}&=\sum_{k=0}^{\min\left\{i,j\right\}}{i\choose k}(g_{k,j-k}+\min\left\{k,r\right\}f_{k,j-k}) \end{aligned} $$

答案即为 $\frac{g_{n,d}}{f_{n,d}}+r$。

Getting a Jump on Crime

如果我们能够求出从 $u$ 能否到达 $v$,那么就变成一个简单的最短路了,直接 BFS 即可。

考虑这个东西怎么求。设距离为 $d$,高度差为 $h$,根据物理必修一相关知识,可以列出方程

$$ \begin{cases} v_x\!^2+v_y\!^2=v^2\\ d=v_xt\\ v_yt-\frac{1}{2}gt^2=h \end{cases} $$

化简得到

$$ \frac{1}{4}g^2t^4+(gh-v^2)t^2+h^2+d^2=0 $$

我们肯定想让 $v_y$ 尽量大(这样就更不容易撞到楼上),所以我们只需要求出 $t$ 的最大值,从而求出 $v_x,v_y$。

然后我们枚举每个边界,如果和路线有交的话就算出跳到这个位置时的高度,然后比较一下即可知道是否会撞上。

Single Cut of Failure

切两条对角线一定能够切断所有电线,所以我们只需要判断答案是否为 $1$ 即可。

把所有端点排序,那么需要判断是否有一个连续的长度为 $n$ 的区间包含恰好 $n$ 条电线,直接开个桶扫一下即可。

由于题目要求,需要把坐标微平移一下。

WF 2019

Beautiful Bridges

容易想到一个 DP,即设 $dp_i$ 表示前 $i$ 个点的最小代价,转移枚举从哪个点修过来。

然而判断转移点是否合法是 $\mathcal{O}(n)$ 的,显然会 T。

考虑对于每个转移点 $j$ 计算不撞上 $j$ 时的半径范围。可以列出式子

$$ r^2\geq (x_j-x_i+r)^2+(y_j-h+r)^2 $$

于是可以解出合法的 $r$ 的范围。然而有可能一定撞不上 $j$,即 $x_i-x_j\leq 2(y_j-h)$,此时解出来的 $r$ 的范围要特判一下。

对于每个 $j$,只需要看 $x_j$ 是否同时满足 $[j,i]$ 的半径限制即可判断它是否合法。

Directing Rainfall

从上往下扫描线,并维护每个横坐标要有雨最少需要打多少个孔。

那么对于一个雨棚,如果其斜率为正则相当于做一个后缀 $\min$ 再把非左端点加上 $1$,斜率为负则相当于做一个前缀 $\min$ 再把非右端点加上 $1$。

考虑维护其差分数组,并用两个 set 维护差分值为正、为负的位置。前缀 $\min$ 就相当于把正的位置改成 $0$,后缀 $\min$ 就相当于把负的位置改成 $0$,在 set 中找到对应的位置改掉即可。可以发现每次操作会付出 $\mathcal{O}(c)$ 的代价减少差分数组中的 $c$ 个非 $0$ 值,而非 $0$ 值的增加次数是 $\mathcal{O}(n)$ 的,所以这部分复杂度为 $\mathcal{O}(n \log n)$。

我们还需要确定雨棚的加入顺序。我们需要保证一个雨棚加入前其上方所有雨棚都已加入,所以直接按 $y$ 排序是错误的。可以从左往右扫描线来得出雨棚之间的先后关系,然后拓扑排序即可求出一个合法的顺序。

注意到我们不仅需要维护所有整数坐标的答案,还需要维护 $k+0.5$ 这样的坐标的答案,因为有从中间下去更优的情况。

First of Her Name

为了方便,将所有串都反过来,问题变为询问有多少个串以某个串为后缀。

将询问的所有串建 AC 自动机,把名字拿到自动机上匹配并把最终位置 $+1$,在 fail 树上统计子树和即可。

Miniature Golf

显然一个人的分数关于阈值的函数是一个斜率单减的分段函数。

假设我们在求 $x$ 的最好排名。我们枚举一个其它的人 $y$,然后找到它们的交点,则 $x$ 的排名会在交点处改变($+1$ 或 $-1$)。我们把所有交点拿出来排一遍序,然后扫一遍就可以求出最好排名了。

这个交点比较好求。我们把两个人的所有拐点拿出来归并排序,然后从右往左扫,当 $y$ 的大小关系发生变化时直接算一下即可。

因为题目要求是整数,所以有一些奇奇怪怪的取整的问题。

Traffic Blights

不晓得这东西怎么讲,所以直接蒯 smy 的了

因为 $r_i+g_i\leq 100$,所以经过 $T=\operatorname{lcm}(1,2,\cdots,100)$ 秒红绿灯一定会回到一开始的状态,而 $T|2019!$,所以我们可以看成在 $[0,T)$ 内的随机时刻开始。

考虑求出到达第 $i$ 个红绿灯的概率 $f_i$,这样子差分一下就可以得到答案了。

朴素地想法是列出若干个 $k+x_i\geq r_i\pmod{r_i+g_i}$ 的同余方程,然后求出解集大小,再除掉 $\operatorname{lcm}(r_i+g_i)$。

考虑一些特殊的同余方程组:

  • $\begin{cases}x\in S_1\pmod{p}\\x\in S_2\pmod{q}\end{cases}$,且 $\gcd(p,q)=1$,则解集大小为 $|S_1|\times|S_2|$。
  • $\begin{cases}x\in S_1\pmod{p}\\x\in S_2\pmod{q}\end{cases}$,且 $p|q$,则可以 $\mathcal{O}(q)$ 求出解集。

如果所有 $p_i$ 都只有一个质因数,那么就可以直接对每个质因数维护一个 $\bmod p^{\lfloor\log_p 100\rfloor}$ 的同余方程,最后合并起来。

我们再设一个 $X$,然后枚举 $a\in[0,X)$,并算所有开始时刻是 $kX+a(k\in N)$ 的贡献。可以发现,$X,a$ 已知时 $kX+a+x_i\geq r_i\pmod{r_i+g_i}$ 可以改写为一个形式为 $k\in S\pmod{\frac{r_i+g_i}{\gcd(r_i+g_i,X)}}$ 的同余方程。

取 $X=2520$,则 $\forall i\in[1,100]$,$\frac{i}{\gcd(i,X)}$ 都只有一个质因数,这样子就可以套用上面的做法了。

NEERC 2017

The Great Wall

把 $b_i,c_i$ 都减去 $a_i$,那么只需要考虑被一个区间覆盖或两个区间覆盖的情况,最后加上 $\sum a_i$ 即可。

考虑二分答案,则我们需要计算 $\leq mid$ 的方案数。

先考虑两个区间无交的情况。设 $b_i$ 的前缀和为 $sb_i$,$c_i$ 的前缀和为 $sc_i$,则和为

$$ sb_{i+r}-sb_i+sb_{j+r}-sb_j $$

设 $f_i=sb_{i+r}-sb_i$,相当于 $f_i+f_j\leq mid,i+r\leq j$,是一个二维数点问题。

再考虑两个区间有交的情况,和为

$$ sb_j-sb_i+sc_{i+r}-sc_j+sb_{j+r}-sb_{i+r} $$

设 $g_i=sc_{i+r}-sb_i-sb_{i+r}$,$h_i=sb_i-sc_i+sb_{i+r}$,相当于 $g_i+h_j\leq mid,i+r>j$,同样是一个二维数点问题。

这样子可以直接主席树解决了,但是有常数更加优秀的做法:把所有的 $(f_i,i)$ 二元组排序,然后从大到小枚举 $i$、双指针求出 $f_i+f_j\leq mid$ 的最大的 $j$,并用树状数组中给对应的下标加 $1$,这样子就只需要在树状数组里查一下对应的下标区间的和就好了。后面那种情况同理。

Journey from Petersburg to Moscow

考虑枚举经过第 $k$ 大的边,然后把所有边边权减去这条边的边权后对 $0$ 取 $\max$,那么对应的最短路就是 $dis_n+kw$。

可能没有经过 $k$ 条边,所以还要对原图的最短路取个 $\min$。

通过一些感性理解可以知道这样子包含了所有情况。

Knapsack Cryptosystem

一个做法是直接 meet in the middle,复杂度 $\mathcal{O}(2^{n/2})$,并不能过 $n\leq 64$。

但是题目中还有一个奇妙的性质 $a_i>\sum_{j=1}^{i-1} a_j$,套用得到 $a_1<2^{65-n}$。

发现随着 $n$ 增大 $a_i$ 的取值范围逐渐减小,这启发我们在 $n$ 大时去枚举 $a_1$。

枚举 $a_1$ 后考虑解出 $r^{-1}$,这样子就可以直接求出 $a_{1..n}$,然后倒着贪心一下就可以求出 $s_{1..n}$ 了。

可以列出同余方程

$$ a_1\equiv b_1r^{-1}\pmod{q} $$

设 $z=v_2(b_1)$,$b'=\frac{b_1}{2^z}$,那么

$$ a_1\equiv2^zb'r^{-1}\pmod{q} $$

因为 $r$ 是奇数,所以 $v_2(a_1)=z$,设 $a'=\frac{a_1}{2^z}$,那么

$$ a'\equiv b'r^{-1}\pmod{2^{64-z}} $$

这样子可以解出 $r'=r^{-1}\bmod 2^{64-z}$,$r^{-1}$ 实际取值可能为 $r'+k2^{64-z}(0\leq k<2^z)$。于是我们再枚举 $k$,然后检查得到的 $a_{1..n}$ 是否合法即可。

这样子 $a_1$ 的总枚举量是 $2^{64-n-z}$,$k$ 的总枚举量是 $2^z$,所以总的枚举量是 $2^{64-n}$ 的。

于是我们把两个做法缝合一下,当 $n\leq B$ 时用做法一,否则用做法二,即可做到 $\mathcal{O}(q^{\frac{1}{3}})$。

Laminar Family

考虑把所有路径按照长度从大到小排序,则只有可能是前面的包含后面的。

我们依次加入所有路径,如果当前加入的路径上和两条或者更多条之前的路径有交,那么显然就 GG 了。

我们可以把加入一条路径看成染一种颜色,那么我们只需要支持

  • 链修改颜色;
  • 询问一条链上所有点颜色是否相同。

可以给每种颜色一个编号,然后维护最小值和最大值来解决询问,这样子直接树剖+线段树维护就好了。

NEERC 2016

Binary Code

每个 ? 可以填 $0$ 或 $1$,而且有一些限制,自然想到 2-SAT。然而朴素连边是 $\mathcal{O}(n^2)$ 的,需要优化。

把所有可能的串插入到一棵 Trie 中,那么相当于选出的点互相不能为祖先。

考虑利用 Trie 树优化连边。对于一条 $u\to \neg v$ 的限制,从 $u$ 向对应的节点连边,然后一路往上连到某个节点,再向 $\neg v$ 连边。因为是 2-SAT 所以还有反边,连边方式同理。

但是这并不能处理相同的串。我们想要相同的串只能选一个,朴素连边同样是 $\mathcal{O}(n^2)$ 的,前缀优化连边即可。这样子在 Trie 树上连边时需要拿自己最前面的点去连父节点最后的点。

Cactus Construction

不妨先考虑树的构造。不难得到一种需要 $3$ 种颜色的方案:先把 $u$ 的子树全部建成根是 $1$、其他节点是 $2$,再把 $u$ 改成 $3$,然后把 $u$ 与子节点合并后连 $(1,3)$,再把 $3$ 改成 $1$ 即可。这个构造是递归的。

扩展到仙人掌上时只需要考虑环的处理。我们先把环上的点连出去的子树都接好,然后把环上某个点染成 $4$,然后按照上面的方法连出一条链,最后连 $(1,4)$ 并把 $1$ 改成 $2$、$4$ 改成 $1$ 即可。

操作次数大概是 $4m$,完全能过。

Delight for a Cat

考虑线性规划。设 $x_i$ 为第 $i$ 小时是否吃饭,可以列出线性规划

$$ \begin{matrix} \mathrm{maximize } \sum_{i=1}^n x_i(e_i-s_i)+\sum_{i=1}^n s_i\\ \mathrm{s.t. }\begin{cases}x_1+x_2+\cdots+x_k\geq m_e\\x_1+x_2+\cdots+x_k\leq k-m_s\\\cdots\\x_{n-k+1}+x_{n-k+2}+\cdots+x_n\geq m_e\\x_{n-k+1}+x_{n-k+2}+\cdots+x_n\leq k-m_s\\0\leq x_1,x_2,\cdots,x_n\leq 1\end{cases} \end{matrix} $$

发现是全幺模矩阵,所以一定有整数解,可以考虑费用流。

按照惯例添加辅助变量

$$ \begin{cases}x_1+x_2+\cdots+x_k-y_1=m_e\\x_1+x_2+\cdots+x_k+z_1=k-m_s\\\cdots\\x_{n-k+1}+x_{n-k+2}+\cdots+x_n-y_{n-k+1}=m_e\\x_{n-k+1}+x_{n-k+2}+\cdots+x_n+z_{n-k+1}=k-m_s\end{cases} $$

然后差分一下

$$ \begin{cases}x_1+x_2+\cdots+x_k-y_1=m_e\\z_1+y_1=k-m_s-m_e\\\cdots\\z_{n-k+1}+y_{n-k+1}=k-m_s-m_e\\-x_{n-k+1}-x_{n-k+2}-\cdots-x_n-z_{n-k+1}=m_s-k\end{cases} $$

NOI2008 志愿者招募 一题的方法建图求最大费用最大流即可。

Mole Tunnels

可以想到一个费用流做法:

  • 对于每只鼹鼠,从原点向 $p_i$ 连容量为 $1$、费用为 $0$ 的边;
  • 对于相连的两个点,连容量为 $+\infty$、费用为 $1$ 的边;
  • 对于每个点,向汇点连容量为 $c_i$、费用为 $0$ 的边。

注意到树高是 $\log$ 级别的,所以我们可以暴力枚举当前点与流向的点的 LCA。具体的,我们预处理每个点子树中到它费用最小的点,然后每次暴跳祖先找到流向的点,再连上反边并更新即可。

NEERC 2015

Binary vs Decimal

可以发现如果 $x$ 是合法的,那么 $x$ 的后缀也是合法的。

于是可以从 $0$ 和 $1$ 开始 BFS,每次加上 $10^k$ 判断是否合法即可。

注意到 $10^k$ 在二进制下末尾一定有 $k$ 个 $0$,所以我们只需要判断 $x$ 在十进制下的最高位一直到 $k$ 是否都为 $0$ 即可。

实现时只需要记录二进制和十进制最高位即可。

Cactus Jubilee

移动一条边等价于先删掉一条边再加入一条位置不同的边。不妨去掉位置不同的限制,最后将答案减去边数即可。

那么我们相当于要对每个断掉一条边后求出有多少种加边的方案,满足加边后是仙人掌。

分两种情况讨论:

  • 如果断掉的边是桥,那么剩下的两部分之间任意连都可以,方案数为两部分点数之积。
  • 如果断掉的边不是桥,根据 ZJOI2017 仙人掌 的结论,需要保证连边的两点路径上的边全为桥边。因此可以只保留桥边得到一个图,答案为 $\sum {sz_i-1\choose 2}$。

桥的情况可以一遍 DFS 求出,而非桥的情况似乎不好快速计算。注意到同一个环上的边断掉后保留桥边得到的连通分量相同,因此可以每次对一个环计算。这个环断掉一条边后相当于若干个连通块合并成了一个,只要找到环上的所有点,减去原来的贡献,再加上合并后的贡献即可。

Distance on Triangulation

对于这种图上多次询问最短路的题,显然考虑分治。

我们找到一条边,这样子就可以把图拆分成两部分,按照 ZJOI2016 旅行者 一题的方法更新询问的答案即可。因为边权全为 $1$ 所以只需要 BFS。

考虑复杂度。整个过程相当于在对偶图上做边分治,而三角剖分图的对偶图的最大度数为 $3$,所以每次分治大的一部分至多有 $\frac{2}{3}m$ 条边,因此复杂度是正确的。

Jump

我们只能先想办法问一个 $\frac{n}{2}$ 出来。先假设已经问出来了,稍后再来考虑怎么问。

规定一个串对应的集合就是它所有 $1$ 的下标集合,下面不再区分串和集合。

假设问出来的串是 $I$,考虑求出 $A=S\oplus I$。

考虑 $|A\oplus\{u,v\}|=|A|+|\{u,v\}|-2|A\cap\{u,v\}|$,即 $|A\oplus\{u,v\}|=\frac{n}{2}+2(1-|A\cap\{u,v\}|)$。那么每次可以确定一个二元组与 $A$ 的交是否 $=1$。

不妨令 $u=1$,那么可以得到其它的数是否可以同时和 $1$ 在 $A$ 内,这样子有两种可能的情况,都问一遍即可。

这里最坏会询问 $n+1$ 次,于是我们需要思考如何在 $499$ 次内找到一个 $I$。

考虑随机,那么一次问到一个 $\frac{n}{2}$ 的概率是 $\frac{{n\choose n/2}}{2^n}$,在 $n=1000$ 时约等于 $2.52\%$。于是随机 $499$ 次有很大的概率出解。

King’s Inspection

注意到出度为 $1$ 的点接下来该往哪走是确定的,我们只需要爆搜出度不为 $1$ 的点往哪走即可。

注意不要漏判无解的情况。

Landscape Improved

我们钦定一个横坐标最后是最高的,然后二分它的高度。

check 时只需要找出左右第一个不需要补的位置,然后算出区间内要填的数量,判断它是否 $\leq n$ 就好了。

然而直接暴力找显然不太行。考虑二分,把式子写出来移项后发现要求 $h_i-i$ 和 $h_i+i$ 的 $\max$,ST 表即可。

NEERC 2014

Epic Win!

如果初始状态确定,那么很容易造出一个 $n$ 个点、每个点只有一个转移的自动机来 $100\%$ 打败对手:每个节点的输出正好能战胜对方这个节点的输出,然后根据对方这个节点的输出转移到对应的节点即可。

如果直接拿这个自动机去打,那么可能某时刻没有转移边,这说明我们没有赢。于是我们只要根据对手的输出,转移到对手的节点对应的自己的节点去即可。

这样子会有一些问题,原因在于我们新加的转移边是会成环的,导致会重复到达某个没赢的状态。所以我们每次没赢时新复制一个自动机,然后转移到新自动机去即可。这样子新加的转移是一个外向树的结构,就不会有问题。

根据上面的分析可以知道,这样子至少可以赢 $10^9-n$ 次,可以通过本题。

Gomoku

人类智慧题。

simulator

Improvements

经过一些手玩或者打表可以发现,合法当且仅当 $\forall i\in[1,n]$,$p_i$ 是一个后缀最小值或者后缀最大值。

必要性证明可以考虑找到 $p_i=n$ 的位置,则前面必然是 $p_1=1,p_2=2,\cdots,p_{i-1}=i-1,p_i=n$,后面是一个子问题,可以递归证明;充分性证明略。

这个结论等价于 $p^{-1}$ 是一个单峰的排列,因为 $p_n$ 前面比它小的数单增、比它大的数单减。

修改一个数和直接删掉没有区别。于是只要正反求两遍 LIS,然后枚举最高点即可。

NEERC 2013

Hack Protection

枚举右端点,那么往左的过程中 and 和只会变化 $\log$ 次。

求出前缀异或和,那么我们只需要对 $\log$ 个区间统计其中某个值的出现次数,可持久化 01 Trie 即可(好像可以直接二分)。

这 $\log$ 个区间可以记一下上一个某一位是 $0$ 的数来找出。

Interactive Interception

设速度为 $k$、起始点为 $b$,那么 $t$ 时刻的坐标 $f(t)=kt+b$。

考虑二分,把 $(k,b)$ 看成一组值,每次尽量划分出一半的值出来。

然而 $(k,b)$ 多达 $10^{10}$ 组,直接存下是不可能的。但是注意到任意时刻对于某个 $k$,可能的 $b$ 都是一个区间,因此我们可以对每个 $k$ 记下这个区间。

现在考虑如何划分。我们把所有可能的 $(k,b)$ 都拿出来并计算它们在 $t$ 处的取值,那么我们只需要询问 $[0,M]$($M$ 是这些取值的中位数)就可以尽量划分成一半了。求中位数可以二分实现。

Kabaleo Lite

假设自己已经操作完了,考虑能否必胜。

这样考虑:其他人为了阻止自己胜利,一定会尽量把 $h$ 变成别的,并尽量多地造另一种。于是我们考虑求出最少会剩下多少个 $h$(记做 $A$),以及不是 $h$ 的出现次数最多的数出现多少次(记做 $B$)。 那么如果 $A>B$ 的话,则必胜。

先考虑如何求 $A$。设 $x$ 为 $b_{1..n}$ 中 $h$ 的数量,$y$ 为 $l_{2..p}$ 中不为 $h$ 的数量,那么有 $A=\max\{x-y,[l_p=h]\}$。

再考虑如何求 $B$。设 $x_i$ 为 $i$ 在 $b_{1..n}$ 中的出现次数,$y_i$ 为 $i$ 在 $l_{2..n}$ 中的出现次数,那么有 $B=\max_{i\neq h}\{x_i+y_i\}$。

直接做的话是 $\mathcal{O}(n^2)$ 的,考虑优化修改后算 $A,B$ 的过程。一次修改相当于把 $b_i$ 的出现次数减 $1$、$l_1$ 的出现次数加 $1$。

首先 $A$ 是很好维护的,可以发现只有可能 $x$ 变化,只要维护 $b_{1..n}$ 中 $h$ 的数量即可。

$B$ 就有些复杂。可以发现,修改后的最大值只有可能是原来的最大值、次大值和 $l_1$ 中的一个,三个取个 $\max$ 即可。注意不能和 $=h$ 的取 $\max$。

这样子就做完了。注意要特判 $n=1,l_p=h$ 的情况。

CERC 2017

Buffalo Barricades

我们首先求出每个栅栏实际包含的牛的数量(也就是不算被后面的栅栏包含的)。

从上往下扫描线,并用 set 维护所有往下的栅栏的横坐标。

  • 如果当前点是牛,我们找到一个最小的 $x\geq$ 它的横坐标的栅栏,则最终这个栅栏包含这头牛;
  • 如果当前点是栅栏,我们把它加入 set 中,然后模拟一遍往左延伸的过程,把编号比它大的连续的一段删掉。

接着求出每个栅栏加入时包含的牛的数量。可以发现,如果 A 包含 B,且 A 加入时间比 B 早,那么 B 的答案要加到 A 中去。可以发现这个东西实际构成一个树形关系,我们只需要从前往后扫,然后把父边断掉,这样子扫到每个点时它的 $size$ 就是答案了。可以直接 LCT 维护。

当然也可以不 LCT,直接倒过来变成加边,就很好用并查集维护了。

Cumulative Code

不妨先写出 $k=5$ 时的 Prufer 序列

$$ p^{(5)}=[8,8,4,9,9,4,2,10,10,5,11,11,5,2,1,{\color{red}{3}},12,12,6,13,13,6,3,{\color{red}{7}},14,14,7,{\color{red}{15}},15] $$

红色的数与其它数不同——这些位置删除的节点是根。但是这些数只有 $k-2$ 个,我们可以单独考虑。下面我们只考虑黑色数的连续段中的情况。

可以发现这样的连续段等于左子树的后序遍历中每个数除以 $2$。

不妨把每个数写成关于根的父亲编号的一次函数的形式,如当 $k=4$ 时有

$$ p^{(4)}(x)=[8x,8x,4x,8x+1,8x+1,4x,2x,8x+2,8x+2,4x+1,8x+3,8x+3,4x+1,2x,x] $$

考虑 $p^{(k)}(x)$ 与 $p^{(k-1)}(x)$ 的关系。可以发现,$[x]p^{(k)}(x)$ 等于 $\Big[2[x]p^{(k-1)}(x),2[x]p^{(k-1)}(x),1\Big]$,$[x^0]p^{(k)}(x)$ 等于 $\Big[[x^0]p^{(k)}(x),\frac{1}{2}[x]p^{(k)}(x)+[x^0]p^{(k)}(x),0\Big]$。

这样子我们就可以将求 $p^{(k)}$ 中若干等差数列项的和转为两个求 $p^{(k-1)}$ 中若干等差数列项的和的问题,可以直接递归计算。

然而如果递归到底的话是 $\mathcal{O}(2^k)$ 的。我们只需要在没有元素时及时返回,再加上记忆化即可。为了记忆化我们把询问拆成前缀相减,并记录深度与末项的位置。

这样子时间复杂度变为 $\mathcal{O}(2^{k/2})$。实际上我们只需要对前 $\frac{k}{2}$ 层记忆化即可,不影响复杂度。

Donut Drone

考虑先暴力走到第一列,然后倍增跳 $k/m$ 圈,再暴力走完剩下的。

那么我们要维护 $(i,1)$ 走 $2^km$ 步后会到哪里。考虑用线段树维护,每个区间维护从 $l$ 走到 $r+1$ 的哪一行,这样子根节点就是 $(i,1)$ 走 $2^0m$ 步后到的行,再倍增即可。

修改直接把前一列在线段树上修改一下即可。

复杂度大概是 $\mathcal{O}(Qn\log k)$,似乎挺能过的。

Intrinsic Interval

析合树模板题。

如果两个点在析合树上的 LCA 是析点,那么答案就是这个析点对应的段;否则还要找到两个点所在的两棵子树,LCA 的儿子序列中这两个子树间的子序列才是答案。

Kitchen Knobs

显然每个按钮要么最终位置唯一(因为 $7$ 是奇数),要么最后在哪都可以(这种情况当且仅当 $7$ 个数都相等)。后面那种我们可以直接去掉。

我们把每个按钮需要旋转的次数算出来,然后再差分一下(注意这里是在模 $7$ 意义下),问题变为每次可以给一个数加 $x$ 一个数减 $x$,求把所有数变成 $0$ 的最小次数。

$0$ 我们可以直接不管;对于剩下的数,显然我们会先把 $1,6$、$2,5$、$3,4$ 两两相消,这样子最后会剩下至多 $3$ 种数。

可以发现,如果剩下的 $3$ 种数和为 $7$ 的倍数,那么我们一定可以用数量减 $1$ 次操作把它们都消成 $0$。于是我们预处理所有这 $3$ 种数的和为 $7$ 的倍数的情况,然后直接 DP 即可。

Lunar Landscape

注意到值域很小,又和覆盖有关,所以猜测和差分有关。

A 类正方形很好差分处理;B 类正方形是斜着的,感觉不太好处理。

我们做坐标变换 $\begin{cases}x\leftarrow x+y\\y\leftarrow x-y\end{cases}$,那么 B 类正方形就变成正的了,同样可以差分处理。

算答案时,我们算出每个面积为 $0.25$ 的小三角形是否被覆盖,然后加起来即可。

CERC 2016

Bipartite Blanket

可以发现,左右两边点集的可行性是无关的,于是我们可以先预处理出两边的每个点集是否可能被一组匹配覆盖。

考虑这个东西怎么预处理。设 $f_S$ 表示左边点集 $S$ 能否被一组匹配覆盖。那么根据 Hall 定理,我们需要枚举 $S$ 的每个子集 $T$,然后判断 $|T|\leq |N(T)|$ 是否成立。然而这样显然无法通过。

但是仔细思考一下可以发现,$|T|\leq |S|-1$ 的 $T$ 是否都成立我们已经知道了(根据 $f_{S-\{i\}}$),我们只要判断 $|S|\leq |N(S)|$ 是否成立就好了。这样就可以在 $\mathcal{O}(n2^n)$ 的时间内求出 $f$。同理我们在 $\mathcal{O}(m2^m)$ 的时间内求出 $g$ 表示右边点集 $S$ 能否被一组匹配覆盖。

那么问题变为求有多少个 $(S,T)$ 满足 $f_S=1,g_T=1,s_S+s_T\geq t$,可以用 meet in the middle 的思想,把所有 $g_T=1$ 的 $T$ 按 $s_T$ 排序,然后枚举 $f_S=1$ 二分出满足条件的 $T$ 的个数即可。

Dancing Disks

设 $f_{i,j}$ 表示 $(i,j)$ 最多能让多少个数有序。显然 $(i,j)$ 可以多路归并左上方的所有柱子上的数,那么有

$$ f_{i,j}=\sum_{1\leq x\leq i,1\leq y\leq j,(x,y)\neq (i,j)}f_{x,y} $$

显然 $f_{1,1}=f_{1,2}=f_{2,1}=1$,于是可以推出 $f_{6,6}=26928$,感觉不太行。

冷静分析一下发现,对于 $(1,2)$ 和 $(2,1)$,我们可以看 $(1,1)$ 最上面两个的大小关系,从而实现 $f_{1,2}=f_{2,1}=2$,这样 $f_{6,6}=42960$,非常好。

于是我们递归做这个过程,每次用堆维护多路归并即可。注意每个柱子实际上是一个栈,所以如果当前柱子需要从小到大排,则前面的柱子需要从大到小排,所以我们还要记一下排序方式。

Easy Equation

考虑一组解 $(x_0,y_0,z_0)$,把 $x$ 看成主元,有

$$ x^2-k(y_0+z_0)x+(y_0\!^2+z_0\!^2-ky_0z_0-1)=0 $$

由韦达定理可知,$x$ 的另外一根为 $k(y_0+z_0)-x_0$。

显然原方程有一组解 $(0,0,1)$,我们只要从这个解出发,按照上面的方法扩展出两个更大的解,直到找到 $n$ 个解即可。

Jazz Journey

显然我们可以对所有 $u\to v$ 和 $v\to u$ 的路线单独拿出来算。

首先我们算出 $u\to v$ 的最小花费、$v\to u$ 的最小花费、$u\to v\to u$ 的最小花费、$v\to u\to v$ 的最小花费。需要注意的是前两种可以买双程票,后两种可以买两张单程票。

那么现在一定在不浪费的前提下尽量多买双程票更优,于是我们先做两遍类似括号匹配的过程,先尽量多买更便宜的那种双程票,再尽量多买另一种,剩下的就买单程票即可。

Lost Logic

如果一个变量取值全为 $0$,我们加一个 $x\to \neg x$,限制它只能为 $0$;同理,如果一个变量取值全为 $1$,我们加一个 $\neg x\to x$,限制它只能为 $1$。

然后一个自然的想法是枚举 $i,j$,如果 $i$ 为 $x$ 的时候 $j$ 全为 $y$,就加一个 $ix\to jy$。但是这个约束数是 $\mathcal{O}(n^2)$ 的,并不太行。

那么可以先把那些相同的或者互补的缩起来。具体的,如果 $i,j$ 相同就加 $i\to j$ 和 $\neg i\to \neg j$,如果 $i,j$ 互补就加 $i\to \neg j$ 和 $\neg i\to j$。

这样子只会剩下至多 $3$ 种($0,0,1$、$0,1,0$ 和 $1,0,0$)。冷静分析一下发现:如果 $3$ 种都有,则不能构造出合法方案;如果只有 $1$ 种,则我们不需要再连边;如果只有 $2$ 种,我们直接枚举两种的取值(共 $4$ 种情况),然后判断是否需要连边即可。

CERC 2015

Export Estimate

考虑按边权从大到小加边。

先考虑算点数。观察一下这个过程,似乎所有度数是 $0$ 或 $2$ 的点都会被删掉?其实并不是,因为一个度数全是 $2$ 的点构成的环最后会留下一个点。所以点数实际上是 $n-cnt_0-cnt_2+cnt_{loop}$。

边数同理,所有度数为 $2$ 的点都会删去两条边再加上一条边,但一个度数全是 $2$ 的环最后会留下 $2$ 条边。所以边数是 $e-cnt_2+cnt_{loop}$,这里的 $e$ 是已经加入的边数。

那么唯一的问题就是如何维护 $cnt_{loop}$ 了。因为只有加边,所以可以用并查集很方便的维护(只需要维护每个连通块是否是度数全为 $2$ 的环即可)。

Frightful Formula

先考虑 $c=0$ 的情况。我们计算每个 $l_i$ 和 $t_i$ 对 $(n,n)$ 的贡献。

只考虑 $l_i$,那么相当于从 $(i,1)$ 走到 $(n,n)$,第一步必须往右,往右走一步乘 $a$,往下走一步乘 $b$,求所有路径的权值和。这个东西显然等于

$$ {2n-i-2\choose n-2}a^{n-1}b^{n-i} $$

再考虑 $c$ 的贡献。同理可以知道,$(x,y)$ 对 $(n,n)$ 的贡献是

$$ c{2n-x-y\choose n-x}a^{n-y}b^{n-x} $$

那么总贡献是

$$ \begin{aligned} &c\sum_{i=2}^n\sum_{j=2}^n{2n-i-j\choose n-i}a^{n-j}b^{n-i}\\ =&c\sum_{i=2}^n\sum_{j=2}^n(2n-i-j)!\frac{a^{n-j}}{(n-j)!}\frac{b^{n-i}}{(n-i)!}\\ =&c\sum_{d=4}^{2n}(2n-d)!\sum_{i+j=d}\frac{a^{n-j}}{(n-j)!}\frac{b^{n-i}}{(n-i)!} \end{aligned} $$

后面是卷积的形式,于是直接 MTT 即可。

有的小青年就发问了,我不喜欢卷积,我不喜欢 MTT,我永远只爱组合意义,你这种推式子,我很不满意!

很好!很有精神!那我们就来分析一下。

我们打个表看一下每一项对 $(n,n)$ 的贡献

$$ \begin{matrix} ca^0b^0{0+0\choose 0} & ca^1b^0{1+0\choose 1} & ca^2b^0{2+0\choose 2} & \cdots \\ ca^0b^1{0+1\choose 0} & ca^1b^1{1+1\choose 1} & ca^2b^1{2+1\choose 2} & \cdots \\ ca^0b^2{0+2\choose 0} & ca^1b^2{1+2\choose 1} & ca^2b^2{2+2\choose 2} & \cdots \\ \vdots & \vdots & \vdots & \ddots \end{matrix} $$

可以发现,当 $i+j\leq n-2$ 时,贡献就是 $c(a+b)^{i+j}$;当 $i+j>n-2$ 时,可以把上一 / 的贡献乘上 $a+b$,然后再减去边上两项,就可以得到贡献了。

Greenhouse Growth

如果一段向日葵高度相同,那么它们在之后任意时刻高度都相同,因此可以缩成一段。

用链表维护这些连续段,每段维护如下信息:

  • $l,r$:左右端点;
  • $t,h$:在第 $t$ 天时高度为 $h$;
  • $fl,fr$:光在左边 / 右边时是否会长高。

第 $i$ 天时的高度可以通过前 $i$ 天光在左边和右边的天数来求出。

我们逐天处理,每天把能合并的合并即可。对于两个相邻的连续段,我们可以根据它们的高度差求出它们会在什么时间合并。于是只要当发生改变时重新计算一下合并时间即可。

具体实现细节比较多,要注意各种奇奇怪怪的情况(比如之前要合并的现在不要合并了)。

Ice Igloos

注意到值域和 $r$ 都很小,所以我们可以只枚举那些圆心到直线距离 $<1$ 的圆。

具体地,我们需要找到所有满足

$$ \frac{\lvert Ax+By+C\rvert}{\sqrt{A^2+B^2}}<1 $$

的圆。

因为值域很小,所以可以直接枚举 $x$,然后把 $y$ 的范围算出来就好了。注意端点需要特判。

Juice Junctions

看到这题的第一反应就是最小割树,然而这个 $n\leq 3000$ 的数据范围一看就很不能过。

注意到题目中有一个奇妙的度数 $\leq 3$ 的限制,这说明最大流 $\leq 3$,我们可以讨论一下:

  • 如果两点不连通,最大流为 $0$;
  • 如果两点不在同一个边双中,最大流为 $1$;
  • 如果两点在同一个边三连通分量中,最大流为 $3$;
  • 否则最大流为 $2$。

问题是这个“边三连通分量”怎么求。思考一下发现,如果断掉任意一条边后两点都在一个边双中,则它们在同一个边三中。我们可以枚举断掉的边,然后相当于判断两点所在边双是否一一相等,可以直接哈希判断。

实际上有线性求边三连通分量的算法,但是这题 $\mathcal{O}(m^2)$ 可以过所以就懒得去看了。

CERC 2014

Can't stop playing

可以发现游戏中的序列一定是一个 ^ 的形状。

对于一个单增或单减的只由 $2^k$ 构成的序列,我们只要知道它们的和即可还原出整个序列。

设 $f_{i,j}$ 表示前 $i$ 个数、最高点右边的和为 $j$ 是否可行。因为前 $i$ 个数的和已知所以可以求出左边的和。

转移时只需要看一下当前数是不是小于等于最左边 / 最右边的数即可。注意放在右边时可能会产生新的最大值使得右边的和变成 $0$。

在转移过程中记录一下转移点,倒推即可求出方案。

Pork barrel

把所有边从大到小排序,然后依次加入,并维护 MST。假设询问 $[l,r]$,则加入了所有 $\geq l$ 的边后 MST 上 $\leq r$ 的边权之和即为答案。

LCT 维护生成树、主席树维护每种边权的出现次数即可。

The Imp

实际上双方都知道对方的最优策略。

那么对于我方的某个策略 $(s_1,s_2,\cdots)$,显然有 $v_{s_i}<v_{s_{i+1}}$,否则一定更劣。

于是我们先把所有物品按 $v$ 从大到小排序,然后考虑 DP。设 $dp_{i,j}$ 表示前 $i$ 个物品,对方去掉了 $j$ 个的最大收益,转移为

$$ dp_{i,j}=\max\left\{dp_{i-1,j},\min\left\{w_i-v_i,dp_{i-1,j-1}-v_i\right\}\right\} $$

答案即为 $dp_{n,k}$。

Outer space invaders

考虑 $d$ 最大的那个外星人,我们选一个时刻把它打了,那么剩下左右两端只剩下了被完全包含的外星人。

于是可以区间 DP。设 $dp_{i,j}$ 表示 $[i,j]$ 完全包含的外星人被打掉的最小代价,转移是

$$ dp_{i,j}=\max_{k=i}^j\left\{dp_{i,k-1}+x+dp_{k+1,j}\right\} $$

这里的 $x$ 时被 $[i,j]$ 完全包含的外星人中最大的 $d$。

CERC 2013

Subway

似乎是 JSOI2015 地铁线路 的原题。当然那题把输入改简单了。

第一问考虑最短路。对于每条线路建一个点,线路上的站向线路连边权为 $1$ 的边,线路向线路上的站连边权为 $0$ 的边。因为边权只有 $0$ 和 $1$ 所以可以 BFS。

第二问考虑一个 DP。设 $dp_i$ 表示到达 $i$ 时最多乘坐多少分钟的地铁。

假设一条线路的 $dis$ 为 $d$,则我们可能在 $dis$ 为 $d-1$ 的站上车,在 $dis$ 为 $d$ 的站下车,所以我们要用 $dis$ 为 $d-1$ 的站更新 $dis$ 为 $d$ 的站。

把所有线路按 $dis$ 从小到大排序,然后对于每条线路转移:$dp_j\leftarrow dp_i+dis(i,j)\;(dis_i=d-1,dis_j=d)$。记一下前后缀最大值即可 $\mathcal{O}(L)$ 转移。

Chain & Co.

考虑按照平行的平面分成三类,那么每一类内部肯定只能在一个集合内。

于是我们枚举哪一类是单独的,然后暴力 check 一下就好了。

Captain Obvious and the Rabbit-Man

可以发现 $p_i$ 是 $k$ 阶常系数齐次线性递推数列,其特征多项式为 $p=(X-1)(X-2)\cdots (X-F_k)$。

设 $p=X^k+a_{k-1}X^{k-1}+\cdots+a_0$,则有

$$ p_{k+1}+a_{k-1}p_k+\cdots+a_0p_1=0 $$

只需要 $\mathcal{O}(k^2)$ 求出 $p$ 的系数即可。

NEERC NSub 2017

Consonant Fencity

暴力是枚举每种字符是大写还是小写,然后扫一遍算答案,复杂度 $\mathcal{O}(2^{|\Sigma|}n)$。

实际上我们只需要知道每个字符对的出现次数,预处理后即可做到 $\mathcal{O}(2^{|\Sigma|}|\Sigma|^2)$。

然而 $|\Sigma|=26$。但是实际上元音字母的大小写是无关紧要的,我们只需要知道辅音字母的大小写即可。这样子就有 $|\Sigma|=19$,可以通过此题。

Equal Numbers

显然只有两种情况:要么是一个数全部变成了它的某个倍数,要么是一些数变成了它们的 LCM。

两种情况肯定都是先选个数少的,排序后扫一遍即可。

Fygon 2.0

对于一个 for i in range(a, b):,可以看成 $i$ 在 $[1,n]$ 内循环,但是只有 $a\leq i\leq b$ 时才算贡献。

我们从 $a$ 向 $i$、$i$ 向 $b$ 连边,则一个强连通分量内的变量取值必须相同,即 $k$ 即为强连通分量数。

然后 $C$ 感性理解一下就是缩点后的大小关系数除以点数的阶乘,而前面那个东西就等于 DAG 的拓扑序数,状压 DP 即可。具体证明可以看这里

Grand Test

似乎和 CF521E Cycling City 一模一样。

首先 DFS 一遍求出一棵生成树,那么只会有一些返祖边。答案存在当且仅当有一条树边被至少两条非树边覆盖。

假设这两条非树边是 $(a,b)$ 和 $(c,d)$,$t$ 是 $a,c$ 的 LCA,如下图

例子

那么 $3$ 条路径即为 $t\to b$、$t\to a\to b$、$t\to c\to d\to b$。

实现时可以直接暴力覆盖、暴力求 LCA,时间复杂度 $\mathcal{O}(n)$。

Hidden Supervisors

可以证明,包含根的最大匹配只会比不包含根的最大匹配大 $0$ 或 $1$。

于是我们对每棵树都求一个最大匹配(可以直接 DFS 求出),然后分成两类:根在匹配中的和根不在匹配中的。特别的,$1$ 并不能连父边,所以要强制看成第一类。

那么我们相当于要把第二类的根拿去匹配前面某个未匹配的点。第一类树中的未匹配点是可以匹配的,而第二类按照未匹配点的数量从大到小排序后加入一定是最优的。如果前面没有未匹配的点,那么可以连到 $1$ 上保证形成一棵树。

NEERC NSub 2016

Digital Addition

每一位的状态只有 $200$ 种,可以直接预处理出来。

考虑数位 DP。设 $f_{i,S,0/1}$ 表示 $[i,w]$ 位、第 $i$ 位左边黑色部分为 $S$、是否进位是否可行,转移直接枚举下一位的状态即可。

因为要输出方案,所以要记录一下每个状态是从哪里转移过来的。

Easy Reading

首先不是 u,d,l,r 的字符是没用的,可以直接去掉。

两个图案相同至少要黑格子数量相同,于是可以双指针求出所有黑格子数满足条件的区间。

在双指针的过程中可以维护出黑格子,但是我们并不能 $\mathcal{O}(nm)$ 的判断图案是否相同。

考虑哈希。设 $H_{x,y}=A^xB^y\pmod{p}$,那么我们只需要比较两个图案的哈希值即可。注意图像是可以平移的,所以我们还需要求出当前图案的黑格子中最小的 $x$ 和 $y$,然后乘上 $A^{-x}B^{-y}$ 平移到原点比较。

然而卡自然溢出,所以最好在哈希值相同时暴力比较一遍。

Gangsters in Central City

显然至少要断掉的边数就是 $1$ 的有强盗的子树数量,因为我们可以直接断掉与 $1$ 相连的边。

于是我们可以把 $1$ 的每棵子树分开考虑(下面的强盗只指 $1$ 的某棵子树中的)。为了满足第二个条件,断掉的边一定是最深的强盗全在其中的点的父边。这个点实际上就是强盗的 LCA。

可以考虑一个经典套路:对于每个强盗,把它到根的路径加上 $1$,那么这个点就是所有点权最大的点中最深的那个。

这样子就可以直接树剖+线段树维护了。删点后子树中没有强盗了的情况可能需要注意一下。

Integral Polygons

如果总面积不是整数则答案为 $0$,否则只要一侧面积为整数即满足条件。

那么也就是($\times$ 是叉积)

$$ \vec{p_i}\times\vec{p_{i+1}}+\vec{p_{i+1}}\times\vec{p_{i+2}}+\cdots+\vec{p_{j-1}}\times\vec{p_j}+\vec{p_j}\times\vec{p_i}\equiv 0\pmod{2} $$

$$ s_n=\sum_{i=2}^n\vec{p_{i-1}}\times\vec{p_i} $$

上面的条件即

$$ s_j-s_i+\vec{p_j}\times\vec{p_i}\equiv 0\pmod{2} $$

把叉积也拆开,变成

$$ s_j-s_i+x_jy_i-y_jx_i\equiv 0\pmod{2} $$

枚举 $j$,那么 $s_j,x_j,y_j$ 的奇偶性已知,我们只需要知道 $s_i,x_i,y_i$ 的奇偶性即可判断是否合法。这只有 $8$ 种情况,开一个桶记一下即可。

注意去掉 $i=j+1$ 和 $i=1,j=n$ 的情况,因为这样的情况面积一定是整数,所以只需要最后减 $n$ 即可。

Java2016

我们可以先对很多个 ?max 来得到 $255$,然后把两个 $255$ 相除得到 $1$。因为代码长度限制需要套几层宏定义。

然后可以求出 $2,4,8,16,32,64,128$,直接把 $c$ 拆位即可。

$0$ 需要特判(直接把样例蒯下来即可)。

NEERC NSub 2015

Distribution in Metagonia

不是很晓得怎么想出来的,直接给算法了:

  • 首先找到最大的 $2^x|n$;
  • 然后找到最大的 $2^x3^y\leq n$;
  • 把 $2^x3^y$ 作为一个答案,然后递归分解 $n-2^x3^y$。

可以发现 $n-2^x3^y$ 中 $2$ 的次数一定 $>x$(因为 $n$ 除掉 $2^x$ 后是奇数,再减掉奇数后是偶数,也就是 $(n-2^x3^y)/(2^x)$ 是偶数),而 $3$ 的次数一定 $<y$(因为数变小了 $2^x$ 还变大了),所以满足条件。

Fygon

易知答案是 $\leq 6$ 次的多项式,于是只要暴力模拟出 $n=0,1,\cdots,6$ 时的执行次数,然后拉格朗日插值即可。

Insider’s Information

考虑每次确定两边的一个元素。那么一个三元组 $(a,b,c)$ 相当于要求 $b$ 不是最早被确定的元素。

考虑先求出一个排列 $p$,满足对于每个三元组 $(a,b,c)$,$a,c$ 中都有一个在 $b$ 的前面。这个可以拓扑排序求出。

然后我们按照这个排列的顺序插入。一个三元组在排列中的顺序只有两种情况:$b$ 在第二个或者第三个。

假设第一个在左边。如果 $b$ 在第二个,那它应该插入到左边才能满足;如果 $b$ 在第三个,那它应该插入到右边才能满足。

这样子会有一些三元组要求当前元素插到左边、一些三元组要求当前元素插到右边,哪一种多就插到那边即可,这样子满足的三元组数一定不会少于不满足的。

NEERC NSub 2014

Fragmentation

如果 $i$ 与 $i+1$ 在同一段中,则连边 $(i,i+1)$,则我们相当于要最大化边数。

可以发现,如果 $a_i=a_{i+1}$,则两者在同一段内更优。下面设 $a_i\neq a_{i+1}$。

考虑怎样 $i$ 和 $i+1$ 才能连边:

  • 首先显然要有 $a_i<a_{i+1}$。
  • 如果存在一个 $j$ 使得 $a_i<a_j<a_{i+1}$,则不合法。为了方便可以先离散化,则应有 $a_i+1=a_{i+1}$。
  • 如果 $a_{i-1}+1=a_i=a_{i+1}-1$,且 $a_i$ 出现次数大于 $1$,则不能同时连 $(i-1,i)$ 和 $(i,i+1)$。
  • 对于一个 $c$,最多只能有一条边 $(i,i+1)$ 满足 $a_i=c,a_{i+1}=c+1$。

考虑 DP。设 $dp_i$ 表示只考虑权值 $\leq a_i$ 的边,且连了边 $(i-1,i)$ 时边数的最大值。

转移从 $a_j<a_i$ 的 $j$ 转移过来;如果 $a_i$ 出现超过一次,则还不能从 $a_i-1$ 转移。因此只需要维护一个最大值和次大值即可。

输出方案的时候不要忘记把之前去重去掉的加回来。

Kebeb House

设 $dp_{i,j}$ 表示前 $i$ 秒、做当前串时已经做了 $j$ 次梦的方案数。转移有两种:

  • 如果这一秒不做梦,从 $dp_{i-1,j}$ 转移。
  • 如果这一秒做梦,设 $p=i-t-1$,那么

    • 如果 $p$ 时刻做的串不是当前串,那么那一串做几次梦都是可以的,所以从 $\sum dp_{p,k}$ 转移到 $dp_{i,1}$(这时一定有 $j=1$,因为 $i$ 是当前串第一个做梦的时刻)。
    • 如果 $p$ 时刻做的串是当前串,从 $dp_{p,j-1}$ 转移。

NEERC NSub 2013

Heavy Chain Clusterization

把每种前后缀拿出来,对于每个串把它的前后缀连边,问题转化为求二分图最小点覆盖。

最后修改:2021 年 03 月 04 日 08 : 38 PM