终于能完整刷完一届POI好高兴= =（其实还剩一道交互题。。）

Where to Build a Brewery?
假设1~n顺时针排列。记选择的地址为x，x+1~p的城市逆时针走，p+1~x-1的城市顺时针走。
首先算x=1时的p值以及答案，再逐步推得x=2,3,…时的答案（需预处理需求与距离的前缀和）。x顺时针移动的过程中p也会顺时针移动，恰好移动一圈，所以复杂度线性。
（从n绕到1的时候细节有些坑要注意）

Skiers
网络流裸题。拆点求最大流。
（标解似乎是贪心，尽可能选择靠右的路线。。因为它是个平面图而且还给定了左右顺序）

Stripes
每放置一条带子就把整条纸带分为左右独立的两个子游戏。
直接递推求出SG函数即可。

Viruses
所有串读进来建成AC自动机(DZY告诉我这其实叫做Trie图)，把不允许到达的结点（串末尾字符，或者能fail到串末尾字符）作上标记。然后DFS检查是否有不经过标记的环。

Signatures
从每个commander开始DFS。复杂度O(n)*O(n)=O(n^2)。

Automorphisms
将置换分解成k个轮换。
首先分析同一个轮换内的点之间的连边情况：
考虑某一个轮换，假设其为a_1->a_2->…->a_p。则在所求的图中，边(a_1,a_2),(a_2,a_3),……(a_p-1,a_p),(a_p,a_1)同向，边(a_1,a_3),(a_2,a_4),……,(a_p,a_2)也同向，……。可以发现p必须为奇数，否则能得出(a_p,a_p/2)与(a_p/2,a_p)同向，矛盾。当p为奇数时，按照上面的方法可以把所有这C(p,2)条边分成(p-1)/2组，每组内的边同向，于是有2^((p-1)/2)种方案。
再来分析不同轮换的点之间的连边：
假设两个轮换分别是a_1->a_2->…->a_p，b_1->b_2->…b_q。则边(a_1,b_1),(a_2,b_2),…同向。容易知道所有这p*q条边可分成gcd(p,q)组，每组内的边同向。方案数即为2^gcd(p,q)。
接下来关键在于统计[tex]\sum_{1\leq i < j \leq k}\text{gcd}(p[i],p[j])[/tex]。暴力只有65分。
O(nlogn)统计x[j]表示满足j|x[i]的i的数量。
然后令y[j]=C(x[j],2)，即为满足j|gcd(p,q)的无序对(p,q)的数量。
倒过来容斥，O(nlogn)得到z[j]，表示j==gcd(p,q)的无序对(p,q)数量。全部加起来即可。

Triple-Arm Crane
令p<=q。
设i是从左到右第一个未被占据的格子，如果此时i+p未被占据，则填上i,i+p,i+p+q（为方便叙述记为“对i进行p操作")；否则填上i,i+q,i+p+q("对i进行q操作")。
为证明这个贪心操作可以一直进行下去，只需证明不存在i+p,i+q同时已被占据的情况：
如果是这样，注意到此时i未被占据，则可以证明i+q必是由于对i-p进行了q操作而被填上的。但根据我们的摆放策略，i-p+p=i未被占据时本应该优先进行p操作，出现了矛盾。

Code
首先预处理出Catalan数C[i]。
若确定根结点为某个字母x，则其左右子树大小分别为x-1,n-x，此时的方案数即为C[x-1]*C[n-x]。
由于根是字典序最优先者，于是可以根据K的大小确定根结点的字母x，以及所要求方案在根节点为x的所有方案中的排名K'。
按字典序，左子树是第二优先，右子树是第三优先，所以左子树应该取第K'/C[x-1]，右子树应该取第K'%C[x-1]，递归处理即可。

The Labyrinth of Wells
题意有点绕，其实就是说颜色相同且三个出口分别对应相同（注意有可能是合并后才相同）两个结点是相同的，可以合并，求最后合并完后剩下几个结点。
题目说明保证了拓扑序，所以可以按拓扑排序逆序枚举结点i，检查i能否与i-1,i-2，…合并，合并时只需对被吞并的结点打一个标记即可。这样复杂度是O(n^2)，在main上被卡了。。。
于是把检查的过程改为hash表（用map就行），直接就能找到哪些结点需要合并。注意i和j合并后，需要将其他指向j的结点改为指向i，会导致这些结点hash值的改变。
（低端做法求不鄙视=-=）

Lollobrigida
（突然联想到今年NOIPDAY2第二题。。好吧还是挺不一样的。。）
容易想到一大一小交替放置。容易发现无解总是由于相同的元素不得不相邻摆放而导致的。
将a[1..n]排序。
若n为偶数，按a[n/2+1],a[1],a[n/2+2],a[2],a[n/2+3],a[3],…,a[n],a[n/2]排列。若这个序列不合法，则必然存在a[n/2+i]==a[i]，从而有a[i]==a[i+1]==a[i+2]==…=a[n/2+i]，即有n/2+1个数相同，此时可由抽屉原理证明必然无解。
n为奇数时也可类似构造，但需要特判前(n+1)/2或后(n+1)/2个数相同的情况。

P-Broken-Line
把所有出现过的X坐标离散化。注意x=-∞和x=+∞也要放入。注意若排序后x0,x1相邻，且x1-x0>=2，则要在x0,x1间加一个点；若x1-x0==1则不用。
Y坐标也一样离散化。然后形成了一个XLEN*YLEN的网格，其中XLEN,YLEN的大小都是O(n)的。把线段占据的位置标为障碍。
为了求得最小转弯次数，BFS即可，对u扩展就是从u向四周伸展的一个十字形（遇到障碍则break），扩展得到的新结点加入队列，转弯次数=u的转弯次数+1。
O(n^2)个结点，每次扩展O(n)，总复杂度O(n^3)可过。

Agents
令状态为(v1,v2)，表示此时a,b分别处于v1,v2两个点上。状态数O(n^2)，于是答案为O(n^2)级别。
BFS，每次转移需要考虑v1的出边和v2的出边，复杂度为O(deg[v1]*deg[v2])=O(n^2)。总复杂度O(n^2)*O(n^2)=O(n^4)，TLE。
考虑优化，把一次转移拆成两次转移，a先走一步，b后走一步。把状态表示为(v1,v2,bo)，bo=true/false表示下一步轮到a/b走。这样状态数仍然是O(n^2)，但每次转移只需考虑其中一个点的出边，O(n)。总复杂度O(n^2)*O(n)=O(n^3)可过。

Repetitions
后缀数组求height以后二分。（数据范围太弱似乎可以暴力）

Promotion
需要支持插入单个元素，查询并删除最大值，查询并删除最小值。
用set能在bzoj上水过，但在main上被卡成80分。改成手写treap依然80。
改用一个小根堆和一个大根堆同时维护这一堆数，数值相同的仅记录出现次数。同时对次数不为零的数值记录其对应结点在堆中的位置，方便删除。
这样在main上是94分，加上fread就能100。(标解应该没那么无耻吧。。也许是某种神奇优化)