jiry_2's Blog

由于BZOJ的死亡率实在太高= =只好开新坑了> <

前几道是自己脑洞大随便找了几道题做，后来就跟着大爷们做集训队作业了...果然蒟蒻做不动题，回头看自己之前skip的题就开始持续低产了..囧

[10.25]终于把codeforces试题1的53道做完了..（最后几题啃的我快精分了）感！觉！自！己！萌！萌！哒！

[10.27]突然发现列表里面还有usaco的题？把以前做过的题加上去好像刚好100道。因为是滚粗狗不用交清澄似乎我可以口胡说我已经做完了？不过还是尽可能的把剩下的题目做起来吧。

[11.5]完结撒花！终于把列表里的cf题做完了。虽然交到清澄上估计就要跪一片但是已经和我没关系了。估计一段时间内是不会再去做cf的题了...

现在做了几道：

112

【464E】The classic Problem 主席树实现高精度

【464D】World of Darkraft-2 很显然等级过大时的影响可以忽略，然后分别DP概率和期望值，然后就T了...膜拜了别人的程序发现时倒过来DP，实在是厉害...

【301D】Yaroslav and Divisors 总共只有nlogn对关系，然后把所有询问左端点从大到小扫过来，贡献记录在右端点，然后树状数组就好了

【463E】Caisa and Tree 对于每一个质数维护一个数组dfs就好了..我就不吐槽那奇怪的输出了..

【317C】Balance 只需要考虑一颗生成树，然后每次完成叶子节点即可

【319D】Have You Ever Heard About the Word? 我用暴力直接过去了...标算是考虑到最多只有种[tex]\sqrt n[/tex]不同的长度，然后每次分段判断

【342D】Xenia and Dominoes 容斥原理，暴力枚举移动砖在哪个方向，然后状压DP

【273E】Dima and Game 把sg函数相同的一段一起处理，然后可以二路归并做。（我直接偷懒用打表过了

【257E】Greedy Elevator set大法好..里外分别维护上下两个set然后乱搞就好了

【316E3】Summer Homework 每个点维护一个矩阵就可以线段树做了，还是挺基础的。

【305E】Playing with String 两次看错题不能多说..每一段连续的中心都是独立的，所以直接处理连续中心的sg函数即可

【263E】Rhombus 花样无脑DP，慢慢写还是挺简单的

【293B】Distinct Paths 状压DP然后用hash存显然可行..但是我懒得写了所以码了爆搜然后T了..之后就是各种优化，关键就是如果你在同一状态下第一次使用颜色（无论哪种）的方案数是相同的

【325E】The Red Button 没有什么思路，然后就膜拜题解了，还是不是特别明白。奇数无解，x和x+n/2的影响集合是相同的，只要递归出只有一个环的解输出即可。

【241B】Friends Trie树建出来然后乱搞

【260E】Dividing Kingdom 爆搜所有可能的分配方案，然后用主席树判断是否可行

【338E】Optimize! 考虑分块，每一块都有[tex]m-\sqrt n[/tex]个数是相同的，然后把相同的数先配对，然后线性判断每个位置剩下的数是否合法即可

【249E】Endless Matrix 小学数学题..我坚信出这道题的人急需接受治疗（被常数卡了很久

【306B】Optimizer 贪心，每次最后选的“待定”，可以修改，之前选的纳入最优解。

【339E】Three Swaps 三次交换最多只能产生七段，每一次操作一定包含整数段。然后就可以搜索做了。开始WA了很久，后来发现递归进去后段的位置会变化，然后就A了。

【286E】Ladies' Shop 我们选取的质量为不能由两个包合并的包的容量。利用母函数的思想fft解决。开始一直爆精度？后来莫名其妙的过掉了。

【332D】Theft of Blueprints 直接用double求出方案总数以及所有的权值和，预处理出组合数就可以很容易的做了。

【261D】Maxim and Increasing Subsequence 可见t>=maxb的时候答案一定为出现过的数字种类，然后就直接暴力DP就好了

【335D】Rectangles and Square 开始码了一个大力出奇迹结果T成傻逼T^T可以用set维护一个矩形的上方和左方的后继，减少枚举数量即可（听说复杂度是nlogn的？）

