2015年挖的第一个坑。以前一直不想去做PA题，因为一直听说PA题非常SXBK而且还没有题解。现在既然DZY已经快把题解写完了，那进这个坑也就没有以前那么虚了。

最近在出CF，看到题目总是下意识的在想这道题在CF里碰到应该是哪一题。所以在一句话题解里再加上一个难度评价？（因为是蒟蒻做的感受，所以可能普遍会偏高。仅供自己理性愉悦一下。

[1.6]完结撒花，效率还行？最后留下一道神题不会和一道代码题不想写T^T。PA题如果在有题解的情况下做起来还是挺让人愉♂悦的。

现在做了几题

23

【PA2011】Tulips 难度：2A

考你会不会编程

【PA2011】Rooks 难度：2B

就直接把空的列分配给空的行就好了。

【PA2011】Unlucky 难度：1C-1D

一道有趣的题。首先一定存在一种最优方案满足以下条件：1.运走了所有的水。2.总路程最短。且最基本的策略是在路上设立若干个中转站。那么一定存在一个最优方案有：对于第[tex]i[/tex]个中转站，消耗这个中转站的水的只有第[tex]i-1[/tex]到第[tex]i[/tex]个中转站之间的路程。证明显然。然后就可以依次计算每一个中转站前进的路程，答案就是总水量减去总路程。

【PA2011】Climbing 难度：1A

贪心的取显然。设连续取的一段最左边的高度为[tex]x[/tex]，然后取的过程相当于不断加入不等式，直到无解位置。

【PA2011】Pedestrian Crossing 难度：1B

从开始走到每一个白段出发点一定是一个区间，只要判断这个区间是不是覆盖了[tex][0,l)[/tex]即可。细节比较恶心，如果是CF上一定是一道FST好题。

【PA2011】Journeys 难度：1C

就是一个有着奇怪的边的图的BFS。可以先对节点建一棵线段树，每一个节点记录一端包含这段区间的边的集合。然后开set记录当前还有多少个点没有被bfs过。然后直接BFS就好了，连接的边从线段树里找，每条边更新的点从set里面找。

【PA2011】Fuel 难度：1A

显然走最长链是最优的，到达链上的每一个点的代价是1，其他点的代价都是2，直接算就好了。

【PA2011】Plotter 难度：1C-1D

可以发现[tex]L_i[/tex]的图形相当于把[tex]L_{i-1}[/tex]以其最后一个点为中心顺时针旋转90度后拼接上去。然后我一直在想能不能找结构基元或者循环节啥的..最后去膜拜DZY的题解发现直接搜索就可以了。对答案有贡献的一定是[tex]L_{70}[/tex]以内，预处理出每一块的矩形界剪枝就好了。

【PA2011】Declining Sequences 难度：1C-1D

显然预处理出以第[tex]i[/tex]为起点长度为[tex]j[/tex]的方案数。然后离线，每一次相当于给出[tex]l,w,now[/tex]求一个最小的[tex]r[/tex]使得[tex]\sum_{i=l}^r dp_{i,now} \geq w[/tex]。因为所有数都是对[tex]10^{18}[/tex]取min的，就没有办法用减法了，所以在线段树上二分起来比较蛋疼。大致就是预处理出[tex]r[/tex]在线段树每一层如果和[tex]l[/tex]分开产生的额外代价啥的。

【PA2011】Double Factorial 难度：1B

求的式子是[tex]\sum_{i=1}\sum_{j=1}^n \left \lfloor \frac{j}{5^i} \right \rfloor [/tex]，当成等差数列然后用个高精求一求就好了。

【PA2011】Vocation 难度：1B-1C

直接匹配TLE，所以算每条边对答案减少的量，只要往周围15个点连边就好了，然后用KM（费用流会T）算最大权匹配就好了。

【PA2011】Road Network2 难度：1B

度数从小到大依次归给度数不为1的节点的儿子，注意要留下一个度数给它的父亲。无解当且仅当度数和不为[tex]2n-2[/tex]

【PA2011】Computational Biology 难度：1B-1C

开始没有看见每一种不同的循环同构都要出现这个条件，一直不会做。后来去看了DZY的题解才发现自己看漏条件了。因为都出现了所以每一个串只要和他循环一次的串连边就好了。然后再DFS找一下总出现次数最大的环。

【PA2011】Byteland Worldbeat Publishers 难度：1C

