Panda2134's Blog

Not only coding

[ZJOI2011]营救皮卡丘

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

HBOI2018游记

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

[九省联考2018]一双木棋

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

[SCOI2012]喵星球上的点名

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

AC自动机学习笔记

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

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...

CDQ分治学习笔记

orz__stdcall 前言 昨天写一个数据结构题……大致就是给出一个排列,每次删除一个数字,求每次删除之前的逆序对数目。 不难发现,这个问题是动态的二维偏序,我们可以把它转为三维数点。不妨假设在某个二维平面中有一个坐标系,横坐标为排列中的下标,纵坐标为排列中的值,也就是排列中一个数 $a_i$ 对应坐标 $(i, a_i)$ 。先用树状数组求出初始逆序对数目,每次删点 $(x, y...

利用单调性优化动态规划

参考了这个题解,虽然有错误,但是讲的很不错。 感觉网上某些斜率优化的题解就是混的,没有严谨的证明,所以我试着证明一下= = 如果证明错了就使劲喷我好了= = 斜率优化 HDU3507 题意 把一个序列 ${c_n}$ 划分成若干份,每份的代价为 $\left( \sum c_i \right)^2 + M$. 最小化总代价和。 思路 $f(i)$ 表示前 $i$ 个的最小总代...

[NOIP2007]树网的核

BZOJ-1999 题意 给出一棵树,求一条路径使得树上点到它的距离的最大值最小。 $n \leq 300000$. 思路 好题。 很早就看到过这个题目了,除了暴力没有任何思路…… 今天学习了一下题解,发现还是很巧妙的。 Vmurder的题解 树的直径的性质 树的直径有什么性质呢?回顾一下两次 DFS 找树的直径的过程,我们可以得到以下的性质: 1. 树上的任何一个点...

[HNOI2013]游走

题意 一个无向简单连通图,边权为 $1\dots m$ 的整数。问分配边权后,从点 1 随机游走到点 $n$ 的最小期望距离。 思路 刚看完《训练指南》上面的矩阵一部分,做一做相关省选题练练手,结果第一题就不会做…… 这是最开始的错误思路: 我们对每个点显然可以列出递推式,设 $a_u$ 为点 1 走到点 $u$ 的期望距离。那么一定有: 为什么?我们考虑是从哪个点 $v_i...