【235C】Cyclical Quest 后缀自动机的应用，每次匹配后在开头删除一个数，沿着father跑

【311E】Biologist 最小割，还是挺裸的

【295D】Greg and Caves 花样DP，注意不重不漏，还是挺简单的

【286D】Tourists 把所有线段剖分成不想交的若干段，然后用堆维护即可。

【258D】Little Elephant and Broken Sorting 求出第i个位置值为j的概率，然后相同算半个逆序对直接搞就好了

【273D】Dima and Figure 写吐了..DP弱不能多说> <

【283E】Cow Tennis Tournament 居然被这种题卡住了感觉我没救了> <想法和剪刀石头布一样，计算不满足的对数，即有一人战胜两人的对数，可以用线段树维护

【305D】Olya and Graph 只可能存在两种边，然后累积答案就好了，细节比较多

【261E】Maxim and Calculator 最大质因数小于等于100的只有300万个数，DP出这些数的最小操作次数即可

【253E】Printer 二分答案，用堆搞

【243C】Colorado Potato Beetle 离散化BFS

【316G3】Good Substrings 后缀自动机求出每一个点能匹配的每个字符串的后缀个数，扫过去就好了

【256D】Liars and Serge n^4DP很显然，然后对n=256的点打表

【303D】Rotatable Number 结论题，详见http://en.wikipedia.org/wiki/Cyclic_number

【338D】GCD Table 中国剩余定理，挺裸的，就是10^12比较恶心

【266E】More Queries to Array... 线段树，维护[tex]A[i] \times i^j[/tex]即可

【332E】Binary Key 枚举每一个循环节有多少个1即可

【290E】HQ 愚人节的题目果然...看了半天才明白原来是要搜索HQ9+这个东西> <直接乱搞就好了

【333C】Lucky Tickets 直接meet in middle就好了，stl大法好

【240F】TorCoder 线段树，把回文串剖成两-三部分，每一部分可以用26个数字表示，把这个作为标记即可

【235D】Graph Game 和那道normal思路一样，不经过环的路径的贡献是[tex]\frac{1}{\text{dis(}i,j \text{)}}[/tex]，如果是在环上扣除两条路径的并的贡献即可

【301C】Yaroslav and Algorithm 用"??"在最后添上一个"?"，用"?"表示+1即可

【309D】Tennis Rackets 设三个变量，然后根据[tex]a^2+b^2<c^2[/tex]列出方程，枚举其中两个然后压常数

【301E】Yaroslav and Arrangements DP，每一种相同的数位分成一层

【309B】Context Advertising 开始看错题了，倍增

【277D】Google Code Jam 发现可以贪心，然后就是背包了

【341E】Candies Game 任意三个数都可以消掉其中一个，用类似于倍增+辗转相除法即可

【323B】Tournament-graph 考虑奇数，i向i+k连边，k是奇数连过去偶数连回来。然后偶数就加上一个点连向1,2。只有n=4是无解的。

【325C】Monsters and Diamonds 题面非常有迷惑性，如果可以无限下去可以结束那么无论值可不可以到达无穷都是-2，如果可以无限下去但是无法结束则不应考虑到最大值里面。然后就是建图+DP（基强连通图+外向DAG？），用优先队列维护最小值，记忆搜搞最大值

【266D】BerDonalds 先floyd求出最短路，然后枚举边，发现变成了很多斜率为1变成-1的分段一次函数，然后就sort维护前缀和啥的

【311C】Fetch the Treasure 注意到k特别小，然后加入x次数很少且x范围很大，那么考虑维护模k为i时能走到的最近点，用SPFA更新。答案用优先队列维护。

【316D3】PE Lesson 首先写出置换，发现只要每个循环节中1的个数小于等于2就是合法的。然后我就只会n^2了。膜拜了题解，抱着不求甚解的态度摘下了公式，过掉了> <

【323C】Two permutations 主席树（鬼畜的强制在线方式

【343E】Pumping Stations 类似zjoi最小割，传说中的Gomory-Hu tree。利用树上路径最小值就是最小割大小就可以贪心求解。

