IOI 赛制!最有素质的一集!
Day 1
T1
什么 B 题。
首先对 $p$ 从大到小排序,一定取一段前缀做。暴力 DP $f_{i,j}$ 表示前 $i$ 个做对了 $j$ 个。可以证明有值的项不会特别多(???),大概是 $\mathcal O(\sqrt{n\log{\epsilon^{-1}}})$ 级别的,所以暴力就过了。
模拟赛场上写了一个非常不牛的分块 FFT,但是 luogu 上似乎被卡精度了。首先每个位置可以看成一个 $(p_i+(1-p_i)x)$ 的多项式。序列分块,处理出 $F_i$ 表示前 $i$ 个块多项式的乘积,块内用上面的暴力 DP。拼起来的时候前缀和优化一下即可做到 $\mathcal O(n\sqrt{n\log n})$。
还讲了一个很牛的分治。设 solve(l,r,F)
表示要处理区间 $[l,r]$,然后 $[1,l-1]$ 的所有多项式乘起来是 $F$。
对于 $[x^i]F$,如果 $i-(r-l+1)>k$,那这个 $f_i$ 在区间里一定有贡献,直接加到区间里面就行了。如果 $i+(r-l+1)<k$,那这个 $f_i$ 在区间里一定没有贡献,所以需要考虑的项只有 $[k-(r-l+1),k+(r-l+1)]$ 里面的,所以 solve 需要保留的多项式长度就是 $\mathcal O(r-l+1)$ 级别的。这样 FFT 一下就可以做到 $\mathcal O(n\log^2 n)$ 求出每一项的答案了。
T2
参考炫酷原神。
首先如何判一个子序列是否:把串扔进子序列自动机里,找到尽可能往前匹配的话,每个字符 $i$ 匹配到了哪个位置 $p_i$。如果存在相邻两个 $p_i,p_{i+1}$,满足 $(p_i,p_{i+1})$ 里面出现了一个和 $p_i$ 颜色相同的数,那就一定合法。容易发现这个条件是充要的。
看上去很像什么矩乘优化。从后向前 DP,$f_{i,j,0/1}$ 表示考虑了 $[i,n]$ 这个后缀,选的第一个数颜色是 $j$(注意 $j$ 所在的位置一定是 $i$ 后面第一次出现 $a_k=j$ 的位置 $k$),是否已经合法的方案数。
转移非常麻烦的分类讨论一下:首先是 $f_{i-1,\not=a_i,0/1}$ 都可以转移到 $f_{i,\not=a_i,0/1}$,表示不选这个 $a_i$。
而如果选了 $a_i$,那就是 $f_{i-1,j,k}$ 转移到 $f_{i,a_i,k\vee(t_{a_i}<t_j)}$,$t_{x}$ 表示 $x$ 这个颜色第一次在 $[i+1,n]$ 中的出现位置。
还有 $f_{i,a_i,t_{a_i}==n+1}$ 需要加一。$=n+1$ 表示后面没有出现过。
容易发现上面的转移满足了子序列自动机的条件,即一定是能靠前匹配就靠前匹配的。
转移可以写成大小为 $13$ 的矩阵,并且修改一个位置最多会修改 $m+1$ 个地方的矩阵(修改位置 $x$ 前面每一个颜色的最后一次出现位置的矩阵都有可能发生变化),但是两个矩阵相乘实际上不用乘这么多项,因为 $f_{\ast,1}$ 不可能转移到 $f_{\ast,0}$,并且常数项也不会变,加上一些神秘剪枝(比如判断矩阵实际上有没有改变,线段树修改 $m$ 个位置最后只 update
一次),实际是能跑过的。复杂度 $\mathcal O(nD(m)+qmD(m)\log n)$。其中 $D(m)$ 表示矩阵乘法需要的时间,剪枝之后可以达到 $3m^3$ 左右。
T3
遗憾离场。看上去像个分析性质题,实际上比较暴力。
首先暴力从后向前模拟,维护 $f_i$ 表示当前想让这个人同意的话,需要分给他 $f_i$ 个金币。显然从小到大选,复杂度是 $\mathcal O(n^2\log n)$。
核心性质是每个人分得的钱数一定不会超过 $\max(a)$(记为 $w$)。在 $i\rightarrow i-1$ 的时候,只需要令 $S_{i-1}=[i-1,n]\setminus S_i$,$S_i$ 是第 $i$ 个人的答案。
所以用线段树维护集合 $A_{i,j}$ 表示如果当前想让他同意,需要花费 $i$ 个金币,贪婪值等于 $j$ 的点的位置集合。
处理到 $i$ 的时候,从小到大枚举金币数量,什么时候需要的总和大于 $m$ 了或者人数合法了就停下。然后很讨厌的限制是金币相同的话编号从大到小选,所以确定了给出的最大金币数 $k$ 后,$<k$ 的所有人都要选,然后所有 $=k$ 的人选的是一段后缀。所以在所有 $A_{k,\ast}$ 上同时进行一个线段树二分,即可找出需要的区间。
这样操作就是,对于不选的人,金币数全部归零,然后所有人的金币数都加上各自贪婪值。这里会发生若干合并和分裂,需要线段树合并和分裂实现。这样是 $\mathcal O(na^2\log n)$ 左右。
注意到一个人清零之后,金币数就一定是他自己贪婪值的倍数,所以对于还没被清零过的数暴力处理(一个人最多被暴力处理 $256/a$ 次),这样复杂度可以优化到 $\mathcal O(n(a\log a+w(a)\log n))$,实际远远跑不满。
Day 2
T1
太魔怔了。
首先如果一个 $2\times 2$ 的矩形都是 $1$ 那就消不掉。找出所有这样的,剩下消不掉的形如若干条蛇。直接维护这个即可。
T2
判定区间 $[i,j]$ 是否合法:把 $[i,j]$ 内的设成最大值,其余设成最小值,设 $s_k$ 表示 $[1,k]$ 的前缀和,要求 $s_{i-1}$ 是前缀最小值,$s_{j}$ 是后缀最大值,$[i,j]$ 之间不存在前缀和小于 $s_{i-1}$ 的,也不存在前缀和大于 $s_j$ 的。这几个条件都可以简单处理,形如 $r\geq f_l,l\leq f_r$。
但是还有一个限制是,$i$ 左边的和 $[i,j]$ 不交的区间以及 $j$ 右边的和 $[i,j]$ 不交的区间的和需要小于等于 $[i,j]$ 的和。这个乍一看似乎没有单调性,虽然 $nex_r$(即 $[r+1,n]$ 的最大子段和)是单调的,但是 $s_r-s_{l-1}$ 并不单调。但是因为钦定了 $s_r-s_{l-1}$ 就是 $[l,r]$ 的最大子段和,所以可以取一个前缀 $\max$,这样两个函数都有单调性了,二分即可。所以最终限制还是形如 $r\geq f_l,l\leq g_r$。可以 BIT 统计,复杂度 $\mathcal O(n\log n)$。
T3
Day 3
小赢一手。
T1
简单题,一个边双里的数肯定需要全部相同。然后可以断开一条链,每个连通块内部颜色相同。看成每个大小为 $s$ 的连通块有 $\frac 1 2 s(s-1)$ 的贡献,要求总贡献尽量小。
然后 DP,设 $f_i$ 表示断了 $i$ 子树内的一个根链,同时断了 $(i,fa_i)$ 这条边,贡献最小值。然后统计答案就是枚举 $i,j$,贡献是 $f_i+f_j+\frac 1 2(n-siz_i-siz_j)(n-siz_i-siz_j-1)$,拆开之后是斜率优化的形式,上个李超树就行了。
T2
暴力是不断合并两个子树。问题变成两个有序序列如何归并到一起。可以用决策单调性分治加二分的方式得到很多分。
T3
爱拼才会赢。拼指拼暴力。
首先可以预处理一下,封装一个 $A(v,l)$ 表示有一个 $B$ 中的区间,最小值是 $v$,长度是 $l$,和 $A$ 中的任意一段拼起来的答案。单次查询复杂度 $\mathcal O(\log n)$。
然后对于 $B$,找出其所有笛卡尔树区间。被查询区间包含的是好算的。困难的是有交的。
序列上建线段树,从右向左扫,扫到一个点就把挂在这个点上的笛卡尔树区间加到线段树里。查询也在若干线段树节点里查询。
可以发现有决策单调性???然后维护一个决策栈就行了。
Day 4
T1
每个格子建一个点,然后建循环一样的图:
容易发现图上的一个圈是满足题目要求的。但是这样每个点可能会流好几次(就是一个格子里有四条边),只需要拆入点和出点限制一下流量就行了。题目要求一个格子有边的限制,所以是上下界最大费用循环流。