「已完结」做题计划1.0 2019-04-21

Solved 「42」 problems

JSOI2016 灯塔

POI原题,枚举根号,RMQ

JSOI2016 反质数序列

判掉偶素数(2),然后奇数偶数分开搞(奇数偶数之间不存在不合法),把不合法连边就是二分图求最大独立集。

JSOI2016 位运算

设选出的数字是从小到大的(要求互不相同),需要满足\(a1<a2<a3..<R\),S是一个二进制状态,第i位为0/1表示ai和ai+1相同/不同,第n为0/1表示an和R相同/不同,最后答案为\(f[2^n-1]\)。暴力dp过不了,注意S重复了K次那么转移相同,矩阵快速幂k下就好了。

JSOI2015子集选取

\(2^{nk}\)

JSOI2015 字符串树

对字符串间trie树,答案为链上的在trie树中某个点子树的点的个数。用主席树维护某个点到根上的答案,答案为\(ans(x)+ans(y)-2*ans(lca(x,y))\)

JSOI2015 送礼物

分数规划。 \[ a_i-a_j\geq mid\cdot(j-i+k) ~\text{or}~ a_j-a_i\geq mid\cdot(j-i+k)\\ ~~~(a_i+mid\times i)-(a_j+mid\times j)\geq mid \times k\\ \text{or}~ (a_j-mid\times j)-(a_i-mid\times i)\geq mid \times k \] 可以枚举ai作为最大/最小值,在[i+L-1,i+R-1]中查询aj+midj最小/aj-midj最大。

这样还漏掉了最大最小值距离<L但是选上周围的满足条件的时候,强制选L同理。

可以st表(Tnlog^2n)或者单调队列(Tnlogn)

JSOI2015 非诚勿扰

对于有n个候选人的女性,选中第i个的概率

\[ \sum_{i=0}^{\inf}(1-P)^n\times (1-P)^{i-1}\times P=\frac{(1-P)^{i-1}P}{1-(1-P)^n} \] 然后答案就是逆序对的概率乘积的和。

JSOI2015 套娃

按B从大到小贪心。

JSOI2015 最小表示

倒过来拓扑排序,bitset维护联通性。注意对于点u,越靠近u的点应该先考虑,比如说(1->2,1->3,2->3),那么对于1,先考虑(1->3)就割不掉边了。这样做的原因是距离1近的不会影响距离1远的,否则topo序就不对。

JSOI2015 圈地

裸最小割。有个数组n^2开成n调了好久。

JSOI2015 串分割

可以先把后缀排序,显然划分出的最大的串的长度只能为\(\lceil n/k \rceil\),所以可以二分答案为排名为第几的后缀,然后去check划分出来的串的个数和k的关系,这里可以贪心,如果长度为\(\lceil n/k \rceil\)能大于mid就选,否则选长度为\(\lceil n/k \rceil-1\)的。

PS:竟然是个环!!!没看到环调了两个小时!!!

JSOI2015 染色问题

本来打的DP,然后萎了。其实是个容斥,可以枚举\((i,j,k)\)表示至少有i列j行k个颜色没选的方案,然后容斥一下就好了,预处理次方才能O(n^3),其实也可以二项式定理做到\(O(n^2log)\)

JSOI2015 最大公约数

固定一个端点,不同区间的gcd的个数为log级别的,因为一次gcd至少要除2。那么以i为为端点,对于不同gcd求最小的左端点,因为只用log个,所以可以存下来搞。有点坑的是要特判掉区间只有一个数的情况。

JSOI2015 地铁线路

首先点连路线,边权为1,路线连点边权为0。第一问bfs就好了。

第二问,记fi表示沿着最短路到达i点的最长时间,把到达路线的时间从小到大排序(其实可以看成topo序),顺着最短路转移。转移形如i->路线->j这样的边,更新fj,这个转移复杂度为平方的,前缀/后缀max优化就O(n)了。

JSOI2015 symmetry