【267C】Berland Traffic 因为两点之间的距离是一定的，可以考虑设1到i的最短路为d[i]，d[n]=1，然后高斯消元求解。

【314E】Sereja and Squares 暴力压常数，结合309D食用风味更佳

【240E】Road Repairs 最小树形图模板题，就是输出方案蛋疼了一点。（终于学会这个以中国人名字命名的算法了）

【303E】Random Ranking n^5大力出奇迹，如果用FFT做多项式数组（元素为多项式）的卷积的话可以做到n^4logn但是似乎常数飞起？

【285E】Positions in Permutations 状压DP出至少有k个位置为好位置的方案数，然后容斥

【331C3】The Great Julya Calendar dp[i][j][k]表示后i位为99...99k，前面最大为j的答案，然后DP即可

【293E】Close Vertices 点分治，用树状数组搞搞

【288E】Polo the Penguin and Lucky Numbers 花样数位DP。

【274C】The Last Hole! 最后出现的洞一定是锐角三角形的外心或者矩形的中心，然后就是暴力的事了

【241F】Race 一道普及组题居然放F，而且我居然写了这么久。。开始傻逼求了最短路。。然后发现直接直线距离就好了，最短路反而会经过其他点。

【319E】Ping-Pong 开始想错方向+看错题了。用线段树套vector来维护并查集，每个点记录覆盖了这个位置的并查集编号。

【235E】Number Challenge [tex]f_{a,b,c,p}[/tex]表示只用了不大于[tex]p[/tex]的质数的答案，则有

[tex]f_{a,b,c,p}=\sum_{i,j,k}f_{\frac{a}{p^i},\frac{b}{p^j},\frac{c}{p^k},p-1} \times (i+j+k+1)[/tex]，用hash维护DP，开始MLE了，开了unordered_map就过了

【306C】White, Black and White Again 范德蒙特卷积（唉实在是傻叉了，具体数学白看了）

【241E】Flights 查分约束系统（太久没用居然这个都没看出来

【268D】Wall Bars [tex]f_{i,a,b,c,d}(0 \leq a \leq b \leq c \leq h,0 \leq d \leq 1)[/tex]表示高度为i时三个柱子最近一次距离为abc且新加的位置是否可以到达，然后就可以DP了

【254D】Rats 首先把一个划进一个集合中，然后第一个只可能出现在[tex]2d^2+2d+1[/tex]个位置中，枚举第一个的位置再判断没有被覆盖的有没有交集即可

【269D】Maximum Waterfall 边一定是O(n)级别的，然后如果按照高度排序就可以用线段树做，有点麻烦，如果按照左端点排序就可以用set的维护了，插入一个点删除他的前驱后继之间的边并且在它和它的前驱、后继之间连边。

【264D】Colorful Stones 开始以为只要维护一个最早能配对的一个最晚能配对的两个位置扫过去就好了，然后发现不对...膜拜题解后发现只要特判一种情况，即上面的串以xy结尾，下面的串以yx结尾也是不可取的（仔细想想还是挺显然的）。

【280D】k-Maximum Subsequence Sum 这题太神了。。用线段树模拟费用流的过程，每次取出最大的子区间（即最长路）然后取反（即增广），重复k次得到的就是答案。要维护的东西实在太多，写的真是带感

【329D】White, Black and White Again 1W个格子发出10W次声音那么只能循环了，随手码了一个循环估计了一个常数就贴着过去了囧

【335F】Buy One, Get One Free 神题，开始以为是傻逼贪心，看了standing后直接膜拜题解...从大到小取，差分后贪心，如果原来的最小贡献比现在的价值小则直接顶掉，否则判断放两个进去优还是不变优，用堆维护。

【294D】Shaass and Painter Robot div2D都不会做是不是要滚粗了..结论：边上所有的点都走过时恰好完成覆盖。然后就用个map搞搞暴力就好了。UDLR依然很恶心。

【241D】Numbers 策爷告诉我只考虑1-31一定有解，但是不会证。据说mx爷证明了得到解得概率十分接近1？Orz...

【249D】Donkey and Stars 把坐标缩放成直角，然后就是一个最长上升子序列了（我开始逗逼写了个树状数组囧）

