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。
Comments (0)