存下四个对称,旋转90和旋转180的矩阵后枚举矩形起点判断两个矩形是否相等。这里可以用二维哈希,和二维前缀和类似,选两个不同的base,有 \[ f_{ij}=f_{i-1,j}\times b_1+f_{i-1j-1}\times b_2-f_{i-1j-1}\times b1\times b2 \] 查询以\((x_1,y_1)\)为左上角,\((x_2,y_2)\)为右下角的矩形hash值就是 \[ ans=f_{x_2,y_2}-f_{x_1-1y_2}\times b_1^{x2-x1+1}-f_{x_2,y_1-1}\times b_2^{y_2-y_1+1}+f_{x_1-1,y_1-1}\times b_1^{x_2-x1+1}\times b2^{y_2-y_1+1} \] 这样其实是O(n^3)的,但是常数太大,某个点竟然要跑7秒。

这里比较神奇,如果边长为x(x>2)的正方形满足条件,那么一定存在边长为x-2的满足条件(中间那一块)。那么可以按照奇偶二分(二分最大的奇数,判断答案+1是否有解,有解就二分偶数,否则输出)。

JSOI2015 isomorphism

树hash板题。但是没有树的同构那个题那么暴力,不能暴力枚举根了。这个时候需要把无根树强行转成有根树。有一个方法是求重心。如果只有一个重心,根就是重心,否则两个重心之间一定有一条边,删掉这条边,新开一个点,然后新点连接两点,以新点为根。hash见树的同构。(JSOI15年怎么考了两个hash而且是同一篇论文里的..)

COCI2015 Divljak

按照插入的T建trie树是不可做的,需要按照询问的串S建trie,然后每加入一个P串时更新Trie树。更新的串自然是P的子串,然而子串可以看成一个前缀的后缀,所以把P在trie上遍历,每访问一个点把所有的fail树上的祖先都加上自己的颜色,最后其实是查询trie上点的颜色个数。这里每次把根到点的路径+1是会算重的,考虑类似寻宝游戏或者七彩树的做法,把点按照dfs序排序后在相邻lca处减掉-1就可做了,实现的话可以用树状数组维护(变成单点加子树查询)。

HEOI2012 旅行问题

题意:给定n个字符串,共有m次询问,每次询问输入四个数S1,L1,S2,L2,表示求第S1个字符串长度为L1的前缀,和第S2个字符串长度为L2的前缀,的最长公共后缀,满足这个后缀是给定的某一个串的前缀。(表示真心看不懂文字)

然后就很简单了,就是fail树上的LCA。

HEOI2012 采花

记录前两次出现的位置然后树状数组。

HEOI2012 朋友圈

比较神奇的一题。先假设朋友之间连边,首先A中只能选0,1,2个人,如果选的话可以枚举,然后就是算B,首先把和选出的A没有边的B点删掉,B点的同奇偶性的点之间是一定有边的,不同的点之间如果有边需要满足题目给的条件,求最大团。取B的反图,那么最大团转化为最大独立集,同奇偶性的无边,就是一个二分图,转化为算二分图最大独立集。

HEOI2013 Eden的新背包问题

CDQ分治或者暴力前缀后缀(都能过)。

HEOI2013 Eden的博弈问题

\(f[i]\)表示i点为黑的时候的最小需要染黑的叶子节点个数,当这个点是黑操作,那么出边只要有一个黑点必胜就好,如果是白操作则全要是黑必胜,可以直接dp,白必胜也类似,然后再dfs一下算一下方案。

HEOI2015 公约数数列

分块,每一块中不同gcd只有log种,存下每一块gcd为i的时候的所有xor值,然后暴力查询。复杂度为\(O(n\sqrt n \log^2n)\),是过不了的。考虑前缀的gcd也一共只有log种,对于每一块如果所有块内前缀gcd和全局前缀gcd求gcd出来是一样的就快速查询。这样复杂度为\(O(n\sqrt n \log n)\)

Heoi2013 Alo

直接考虑每一个点作为次大值时的答案,则要查询区间异或最值,可以用可持久化trie。求每个点作为次大值的区间有很多种方法,这里写了单调栈+二分+st表。

