PA做着做着就不会做了,上一个坑绝壁是填不满了。。然后对波兰人产生了一些兴♂趣。
也算是⑩月新坑吧,督促自己多刷题QAQ。
我先为BZOJ打一发广告。
这是非VIP的POI题目数量
这是VIP的POI题目数量
也是挺感人的。
为了不浪费我花掉的钱,于是决定来刷一刷。
upd.9.29
[POI2007]旅游景点atr:spfa跑完以后状压dp
[POI2007]办公楼biu:显然补图的联通分量即为答案,然而补图很稠密,联通分量很小但是依然可以卡,那就bfs+删链表+回退链表好了,很好写1k足矣。
[POI2007]树Drz:感觉很恶心的线段树啊,各种情况判一判分别维护线段树,大概就这样,我还没写(也不想写了),可能会口胡成分比较大。
upd.10.20
1110: [POI2007]砝码Odw:这么神的做法我显然想不出来。首先从小到大贪心放一定是对的,然后由于题目条件设置,其实不同的砝码一定是一个等比数列,那么不同的个数就是log级别的,我们把这些不同的砝码看作进制每一位的基底,每个容器都进制分解掉,然后从小到大能装则装。
1112: [POI2008]砖块Klo:固定区间中位数,用树状数组就好了,难度瞬间下降。
1113: [Poi2008]海报PLA:长值何用系列。无脑做差。
1115: [POI2009]石子游戏Kam:阶梯nim,get√
1105: [POI2007]石头花园SKA:猜一个结论,放到[tex]y=x[/tex]一边去就可以是最优的,发现叉不掉自己,那就是对了:P,然后还有一问,有点恶心,[tex]max_x,max_y[/tex]以及[tex]min_x,min_y[/tex]两两是可以互换的,除此以外,还要判可行性,但你以为这样就好了嘛,矩形边长会爆int你服不服。
1117: [POI2009]救火站Gas:树形贪心?233333
upd.10.24
1119: [POI2009]SLO:置换圈找一下,找个最小值换,或者找全局最小值换。
1121: [POI2008]激光发射器SZK:光路可逆。
1122: [POI2008]账本BBB:枚举2操作有几次,维护前缀min,单调队列,好烦T T。
1123: [POI2008]BLO:割点。
1124: [POI2008]枪战Maf:自环判,“环套内向树”上判,环上判。。。
upd.10.26
1125: [POI2008]Poc:听说波兰人喜欢卡hash?事实证明还是有点节操的。hash搞搞,并查集搞搞就[tex]O(\alpha m)[/tex]了,一开始想用map,为了复杂度好看一点就没用。
upd.11.1
1130: [POI2008]POD Subdivision of Kingdom:复杂度只允许[tex]C^{13}_{26}[/tex]。所以要优化计算边的方法,就用位运算,分块预处理[tex]0\sim2^{16}-1[/tex]在二进制下[tex]1[/tex]的个数,然后dfs位运算就好了。
1131: [POI2008]Sta:dfs下去转移就好了。
1132: [POI2008]Tro:[tex]3000^2log_23000[/tex]居然可以过。。。枚举[tex]i[/tex]极角排序,叉积前缀和。
upd.11.20
1133: [POI2009]Kon:首先要知道两两站之间转移有效检票数,这个只要把读入的乘客上下方案每层做一个后缀和,比如做出来的后缀和是[tex]suf_{i,j}[/tex],那么[tex]i[/tex]站转移到[tex]j[/tex]站的有效检票数就是[tex]\sum_{k=i+1}^{j}{suf_{k,j+1}}[/tex],然后直接做复杂度是[tex]O(n^3k)[/tex]显然不对,主要是因为区间求和很暴力,很容易发现改动一下转移方式就可做到区间求和和转移同步,就优化了一个[/tex]n[/tex],可过。
1135: [POI2009]Lyz:
令每个大小的人数为[tex]p_i[/tex]
当前合法的条件是
[tex]\forall(l,r)[l\leq r],~\sum_{i=l}^{r}{p_i}\leq (r-l+1+d)*k[/tex]
移项可得
[tex]\forall(l,r)[l\leq r],~\sum_{i=l}^{r}{(p_i-k)}\leq d*k[/tex]
由于[tex]d*k[/tex]值固定,故问题转化为动态维护最大子段和,判断其是否超过[tex]d*k[/tex]
线段树。
upd.11.20
poi太神了。。。好多题做不动T T。。。弱死了
poi题解分年写了QAQ。