11
21
2014
0

论逗逼的自我修养之POI2012

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

作为一个蒟蒻,自然没有策爷那种一拍桌子“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]的点,然后一个一个插进去,用并查集维护环就好了 

Category: 论逗逼的自我修养系列 | Tags: | Read Count: 1015

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter

Host by is-Programmer.com | Power by Chito 1.3.3 beta | Theme: Aeros 2.0 by TheBuckmaker.com