考虑交换两个匹配，因为权值不变所以对于任意的[tex]i<j \leq n, a< b \leq m[/tex]都有[tex]w_{i,a}-w_{i,b}=w_{j,a}-w_{j,b}[/tex]。因为这个有传递性，只需要考虑对于任意的[tex]i<j \leq n, a< m[/tex]有[tex]w_{i,a}-w_{i,a+1}=w_{j,a}-w_{j,a+1}[/tex]。因为值的变化次数是[tex]O(m)[/tex]的，只要判断一下这些断点就好了。

【PA2011】Exam 难度：1C

因为边长固定，所以不存在包含关系，可以求出每一个矩形最早与哪一个矩形相交，这个可以用整体二分+bit在[tex]O(n \log ^2n)[/tex]下求得。然后如果最早是和自己相交，那么就是所求答案。

【PA2011】Computational Geometry 难度：1A

很容易想到用很多[tex]1 \times 2[/tex]的矩形连起来，这样每2的面积消耗四个顶点，然后在最后再用一个[tex]1 \times k[/tex]矩形消耗完面积。

【PA2011】Coprime Numbers 难度：1B

容斥显然，先求出一个公约数为[tex]d[/tex]的对数，然后再减去它的倍数的贡献就好了。

【PA2011】Telescope 难度：1C

硬币一定是一段一段的连续投入，且每一段的最后一枚生效的第一时刻一定是一颗流星飞过的时候。所以可以预处理出[tex]f_{i,j}[/tex]表示在放入[tex]j[/tex]集合硬币且再放入一枚生效的第一时刻是[tex]i[/tex]飞过的时候最多看到多少的流星。然后再跑状压DP合并起来就好了。

【PA2011】Prime prime power 难度：1C

题目本身不难，卡常数SXBK。显然指数最大为61，可以先求出对每一个指数答案大于[tex]n[/tex]的最小底数是多少，然后归并。指数大于等于3可以先筛出1100000内的质数，指数为2可以用米勒拉宾判。

【PA2011】Hard choice 难度：1C-1D

就是维护边双，可以用LCT维护一颗生成树，然后每一次在已经联通的两个点之间连上一条边的时候可以把这一条路径上的点全部暴力加到公共祖先所在的并查集里面，然后再把这些点全部删掉。至于连接删去点的虚边可以再查询父亲的时候把父亲更新为父亲所在并查集的根。（题目很简单但是LCT总不能放到B题吧

【PA2011】Automorphisms 难度：1B

已经出烂了的题目。把重心作为根就可以把无根树的问题转化为有根树，然后就是各种hash。同一个父亲本质相同的儿子是可以相交换的，答案乘上本质相同儿子数目的阶乘就好了。

【PA2011】Kangaroos 难度：1C-1D

一个询问相当于询问筛去左端点比询问右端点大或者右端点比询问左端点小的袋鼠后最长连续区间是多少。可以对袋鼠序列分块，然后每一个块中询问的右端点和左端点都只有[tex]T[/tex]个有效值（[tex]T[/tex]是块的大小），即块中每一个袋鼠的左端点和右端点。然后就可以枚举这[tex]T^2[/tex]个组合预处理出左端连续的长度，右端连续的长度以及这个块中最大连续长度，预处理可以用双向链表实现（从大往小枚举左端点，变成一个一个插入）。块和块之间的合并就和线段树一样。时间复杂度[tex]O(m\sqrt{n \log n})[/tex]。

【PA2011】The Shortest Period 难度：1C

从小到大枚举答案，假设答案为[tex]ans[/tex]那么删除的位置有两种情况[tex][1,ans+1][/tex]或[tex](ans+1,n][/tex]，这两种都可以找到最终作为答案的串（一个是[tex][ans+2,2ans+1][/tex]，另外一个是[tex][1,ans][/tex]，特判超出[tex]n[/tex]的情况）。可以预处理原串在每一个位置删除的Hash值，然后再算出答案为[tex]ans[/tex]时长度为[tex]n-1[/tex]字符串的Hash值，二分查找一下就好了。

【PA2011】Laser Pool 难度：1E

原谅我代码能力差，这种代码题不放E报复社会放哪里！这道题我没有写，口胡一下做法。显然总共有[tex]\gcd(n,m)[/tex]个循环节，可以预处理每一个循环节的长度、经过的交叉点数、前[tex]i[/tex]次碰壁后的长度以及经过的交叉点数。然后每一个询问都是若干次循环加上若干次完整的碰壁加上一小段。接下来的问题就是如果处理框中一条线段经过了多少个交叉点。首先与多少条线相交很好算，至于交叉点就直接压位暴力就好了。（我想了很长时间怎么写方便一点最后还是放弃治疗了。