题解

拍照

从$1\sim n\{1\backslash sim\; n\}$和从$n\sim 1\{n\backslash sim\; 1\}$分别跑一遍最长上升子序列，枚举最高的人$i\{i\}$时，计算$1\sim i\{1\backslash sim\; i\}$和$n\sim i\{n\backslash sim\; i\}$之和，取和最大的$i\{i\}$。（枚举最高的人$i\{i\}$时要保证$i\{i\}$被选到，所以要分别从前和从后跑一遍最长上升子序列

code

素数

明显的，对于能拆分出奇数个素数的数来说，它们两两之间要么互质，要么大数/小数为非素数。对能拆分出偶数个素数的数也是同理。

按拆分出的素数个数的奇偶把整数集合中的数分为两个集合，两个分别连接源点和汇点，商为质数的两个数连边。那么其实就是求这张图的最小割，然后答案就$n-\{n-\}$最小割。最小割最大流。

code

幸运

AC自动机+dp状态压缩板子题，这题的原题是：DNA Sequence

先讲原题

原题是多组输入

第一行输入$n\{n\}$和$m\{m\}$，$1\le n\le 2000000000,0\le m\le 10\{1\backslash le\; n\; \backslash le\; 2000000000,0\backslash le\; m\backslash le\; 10\}$

后面$mm$行，每行一个长度不超过10的字符串，只由$A,C,T,G\{\; A,\; C,\; T,\; G\}$构成

输出长度为$nn$且不包含这$mm$个字符串的字符串个数。

思路

这个图是例子$\{\mathrm{“}ACG\mathrm{”},\mathrm{”}C\mathrm{”}\}\{\backslash \{“ACG”,”C”\backslash \}\}$,构建trie图后如图所示，从每个结点出发都有4条边$\mathrm{（}A,T,C,G\mathrm{）}（A,T,C,G）$

从状态0出发走一步有4种走法：

• 走A到状态1（安全）；
• 走C到状态4（危险）；
• 走T到状态0（安全）；
• 走G到状态0（安全）；

所以当n=1时，答案就是3

当n=2时，就是从状态0出发走2步，就形成一个长度为2的字符串，只要路径上没有经过危险结点，有几种走法，那么答案就是几种。依此类推走n步就形成长度为n的字符串。

matrix矩阵如下(矩阵i行j列的权值是结点i转移到结点j的方案数)：

n=1
2 1 0 0 0
2 1 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0

n=2
6 3 0 0 0
6 3 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0

原题的代码改下模数以及字典树部分就行了。

code 含解释

摆花

从$a\{a\}$开始往后找空位，然后依次摆放$b\{b\}$盆花，输出这一轮摆的第一盆花和最后一盆花的下标，如果摆不下$b\{b\}$盆，输出$0\{0\}$，但是能摆下的还要摆。注意这几点后，二分第一盆花和最后一盆花的下标，用线段树维护区间有多少盆花。

涉及区间覆盖，区间查询。注意区间覆盖的值为0时$lazy\{lazy\}$标记的处理。

code

单车

对每个单车跑一遍bfs，找到任意一个单车到任意一个停车位的最短路。把单车和停车位分别看成一个集合，这就是一个裸的二分图最大权匹配。可以无脑上$KMKM$或者网络流的板子。

code

括号

时，我们可以直接枚举左端点，然后统计贡献，复杂度$n^{2}n^2$。原题连接：C. Compressed Bracket Sequence

$n\{n\}$的范围较大时，可以用栈去模拟括号匹配，然后分类讨论：

• 左括号数等于$x\{x\}$，右括号数等于$yy$
• 左括号数$==\{==\}$右括号数，贡献$y\{y\}$个合法匹配，看左边有多少对连续的连续的完美括号匹配，如果有$k\{k\}$对，那么又贡献$k\{k\}$个合法匹配，同时$++k\{++k\}$。eg，当前左右括号为$((()))\{((()))\}$，$k=2\{k=2\}$，$kk$对连续的完美括号匹配为$()(())\{()(())\}$，那么$()(())((()))\mathrm{、}(())((()))\{()(())((()))、(())((()))\}$也是合法匹配。
• 左括号数$>\{>\}$右括号数，贡献$y\{y\}$个合法匹配，同时$x-=y\{x-=y\}$，当前只有一对连续的完美括号匹配。
• 左括号数右括号数，贡献$x\{x\}$个合法匹配，同时$y-=x\{y-=x\}$，看左边有多少对连续的连续的完美括号匹配，如果有$k\{k\}$对，那么又贡献$k\{k\}$个合法匹配，并继续分类讨论。

code