【274E】Mirror Room 消棋子最终鬼畜版...麻麻我终于会用set和map了

【317E】Princess and Her Shadow 首先先沿着到影子的最短路走，走道无穷远处说明就没有障碍了，可以利用最边界的四个点搞定。

【325D】Reclamation 显然如果土地围成了八联通环就不行，把网格图复制成两块，然后判断是否存在一条(r,c)到(r,c+m)的只经过土地的路径即可

【360D】Levko and Sets 对于每一个[tex]a_i[/tex]求出[tex]a_i^{c_i}=a_i(mod p)[/tex]然后容斥就好了，开始用bsgs求+滥用stl直接T成傻逼..后来膜拜题解发现可以用指标求？然后就过了。。

【306D】Polygon 先搞一个正多边形，再把每一条边平行的移出去一点即可

【264E】Roadside Trees 转化为倒过来求最长下降子序列，然后用两棵线段树维护位置不在前10以高度为关键字的信息以及高度大于10以下标为关键字的信息，然后暴力搞搞。调了半天最后发现是线段树写跪了。。也是醉了

【280E】Sequence Transformation 好神的题。DP做法很显然，把考虑前i项的DP数组看成第i项取值的函数，可以证明导数单调递增。然后只要维护这个分段函数就可以了。（听说清澄上面数据范围加大了？请让我默默点根蜡烛

【354D】Transferring Pyramid 开始看错题了囧，然后点开了题解，然后就被剧透了一脸，考虑由最右端一个三角形最下角挖去一个三角形的情况，当大三角形扩大一列后只可能选择一个点作为change的顶点。这是可以再[tex]O(n^2)[/tex]的时间内DP出来的，又选择的三角形的大小一定不会超过[tex]\sqrt {k}[/tex]，就可以优化到[tex]n\sqrt{k}[/tex]

【309E】Sheep 不会做，又没有题解。后来策爷给了我两篇英文论文，看的我真是恨不得滚回去学英语了...后来勉强对着论文+约大爷的代码写了出来，现在还是处于不明觉厉的状态囧...

【251E】Tree and Table 令[tex]f_i[/tex]表示把以[tex]i[/tex]为根的子树放到网格图中且i固定在左下角的方案数，这是可以DP的，接下来就是分类讨论+分类讨论了..（我居然真的写出来了！感！觉！自！己！萌！萌！哒！

【356E】Xenia and String Problem 先计算出以每一个位置为中心的字符串的最大长度，然后可以用堆来算出覆盖了某个位置的字符串的权值和。接着枚举每个位置每个可能的字符，然后枚举这个位置作为长度为[tex]i[/tex]的字符串的中心然后向两边扩展即可，复杂度应该是[tex]O(nlog^2n)[/tex]

【331E2】Deja Vu 爆了差不多30发OJ，完整的路径一定经过一条看到的包含这条边的边，于是可以预处理出极短满足条件路径，不包含满足条件路径的前缀后缀，然后DP，因为有不能看到东西的边存在所以很恶心..（开始把极短满足条件路径拼上这种边当做前缀和后缀最后发现是错的...）正确的姿势是先DP出不刻意包含（可以出现在极短路径上）不能看见东西的边的答案，然后再拼成后缀再DP一遍即可。

【269E】String Theory 爆交54发！最开始直接暴力染色，爆交n发，然后发现非四个角的循环有可能不同，爆交n发，然后又发现当前状态DFS出来的循环的起始点和终止状态可能不一样，是循环同构的关系...WTF！后来把每个循环搞成01串然后最小表示最后双hash搞..但是还是因为一些细节问题WA了好久囧..A了这题有种飞升了的感觉..

【335E】Counting Skyscrapers 首先如果输入时是Bob的话那么答案就是[tex]n[/tex]，考虑Bob已经走在一个高度为h的通道上，那么它终止于于高度不小于[tex]h[/tex]的楼房，所以期望经过了[tex]2^h[/tex]幢楼房，而其贡献也是这个值。如果输入是Alice的话考虑一层一层加上去然后去掉重复的贡献，可以推出一个式子。

