Panda2134's Blog

Not only coding

Codeforces Round #475 (Div. 2)

A. Splits 考虑全部分成 $1$ 以及分成 $2, 1$ 两种情况，可以证明答案是 $n / 2 + 1$. B. Messages 并不需要DP！贪心即可！如果 $C - B > 0$，那么把所有的信件留到最后再看，否则一收到就看。 C. Alternating Sum \[\begin{align*} \sum_{i=0}^n s_i a^{n-i} b^i ...

Posted by panda_2134 on April 19, 2018

DP复习

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

Posted by panda_2134 on April 16, 2018

HNOI2018

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

Posted by panda_2134 on April 15, 2018

近期计划

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

Posted by panda_2134 on April 11, 2018

[ZJOI2011]营救皮卡丘

本来以为自己对网络流理解足够深刻了，做了这个题才发现自己Too Naive……看懂题解都用了好久……明明只是套上了一个Floyd…… 明天再做一遍。题意 $k$ 个人从 $0$ 号点到 $n$ 号点，可以分头行动，但是规定：任何一人要到达 $k$ 点，必须至少有一个人到过 $k-1$ 点，求至少一个人到达 $n$ 号点时，所有人走过的路径长度和的最小值。思路看了好久题解…… ...

Posted by panda_2134 on April 10, 2018

HBOI2018游记

挺难过的…… 本来以为网络流学的很好，结果d2t1写了假的动态加边最大流，直接自爆 Day -1 晚上熬夜打模板…… Day 0 动车上想到还没写过CRT，看了半天chrt的讲解，然后赶快把《训练指南》上面的抄了一遍。然后开始颓Minecraft 由于前几天答应了教练给高一去划水的同学讲骗分，一到宾馆就开始做slide，连模板都没看。做了一会slide，就去试机。今年...

Posted by panda_2134 on April 10, 2018

[九省联考2018]一双木棋

这是一份暴力题解。 Prelude 这个题当时在考场上马上就想到了Minimax搜索，然后带上AlphaBeta剪枝就可以乱搞了，一个小时连码带对拍搞完，然后开始干后面题的暴力考试结束前5分钟我把题意看错了，慌得要命，改了之后样例输出3，交卷之前一分钟，潜意识中感到不对，连着按了30几下Ctrl-Z，撤回到了正确的版本，编译了一下，连样例都没测，就交卷了。还好rp好，没有WA声一片，...

Posted by panda_2134 on April 9, 2018

[SCOI2012]喵星球上的点名

这个题最开始只会做第一问……（其实也不完全是自己做出来的，因为是在试炼场里面看到的）后来去膜拜各路神犇的题解，想知道第二问怎么做，发现没几个看的懂的，全是什么后缀自动机/乱搞/暴力什么的……最无语的是据说 $O(nm)$ 暴力碾压正解…… 暴力碾标算，$n^2$ 过十万 2333333 直到找到了雅礼的dy神的题解，才发现一个第二问的我看的懂的做法= = 太神辣！题意...

Posted by panda_2134 on March 28, 2018

AC自动机学习笔记

第一次学是 1 月份雅礼集训的时候……不过太久没用已经忘了= = 而且当时理解也不是很到位。要省选了，得复习一下，顺便把坑填起来。约定： $\Sigma$ 表示字符集大小，$T$ 为模板集合，$S$ 为母串，我们的目标是在母串中找出模板。 Trie 就是把各个字符串相同的前缀合并形成的树。比方说 $\mathtt{[“his”, “she”, “hers”, “is”]}$ 的 ...

Posted by panda_2134 on March 28, 2018

Educational Codeforces Round

以前打的几场都没有及时补题，这几天补起来这一场期望过6题，实际过4题。还是4个暴力。主要是C题WA了好几发，细节太多了…… A - Diagonal Walking 直接贪心，正确性显然。 #include <bits/stdc++.h> using namespace std; int n; char A[200], B[200]; template<t...

Posted by panda_2134 on March 26, 2018