POI18~20部分题(tu)解(cao)

Recursion posted @ 2015年2月25日 23:03 in 题解 with tags POI , 1569 阅读

今年年初开的新坑，填到现在也没填完→_→

POI题的质量还是相当可以的，题解虽然是波兰文的丢到谷歌翻译里翻成英文还是能看的。

到现在每一届还有好几道神题不会捉真是没救了

~~反正也没人会看，随便写写好了。~~

37/52 完成度：71.2%

poi20 colorful chain (poi居然有水题好开心>_<)开个数组记录一下每种数出现次数就行了，非常坑的是因为卡常数必须要开输入优化，第一次发现输入优化竟然效果这么明显...

poi20 where is the one 非常有趣的交互题...首先我们找到与1相差最大的位置，很容易发现这个差值一定大于[tex]\frac {n} {2}[/tex]，所以可以直接把[tex]f[/tex]函数当成判断是否相等。于是可以二分得到这个位置。然后扫一遍得到与这个位置相差[tex]n-1[/tex]的另一个位置，这两个位置明显是1和[tex]n[/tex]的位置，用[tex]g[/tex]比较一次大小就可以了...到最后[tex]g[/tex]只调用了一次...

poi20 take-out 一开始想了个方案发现不能保证连续性。然后发现貌似倒过来考虑就行了？由于我太懒用了set果断要爆炸...然后发现大吧的博客里有个很简单的实现方法，果然是我太弱了...

poi20 triumphal arch (听说这是前年分组赛的题？...)很容易想到二分答案，然后想了半天贪心未果...然后发现好像可以树形dp...国王的最坏路线一定是一直向子树走，令[tex]f_i[/tex]表示以[tex]i[/tex]为根的子树除了[tex]i[/tex]以外到达这个点之前需要建多少个门，然后递推一下就行了。又一次没特判1真是sb...

poi20 bytecomputer 大胆猜想以后发现答案序列一定都是-1,0,1。令[tex]f_{ij}[/tex]表示第[tex]i[/tex]位以[tex]j[/tex]结尾的最少操作数，暴力转移。

poi20 tales of seafaring (这题也是水题吧...)bfs搞出每个点的长度分别为奇数和偶数的最短路，然后发现只要存在一条奇偶性相同且不大于询问的最短路那么一定符合。

poi20 taxis 前半段很显然应该从大到小乘车，问题在于如何找到右半段走的一辆车，我直接取了最小的一个大于等于[tex]m-d[/tex]的车，然后就A了...要注意的是直接到达[tex]m[/tex]的情况。

poi20 tower defense game 这个样例给人感觉是，直接从小到大扫过去如果没覆盖到就覆盖。事实证明正解就是这个。

poi20 watering can 难得遇到数据结构题，非常良心的是用交互防止输入卡常数。每次区间加以后把所有不小于[tex]k[/tex]的值删掉，用一个树状数组维护就行了。

poi20 walk 神题。有一个很神的结论：删去[tex]k[/tex]个点后至多存在一个联通块大于[tex]nk[/tex]，于是暴力hash+bfs。看了半天题解实在没搞懂波兰人怎么证的，先挖个坑以后再看好了→_→我很想吐槽这种题真的是比赛时候能做出来的？还有把数据搞得这么sxbk，用vector暴力搞hash又爆内存又被卡常数什么心态，折腾了一下午70分我是实在没办法了→_→(对不起我真的不是故意想卡评测机的...)

poi20 price list 有趣的题。边删边边bfs。有一个很有趣的结论是一个无向图的三元环是[tex]O(m^{1.5})[/tex]级别的，所以可以过...而且事实证明跑得飞快，少见的100000级别的题所有点都在0.3s以内出解...

poi20 polarization 好题。最小值显然是[tex]n-1[/tex]。最大值的话，一个结论是一定存在一个点，其他的点要么指向它，要么它指向这个点。枚举这个点，然后就变成了若干个子树分成两组使大小尽量接近。如果这个点不是重心直接算就行了，否则进行背包dp。按[tex]\sqrt n[/tex]分成两组，大的组暴力背包，小的组按每一个值背包，总复杂度[tex]O(n^{1.5})[/tex]。

poi20 laser (因为是波兰文所以做的人少？明明是sb题)首先转换成角度，然后就变成简单dp了。

poi19 letters 经典逆序对的应用。

poi19 distance 这沙茶题我还想了半天...枚举约数暴力扫一遍就行了。