Heoi2013 Sao

题意:给一颗树,树上的边其实是有向边,问把这颗树拓扑排序的方案数

树形dp,考虑如何合并信息,信息可以看成一段决定了先后顺序排列。设u的一个子节点为v,要求u在v的前面。求u子树内的方案不是很好求。我们可以设\(f[u][k]\)表示u子树内,u排在第k的方案。由于子树和子树之间的顺序是不会影响的,有转移 \[ f_{uk}=\sum_i^{\min(\text{size[x],k})} \sum_{k-i+1}^{\text{size[v]}} \binom{k-1}{i-1} \binom{\text{size(u)+size[v]}-k}{\text{size[u]}-i} f_{ui} f_{vj} \] u在v后面的类似,这样是O(n^3)的。

注意那个式子中的j除了保证合法转移貌似没有什么作用,可以后/前缀和优化做到O(n^2)。

HEOI2013 钙铁锌硒维生素

题意:定n个线性无关的向量\(\textbf {A[1..n]}\)(如果不是线性无关直接输出无解即可),另外n个向量\(\textbf{B[1..n]}\),求能否给A中的每一个向量选择一个B中的备用向量,使得任意两个备用向量在B中编号不同,且A中的一个向量的备用向量和A中其余向量线性无关,输出字典序最小的解。

首相得会个暴力。暴力判断\(\textbf{Bi}\)能不能和\(\textbf{Aj}\)匹配,即判断Bi和其他的A是否线性无关。判断这个可以把向量看成矩阵的行然后求矩阵的秩是不是n,如果不是则线性有关。暴力判断完以后打个匈牙利输出方案,复杂度O(n^5)。

考虑上面的部分其实有很多步骤是不必要的。设\(V_{ij}\)表示\(B_i\)\(A\)中元表达的时候\(A_j\)的系数

因为A中的向量都是线性无关的,那么如果\(V_{ij}=0\),那么Bi不能作为Aj的备用机器人(其他向量可以表示B,不满足线性无关),如果不等于零,因为A都是线性无关的,B只有唯一一种表示,删去Aj以后就无法表示,B和剩下的线性无关。

\[ B_{ij}=\sum_{k=1}^nV_{ik}A_{kj} \]

仔细一看上面的式子,发现就是个矩阵乘法。 \[ \begin{aligned} B&=VA\\ V&=BA^{-1} \end{aligned} \]

求出A的矩阵逆以后就可以求出V了。

至于输出匹配方案,\(O(n^2)\)的贪心其实是错误的(详见BZOJ讨论),我只会一个\(O(n^3)\)的(顺次枚举,判断剩下的是否存在完美匹配)。

HEOI2015 小\(\text{Z}\)的房间

矩阵树定理傻逼题,\(\text{nm}\)全打的\(\text{n}\)还有70分。

HEOI2015 最短不公共子串

这sb题竟然做了三天

首先第一问直接hash每个s的子串存到map里面然后T查一下就做完了

第二问我们记\(\text{nxtt[i][j]}\)表示t串第i个位置后面的j字母第一次出现的位置。然后暴力枚举一个i串的起点,t串从头往后如果有\(\text{nxtt[s[i]]}\)就跳\(\text{nxtt}\),没有就可以更新答案了,把所有更新出来的答案取min。

第三问把t的所有后缀插到trie树上去,然后同样的维护一个\(\text{nxts[i][j]}\)表示\(\text{next}\)数组,在trie树上BFS,每次枚举26个字母,如果有nxts但是trie树上没有转移边就更新答案,否则把nxts和trie的转移边丢进去bfs。

第四问就是把第三问改一下,同样用bfs记录S串匹配到i,T串匹配到j和现在匹配到长度。枚举26个字母,S有转移T没有更新答案,否则继续bfs,注意同样的状态访问一次就不需要访问了。

这样就可以本地AC了。其实第一问的常数太大就过不了,改成和第三问一样的trie,然后枚举起点就好了。然后惊奇的发现trie树开不下MLE了。其实就是后缀自动机,把建树改成SAM就行了。

