0%

高中打OI时代写的题解都在这里 原本在WordPress上,现在用Hexo制作为静态界面存放 可能有一些公式/图片挂了,但是也没办法修,就不修了 评论区没了,如果对内容有问题,欢迎用以下方式联系: Luogu私信: https://www.luogu.com.cn/user/52068
阅读全文 »

1. 打错freopen,不删freopen,OJ交题不删调试什么的。 2. INF = 1 << 30,memset了0x3f,最短路,导致奇怪的bug。 3. 网络流板子打错,因为网络流的玄学性,错板子过了题结果一直错着。 4. 莫队忘记给每个位置标记在哪个块就去排序…TLE。
阅读全文 »

按惯例是要发这篇文章的,还是写一下 Day1T1考场上写了个很不一样的做法,十分难以维护(在下面),冲了三个多小时只有85。T2T3两个暴力,加起来96。 查分发现T1的long long没开全,变成20了。 发现T2是傻逼题,考场看到2^m部分分太香就没多想,血亏。 Day2T1考场冲了85分(剩
阅读全文 »

周末偷偷看了看CSP T4,发现非常刺激,铁牌退役狗想了一中午(不过感觉比树上的树简单不少) 注意到本题中的蛇只需要最大化自己吃几个,不需要最大化排名。我们称拥有其它蛇梦寐以求的选择权利的蛇为后浪蛇(当前值最大),没有选择权利的蛇为打工蛇(当前值最小)。 考虑后浪蛇的策略:如果吃掉打工蛇,在游戏之后
阅读全文 »

退役前给自己看的,删了一些东西放出来了,有兴趣可以看看 Conquer the World 题意:树上匹配,权是距离 模拟费用流。 Gem Island 题意:一开始每个人都有1个绿宝石,每天选一个存在的绿宝石并分裂,求拥有前r大的人绿宝石个数期望 考虑任意一种方案被得到的概率:考虑方案数,为分
阅读全文 »

退役前给自己看的,删了一些东西放出来了,有兴趣可以看看 cf674g 考虑维护出现次数超过一半的数的方法:维护当前数,当前数出现次数,遇到一样的+1,否则-1,次数变为0的时候改数。 这种方法可以推广到更多数。考虑维护一些这样的(数,次数)对,对于新数,如果在维护的集合内出现过,直接+1,否
阅读全文 »

退役前给自己看的,删了一些东西放出来了,有兴趣可以看看 FFT,NTT全世界都会了… 分治FFT 是一类思想。举个板子: 给出了$g_{1,…,n-1}$,求$f_{0,…,n-1}$ $$f_i = \sum_{j=1}^i f_{i-j} g_j$$ 计算$f$需要用到之前的$f$。所
阅读全文 »

在做【UNR #4】校园闲逛的时候,发现可以分治FFT,就试着冲了一下。结果之后很久没写出来。orz了skyh大神的代码之后才搞出来,尝试总结一下 首先这道题怎么整:一种非正解但是能过的做法就是,考虑直接分治FFT,则$f_{x,y,i}$由$f_{x,z,j},f_{z,y,i-j}$拼出来。用分
阅读全文 »

[APIO2016]烟火表演 大约是退役前最后一篇题解,把之前的坑填上。只说一下思路,细节可以看其它题解 首先考虑一个DP:令$f_{x,i}$表示$x$点,到叶子的长度为$i$的最小代价。那么考虑合并,有$f_{x,i} = \min_{j \leq i} f_{y,j} + i-(j+c)$。
阅读全文 »

OI生涯没有WC没有APIO没有CTSC,有点伤心 Day1 路由器,DP推不出来,冬眠。下午没听懂,冬眠 Day2 没听懂,冬眠 Day3 没听懂,冬眠 Day4 没听懂,冬眠 Day5 考试,打铁了 Day6 咕咕咕 题解: 「WC2020」有根树 考场思路:考虑父亲肯定比
阅读全文 »