Ois

一点闲话 感觉这题好弱啊.应该有一堆神犇能秒吧. 取模是为了避免输出long long的问题.不知道有没有人中间就取模了2333. 这题的idea源于wc2015的k小割.考场上写了良久最后mle. 于是我决定这题既不卡空间也不卡时间. 是不是感觉我的题比ioi和zyf的题都良心啊hhh 测试点1-6 这六个点的权值和非常小.于是可以树形dp.用fi,j表示以i为根的子树中权值和为j的方案总数.于是可以dp一下就得到答案. 测试点7-8 接下来的点都是大数据了,然而还是有一些部分分. 比如这个. 没有题的一条链情况比这个题更简单了吧ovo 测试点9-10 这是最简单的菊花图ovo似乎就是k小割的弱化版啊.做法比较多喽. 介绍一个叫做学姐二分的方法.二分一个答案,然后强行dfs方案.如果总方案数大于k就直接结束.这样是可以保证复杂度的TAT 测试点11-12 一条链变成两条链了.一样的二分答案然后枚举一边二分另一边嘛. 剩下的测试点 这些点没办法用奇怪的方法了吧?有人用奇怪方法黑过去的和我说一声ovo 考虑当前如果已选的某个点集S,我们也把它叫做一个状态. S可以向S中任意点的没有在S中的儿子扩展.设扩展后的状态叫S’.(它可能有很多个) 不难想到,已知前k小的状态S1 .. Sk后,第k+1小的状态一定是S’1 .. S’k中权值和最小的一个. 于是我们就是要维护当前所有状态的可扩展的状态. 对于每一个状态,用一个可持久化堆来记录它能扩展到的所有点,然后取其中最小的一个加上它本身的权值和扔进外层的堆里. 那么每次外层堆里的最小值就是第k+1小的状态. 那么找到k+1小状态后,就要将这条边从原状态中删除.然后对于新扩展出来的状态,把新扩展出来的原树上的点的所有儿子也扔到这个状态的堆里就好了.注意有的点的度数会很大,所以每个点的儿子本身就要用可合并堆来存. 然后直接找下去直到扩展出第k小的状态就行了. 以上所有操作的时间复杂度都是O(log(n))的,所以总复杂度是O(k*log(n))的. 另一种思路 上面提到过的"学姐二分"也可以应用到这里.因为我也没写过所以不作重点介绍了.大家可以自行思考一下. 劼司机的思路 (苣蒻的出题人并不能理解这种做法,你可以去找劼司机本人讨论ovo) 就是把树画到平面上。。 然后建个对偶图 对偶图里每条边的边权为他子树里边权和 也就是。。 在对偶图里走过一条边，等于把这条边下面的子树砍掉。。 然后就没了。。。 吉利就是这么虐人的！ 松爷好强!

唯一一道有点麻烦的题.似乎是Picks出的?orz.于是窝就90辣. 据说可以链剖然而退役的laekov已经搞忘了那是啥. laekov思考了五分钟. 把所有链按长度排序.答案必定是这个路径序列的某个前缀的并集上的最长边. 然后并集只会减小不会增大.于是暴力判断当前并集端点是否在下一条路径上就可以了. 于是会被卡常数ovo窝也不知道怎么破.在uoj上加了个读入优化炸糊过去了. 然后窝程序在最长路径长度为0的时候会因为数据结构写丑而死循环ovo 反正还是挺水的啊.noip的压轴题怎么能这么水.

水水的dp.压一维状态表示上一个字母到底有没有被用就可以算出子串数了. 然后会mle就滚一维呗.有高一小朋友不知道2333. 似乎会卡常数23333.

水水的二分答案. 想四年前classroom还属于思考题.现在就已经沦落到开场题的地步了.oi界发展迅速啊. 然而真的不是3分钟搞定?