TJOI&HEOI2016 序列

DP+二维偏序

TJOI&HEOI2016 游戏

行和列二分图匹配,如果是硬石头新开一个点。

TJOI&HEOI2016 求和

\[ \begin{aligned} &\sum_{i=0}^n\sum_{j=0}^{i}S(i,j)\times 2^j\times (j!)\\ &=\sum_{i=0}^n\sum_{j=0}^{i}\frac{1} {j!}\sum_{k=0}^j(-1)^k\binom{j}{k}(j-k)^i\times 2^j\times (j!)\\ &=\sum_{j=0}^{n}2^jj!\sum_{k=0}^{j}\frac{(-1)^k}{k!}\times \frac{\sum_{i=0}^n (j-k)^i}{(j-k)!}\\ &=\sum_{j=0}^{n}2^jj!\sum_{k=0}^{j}\frac{(-1)^k}{k!}\times \frac{(j-k)^{n+1}-1}{(j-k)!(j-k-1)}\\ \end{aligned} \]

后面的sigma是卷积,最后一步是等比数列求和,注意公比为1的时候不成立。

TJOI&HEOI2016 字符串

串反过来建SAM,然后二分。一个串满足条件当前点在[a,b]之间而且在后缀树的子树中,是个二维问题,主席树解决。

TJOI2019 甲苯先生的字符串

快速幂模板

TJOI2019 甲苯先生的滚榜

平衡树+树状数组模板,竟然发现我平衡树板子一直有问题。

TJOI2019 唱、跳、rap 和篮球

由于不合法位置没有交,可以容斥,\(f_i\)表示至少有\(i\)个"唱跳rap篮球",其他随便放的方案。

至少有i个的方案是\(\binom{n-3*i}{i}\),因为填一个起点后面长度为3的就不能填了。

然后其他乱填的方案。设唱有a个人,跳b个人,rap有c个人,篮球d个,是个可重排列。

\(\frac{(n-4i)!}{a!b!c!d!}\),这个东西四个\(f(x)=\frac{1}{x!}\)这样的指数生成函数的卷积,答案为卷完的第\(n-4i\)项乘上\((n-4i)!\)

显然可以ntt优化到\(O(n^2log)\)。然而不用也可以过。

TJOI2019 大中锋的游乐场

\(dis[i][j]\)表示到\(i\)点,汉堡比饮料多\(j\)个的答案,最短路即可。

TJOI2019 甲苯先生和大中锋的字符串

SAM算一下Right集合的大小。每次把minlen到maxlen区间加一。

TJOI2019 甲苯先生的线段树

原题是CF750G

第一问暴力跳LCA。

第二问,考虑暴力枚举路径的LCA为\(x\),和左链长度L以及右链长度R。

这个时候可以确定一个上下界,下界是左右链全部向左儿子延伸,上界是全向右儿子延伸。

对于左/右链,如果从下往上的第i个儿子从左边改为右边,会独立地产生\(2^{i-1}\)的贡献

然后神奇地发现如果把\(x\)变成\(x+1\),LR固定,那么\(x+1\)的下界要大于\(x\)的上界。

也就是说对于固定的LR,我们可以唯一的确定x。

知道这个结论就好做了。

题目转为了两个01串,长度为L和R,第i位填1会有\(2^{i-1}\)的贡献,求总贡献为val的方案数。这个直接数位DPdfs就好了。

复杂度\(O(d^5)\)

GXOI / GZOI2019 与或和

单调栈模板题。

GXOI / GZOI2019 逼死强迫症

发现一个性质然后推出递推式,\(f_n=f_{n-1}+f_{n-2}+2\sum_{i}^{n-3}\text{fib}(i)\)

斐波拉切数列前缀和 \[ \sum_{i=1}^{n}\text {fib}(i)=\text{fib(n+2)}-1 \]

然后就直接矩阵了。

GXOI / GZOI2019 旅行者

拆二进制选起点/终点。BZOJ2407原题。

GXOI / GZOI2019 旧词

SNOI LCA原题。改成差分。