Panda2134's Blog

Not only coding

[置顶]比赛注意事项

找最大值的时候用 $\ge$ 而非 > !尤其是要确定最大值的位置的时候!(fst*1) 交代码之前一定要检查: 文件名 部分分对应关系(包括数组!)(因为这个爆掉部分分) 内存占用(windows也可以使用MinGW中的size!)(因为这个爆0一次) 认真用 5min 读题+划重点,尤其是CodeForce...

OI日记

还有五十几天就要退役了。这几天非常低落,状态非常差。写点什么吧。 写给自己看的,懒得加密了。如果有人想看就看吧。 2018.5.20 省队训练 day3. 又一次垫底。 我不知道是哪一点没有做好。考场上一次次检查确认无误的 DP,交上去却爆零。别人第三题乱搞MST有65分,我加上了多次迭代取最优却适得其反,只有19. 似乎乱搞题从来就没有青睐过我,好像乱搞的人变成了我就总是会fs...

[雅礼集训]Tree

真神。 题意 给出一个 $n (n \le 10^5)$ 个点的带权树(边权 $w_i \le 10^6$),以及 $q(q \le 100)$ 个修改边的操作,输出每次修改边后以及所有修改之前,树上满足最短路径边权值 $\gcd$ 是 $1$ 的无序点对数。 思路 首先考察莫比乌斯函数的容斥含义。这可以由 $\gcd = 1$ 想到。如下式: 不妨先考虑不带修改的情况。 对于每...

2-SAT学习笔记

参考了这个Blog $O(nm)$ 算法 假设一个点取 0,并且顺着往下标记;如果有矛盾,假设它取 1,再标记。如果取 0 或者 1 都不行,可以证明问题无解。 代码: 用感叹号标记的行对应于输出方案。 注意从 $0$ 开始标号较为方便,此时输入编号后要减 $1$ . 点数是从句数目的两倍! bool dfs(int u) { if(vis[u]) retu...

[HNOI2007]梦幻岛宝珠

题意 01背包,但是 $c_i$ 范围很大($c_i \le 2^{30}$),且可以分解为 $c_i = p_i \cdot 2^{q_i} (p_i \le 10, q_i \le 30)$ 的形式。 思路 膜拜了 PoPoQQQ 的题解。 考虑泛化物品合并。按照 $q_i$ 不同,分为多个背包,即 $f(i, j)$ 表示背包容量为 $j \cdot 2^i$. 用对应背包装对...

数学相关

全 van 了,刚才看 anoxiacxy 大佬博客才想起来自己具体数学只看了一点点 😯 明天开始填坑,预计数论部分明天后天填完?到雅礼之后要跟上他们训练,看数学的时间就又少了……还有有限微积分,二项式系数以及特殊数列什么的……反正争取看 APIO,CTSC 后能不能弄完吧。 写 $\LaTeX$ 公式太慢了,准备写笔记本上面再扫描上来…… 先坑着。 1. 数论

Codeforces Round #475 (Div. 2)

A. Splits 考虑全部分成 $1$ 以及分成 $2, 1$ 两种情况,可以证明答案是 $n / 2 + 1$. B. Messages 并不需要DP!贪心即可! 如果 $C - B > 0$,那么把所有的信件留到最后再看,否则一收到就看。 C. Alternating Sum 分 $b / a = 1$ 和 $b / a \neq 1$ 两种情况应用等比数列求和。...

DP复习

HNOI2018 d2t3 那么水的树上DP都没看出来,让我意识到现在的DP水平可能还不如NOIP之前……去雅礼之前这个星期来复健一下…… 仔细想想,我的省选算法除了网络流和树剖、平衡树之外真的没有学的特别好的…… NOIP的时候就是DP救了我……九省联考网络流却炸了……不管怎么说先搞搞DP吧 [HNOI2018] 道路 mmp当时在考场上把问题一般化为了多元函数的最值……...

HNOI2018

不想写游记了…… day2翻盘失败 HB总共去了6个人,我第五,被第三名甩了80… 可能就认真学OI来说我起步确实挺晚的……但是不能就这么放弃啊…… 暴力写挂,数据结构被卡常成暴力分,模拟退火参数错误,这些都是缺乏比赛经验的后果啊。 dp也退步了,d2t3的dp放在考noip之前的几天绝对可以A掉的……场上却以为是数学题…… 考挂了就是自己菜,就是这样 决不...

近期计划

这周末就是HNOI2018了(虽然是划水选手),五月初就是CTSC,APIO,五月底就是PKUSC,去雅礼之前先把要学的补完,然后拯救一下DP,网络流和数学,再搞下数据结构…… 要学的东西:非旋Treap,2-SAT,后缀自动机,各种计算几何,《具体数学》,三分,树上分块,树上莫队,多项式…… 要巩固的东西:LCT与树分治,后缀数组,概率期望,网络流,莫比乌斯反演(学了跟没学一样……) ...