【238D】Tape Programming 好神啊..每个区间的状态一定是1跑到n的一段，所以只要从1跑到n（注意可能有几段）然后计算每一段的贡献就好了

【331D3】Escaping on Beaveractor 先用set大法求出后继，然后倍增即可

【293D】Ksusha and Square 枚举横/纵坐标求出这一条直线上整点个数然后累加即可

【321D】Ciel and Flipboard 到现在为止还对线代一无所知的我是不是和时代脱节了？考虑一条线上坐标差距为[tex]x[/tex]的两个点以及中点，一定有偶数个点被翻转，然后充分性要用线代证明。于是只要枚举[tex]x[/tex]个点的状态然后贪心求最大值即可。

【351D】Jeff and Removing Periods 问题相当于询问区间内有多少种数以及区间中是否存在一种数的下标为等差数列，可以把右端点排序，因为右端点固定下来后一种数字为等差数列的范围一定是一个区间，用一颗线段树+一个树状数组维护就可以了。

【329E】Evil 看不懂题解..对着ydc的程序码了一发然后WA62..然后根据ydc的程序把[tex]\leq[/tex]改成[tex]>[/tex]然后就过了？不知道是数据弱还是什么其他原因..留个坑以后回来填

【251D】Two Sets 很好的题，开始看到题目果断就Trie树建出来然后滚粗了2333。贪心很容易想到，然后把每一位的贪心结果转化成一个方程然后用类似于高斯消元的解法来做，如果矛盾说明就无法取到。

【316F3】Suns and Rays 你需要计算出题人的脑洞上长了几根毛。首先把外围的0向里扩张[tex]a[/tex]次，把毛都搞掉，然后把剩下的圆向外扩张[tex]b(a \leq b)[/tex]次，然后在现在的图中没有被染色但是原来被染色的就是毛，统计联通块个数即可。接下来就是愉快地调参数环节。我调了半天最后干脆特判了

【348E】Pilgrims 所有黑点到最远黑点的路径一定经过最远黑点对的中心，于是把中心作为根则一定经过中心，然后可以用map套个pair搞。

【243D】Cubes 把所有的方格都投影到一条线段上然后离散成整点。然后按照这个方向的先后顺序一点一点的插进线段树，线段树里维护的是一个区间段里面的最高高度，然后只需要统计答案然后区间修改即可

【248E】Piglet's Birthday 打着运动会的借口浪了一天，晚上做了一道傻逼题来避免颗粒无收的惨剧。其实这题是239C，每个书架上面没有被尝过的一定小于等于100，令[tex]f_{i,j}[/tex]表示第[tex]i[/tex]个书架有[tex]j[/tex]个瓶子没有尝过的概率，答案就是[tex]\sum_{i=1}^n f_{i,0}[/tex]，每一次只要枚举[tex]j[/tex]以及取走了多少个没尝过的瓶子排列组合搞搞即可。

【360E】Levko and Game 结论：每一条边的权值不是[tex]L_i[/tex]就是[tex]R_i[/tex]，对于两个起点做最短路，然后对于每一条边权为[tex]R_i[/tex]的边，如果[tex]d1_u < d2_u[/tex]那么就变成[tex]L_i[/tex]，然后判断到终点距离哪个小，判断平局只要把[tex]<[/tex]换成[tex]\leq[/tex]即可。

【243E】Matrix 去学了学传说中的PQTree，又花了点时间搞点其他的事情，所以AFK了好久。终于把PQTree调出来了，看着十几K的代码也是有点小激动

【346E】Doodle Jump 大致思路是把问题的规模减少，但是题解中的证明还不是特别明白，先留个坑。

【238E】Meeting Her 令[tex]f_{i,j}[/tex]为在第[tex]i[/tex]个点坐着第[tex]j[/tex]辆公交车的最优解，然后用类似与最短路的方法更新答案。

【297E】Mystic Carvings 三条线段共有五种可能的情况，除了要计算的两种情况分别问川、XI、H三种，其中可以通过枚举中间边计算“川”型，而XI和H都有两条不相交的线段，枚举其中一条即可。预处理一条线段左边和右边的线段条数我是用主席树实现的，似乎离线搞搞可以用树状数组？