day1考的农业题.据说可以状压然而退役的laekov已经不会写状压了(雾. 于是直接dfs就好了啊23333 每次搜索的时候强制把当前点数最小的牌出掉至少一张.这样时间复杂度/=答案!.然后就完辣.

依然是水水的题. 基环内向树.从任意点开走要么是o型环要么是ρ型环. 那些写bfs的是啥心态.非要展示代码能力么. 以及谁说没考数论的?这题不就是"泼辣的肉"的推广(雾.

noip成绩终于出来辣可以水水地写个题解辣.假装窝还是在更新窝的网站嘛. “这么水的题还要写题解?” “对不起嘛,laekov是noi才ag弱渣嘛.” 3分钟题ovo.

这东西是写给jxfls的学弟学妹们的.cdqz众好好听毛教授的话就行了不要管窝. 写这个的目的是窝作为一个过来人对于泥萌进省队或者拿noi的Au给一点建议.(然而窝也没有noi的Au,所以泥也可以当窝是在口糊) 首先要明确一下这有什么好处.如果进了省队且noi至少拿了Cu(70%诶,sc算是中强省所以会有不少人垫背的),那么会有学校和泥签约.比如考上一本就可以被某校录取.某校嘛好点的比如pku,thu,sjtu,fdu,再有uestc,zju之类的.然后如果拿了Au(即前50),就可以被点招,高考0分上thu(或者泥愿意去pku啥的也行). 毕竟是jxfls出来的.在jxfls若干年也没有见过进省队的.窝想如果jxfls出现至少一个省队,那oi在学校里的地位也许就不一样了.说不定就能进入某种良性循环.如果能出noi的Au,规律是有一就有二,然后有三.毕竟Au爷可以不用高考,而是可以把精力放在冲国家队和提携后辈身上.如此往复.也许这要等很多届.也许永远也不能成功.不过这也算是窝曾经的心愿了吧.这篇文就算是窝尽一点绵薄之力了吧. 其实这件事在jxfls这种难以停课的地方并不容易.cdqz众多半从高二开学就不上文化课了.经过若干个月全力以赴的oi学习,水平自然是不同的.所以泥萌更要抓紧时间. 首先泥要意识到泥有多弱.noip在省选中占30%.泥可以把noip里高三的刨开之后看一看泥在能进省队的人里排在什么位置.也许很多人曾经以为noip一等就是终点.其实它是起点.所以说不要认为自己很厉害.省内,在cdqz,在南山,在绵中…在省外…有很多比泥萌厉害得多的人.他们中也有一部分很乐于与泥萌交流.要把握这样的机会,去和强者交流. 另外泥萌也要明白一点,教练不考noi.所以自己的路还得自己走.仅仅跟着教练是得不到好成绩的.个人经验,oi就是靠题目堆出来的.在不停地想题写题中找到不会的算法和数据结构,然后不断完善. 针对省选和noi做题推荐bzoj,又称lydsy.虽然分类什么的比较乱但是题目质量和数量都比较好.而且刷的人多.窝在高二省选时似乎有700道.窝认为如果泥能刷400+道非水题的话省选就能比较有底气了.至于不会的题也不一定要去硬纠结.去网上搜一搜别人博客里的题解,提高一下知识水平,再去敲敲练练代码能力也是极好的.至于哪些题可做的话可以每页按通过人数排序,或者找个前辈的记录跟着做.有些题的确是没法做的.至于bestcoder啊codeforces啊这样的在线比赛如果有时间也可以多参加一下,很能培养参加比赛的感觉.反正自己要努力就好了. 顺便提一下建议多使用linux.我指的是命令行.在bash里完成一切操作,用vim(或者emacs,nano啥的,反正我是vim党)写代码,用g++编译.虽然看上去没啥不同也许最初还会很不适应,但是这对养成好的编程习惯和未来参加noi有好处. 然后考试的时候也别太关注别人在干什么(比如窝在泥旁边打扫雷),干好自己的事就行了. 以上.总之祝你们好运. 再另外虽然窝是一只高三党,窝还是很乐于与泥萌交流的.

rausen大爷太强辣! 嗯看到这个东西,咦,直线某一边的点的权值和?kd-tree上上上. 于是就开敲kd-tree.敲到一半弃emacs换vim. 然后就wa了.然后发现double的精度太高了ovoovo 于是rausen跑得好快啊.

之前感觉是sg函数.不过不会.在wulala神犇的指点下找来题解看了一下.太神辣.自己肯定想不出来… 设以点u为根的子树的局面的sg值为sgu.设以u为根的子树中先手先hack掉v后的sg函数为gu,v. 那么gu,v = f[v] xor ∑ fu到v路径上所有点的非主干儿子. 然后fu = mex{gu,v} 这个转移得转移是O(n2)的样子吧. 然后发现某棵子树的g其实每次都是异或了一个相同的值.而且会合并. 咦可以用trie来优化一下.打下标记啥的.然后根据主席的论文这个东西是O(log n)的?虽然感觉复杂度证明没有说清楚啊ovoovo 然后就在trie树标记上卡了好久啊火冒三丈ing