poi19 tour de byteotia 容易发现与前[tex]k[/tex]个点无关的边直接缩起来就行了，问题就转变为了给一个图，删掉最少的边使其无环，并查集维护一下就行了。又是sxbk卡内存，把并查集的合并操作不单独写函数就A了真是醉了。强烈怀疑波兰人的空间限制是骗人的→_→

poi19 fibonacci representation 64M内存在main上能干啥？典型暴力出奇迹。

poi19 squarks 有趣的构造题。[tex]s_1[/tex],[tex]s_2[/tex]显然是[tex]a_1[/tex]+[tex]a_2[/tex],[tex]a_1[/tex]+[tex]a_3[/tex],穷举[tex]a_2[/tex]+[tex]a_3[/tex]的位置，[tex]O(n^2)[/tex]贪心判断，用hash表维护每种值出现的次数。数据很良心没有卡map。

poi19 warehouse store 无脑贪心。把所有需求排序，维护前缀和就行了。

poi19 a horrible poem 好题。容易发现答案一定是区间长度的约数。枚举每一种质因子的个数，hash可以[tex]O(1)[/tex]判断是否循环，质因子可以线性筛预处理。不卡hash简直良心。

poi19 prefixuffix 又是一个结论题...终于见到卡hash的poi题了...双取模就行了，丝毫不虚。

poi19 vouchers 只需要记录下每个数的倍数取到了哪，然后暴力就行了。

poi19 salaries 乱搞题。其实也不算很难，但不看题解确实不好想清楚...

poi19 cloakroom 一开始以为是神题，后来想了很久后发现貌似直接离线背包就行了？...

poi19 bidding 滚动数组dp。

poi18 conspiracy 好题。先爆搜搞出一个方案，然后发现其他的方案一定是由这个方案最多删去一个点再加入一个点得来的，且答案规模一定是[tex]O(n)[/tex]的，暴力穷举就行了。判断团和独立集时可以直接比较度数和的差是不是[tex]k*(k-1)[/tex]，[tex]k[/tex]为团的点数。

poi18 lollipop 考虑最左边的1，向右延伸的和都可以通过这个1来调节得出所有的可能方案。右边同理。还有的情况是从最左边和最右边开始的区间。分别预处理一下就行了。

poi18 shift (dlh说这题是沙茶题我果然太弱了么T_T)通过两个操作可以实现将任意一个元素向前移两格。因此可以处理好前[tex]n-2[/tex]个数，若剩余的两个数位置不符，若[tex]n[/tex]为奇数，无解，否则将[tex]n-1[/tex]移到开头就行了。

poi18 difference 沙茶题。枚举出现最多和最少的字母，转化为最大子段和问题。

poi18 garbage (又一次喜闻乐见被卡常数)只考虑需要改变的边，然后用dfs搜出所有的环即可。

poi18 party (这题是来搞笑的么)删掉[tex]\frac {n} {3}[/tex]对不相邻的点就行了。

poi18 meteors 整体二分经典题，[tex]solve(st,en,l,r)[/tex]表示解决第[tex]st[/tex]到[tex]en[/tex]个询问，答案区间在[tex]l[/tex]到[tex]r[/tex]的结果，用树状数组维护[tex]l[/tex]到[tex]mid[/tex]的操作将询问分到左右两个子区间，分治之。

poi18 sticks 乱搞题。将所有木棍排序，去掉相同的，如果有等长的一定满足，否则穷举中间的木棍，维护每种颜色到当前位置最近的木棍，判断一下。32M空间限制开了一堆pair，set居然没爆炸有点感动。

poi18 temperature 沙茶题。左端点随右端点右移单调不降，用一个堆维护历史下端点最大值。

poi18 strongbox 由裴蜀定理可以推得就是要找一个最小的是[tex]a_k[/tex]的因数但不是[tex]a_{1..k-1}[/tex]的因数的数，预处理一下因数扔进map里就行了。

poi18 periodicity 超级神的构造题。考虑周期等同于考虑同时是前缀和后缀的串，搞出来以后分情况讨论。波兰人不能更神。

poi18 tree rotations 线段树合并...那个卡常数版本实在过不去，空间太大了...

以后可能会填的坑(特别sxbk的题不想做了)：

poi20 multidrink 前年分组赛的题，要各种分情况讨论，不会捉。

poi20 inspector 据说是傻×题但我感觉处理起来挺麻烦的...

poi20 maze 挺有趣的构造题，但是理由同上...

poi19 minimalist security 理由同上...

poi19 rendezvous 倍增乱搞，理由同上...

poi19 festival 貌似是差分约束系统，不会捉。