又开新坑辣~\(≧▽≦)/~

作为一个蒟蒻，自然没有策爷那种一拍桌子“POI怎么那么多人做的”，然后就去和PA大战三百回合的气魄，只好挑那些大爷们早已写过题解的题目做。

完结撒花。感觉POI2012的题目要比POI2013的题目和谐很多> <

终于水完一届完整的POI辣

现在做了几题

17

【POI2012】Festival 查分约束系统显然，如果查分约束系统建出来是一个DAG，那么答案一定为[tex]n[/tex]，所以只需要考虑把每一个强连通分量的数值种类累加起来就好了，这个可以用最长路搞。

【POI2012】Letters 贪心按照顺序一个一个匹配然后跑逆序对。

【POI2012】Distance 枚举约数大力出奇迹。

【POI2012】Rendezvous 典型无脑傻逼题。

【POI2012】Well 二分显然，如果确定了[tex]k[/tex]和[tex]z[/tex]，那么正反各扫一遍就可以得到操作最少的序列。然后考虑每一个[tex]k[/tex]的操作次数由[tex]k-1[/tex]得到。开始写了一个堆，在main上面只有90分。实际上可以转化为区间加一然后差分扫一遍就好了。

【POI2012】Vouchers 典型无脑傻逼题。

【POI2012】Cloakroom 这种题都要看剧透我是不是没救了...[tex]dp_{i,j}[/tex]表示用了按照[tex]a[/tex]排序后前[tex]i[/tex]个组成[tex]j[/tex]时[tex]b[/tex]的最小值的最大值。把询问离线然后背包就好了。

【POI2012】A Horrible Poem 哈希，答案一定是询问长度的约数，可以考虑枚举长度质因数的幂次来确定答案中这种质因数的次数，这样就可从[tex]O(m \sqrt n)[/tex]优化到[tex]O(m \log n)[/tex]

【POI2012】Fibonacci Representation 直接记忆搜，大力出奇迹

【POI2012】Squarks 小清新构造题，枚举第二小和第三小的和是那个位置，然后判断就好了。

【POI2012】Bidding 暴力DP，因为第一维的状态只有[tex]O(\log ^2 n)[/tex]

【POI2012】Salaries 求出每一个位置的上届，然后扫一遍。

【POI2012】Leveling Ground 差分之后用扩展欧几里得算法求出每一个位置的方案，然后再贪心的调整每一个位置，可以用堆实现。

【POI2012】Minimalist Security 每一个联通块设一个未知数搞就好了

【POI2012】Warehouse Store 考烂了的贪心，先能取就取，不能取就牺牲取了的最大的那个。

【POI2012】Prefixuffix 枚举开头那段的中间点，随着中间点左移，能匹配的最大长度一定不大于左移之前的长度+1。数据有一点卡hash

【POI2012】Tour de Byteotia 先删去小于等于[tex]k[/tex]的点，然后一个一个插进去，用并查集维护环就好了