ZigZagK的博客
[哈夫曼树]BZOJ4198(Noi2015)【荷马史诗】题解
题目概述有 $n$ 个单词,要给每个单词对应一个 $k$ 进制数,使得所有单词变为 $k$ 进制数之后接起来长度最小,并且满足在长度最小的前提下最长 $k$ 进制数最短,且 $k$ 进制之间不能...
[思维+DP]AtCoder Grand Contest 022E【Median Replace】题解
题目概述有一个长度为奇数的 $01$ 串(有些位待定),每次可以把相邻三个合并成 $01$ 中数量多的,求最终能够变成 $1$ 的方案数。解题报告题解好像是大力分类,不过我们可以膜LPA2002...
[思维]HDU4473【Exam】题解
题目概述令 $f(x)=\sum_{a=1}^{+\infty}\sum_{b=1}^{+\infty}[ab|x]$ ,求 $\sum_{i=1}^{n}f(i)$ 。解题报告emm……其实就...
[分块+虚树]Codeforces966E【May Holidays】题解
题目概述有一棵树,每个节点有一个权值 $t_i$ 。现在有 $m$ 次操作,每次操作表示一个节点被删除了或被重新添加了,每次操作后统计子树中被删除节点 $>t_i$ 且没被删除的节点的个数...
[贪心+后缀自动机+线段树合并]Codeforces700E【Cool Slogans】题解
题目概述给定一个字符串 $S$ ,要求构造字符串序列 $s_1, s_2, \ldots, s_k$ ,满足任意 $s_i$ 都是 $S$ 的子串,且任意 $i \in$ $[2, n]$ ,都...
[莫队+阈值优化+哈夫曼树]Codeforces700D【Huffman Coding on Segment】题解
题目概述给出 $n$ 个数和 $m$ 个询问,每次询问给 $[L,R]$ 中的数进行哈夫曼编码得到的长度总和。解题报告挺强的题,给 $[L,R]$ 中的数进行哈夫曼编码,数据结构肯定搞不了,所以...
[边双连通分量]Codeforces700C【Break Up】题解
题目概述给出一张带边权无向图,现在要砍掉最多两条边,使得 $s$ 到 $t$ 不连通,求最小边权。解题报告其实就是考虑 $s$ 和 $t$ 所在的边双连通分量,但是不能 $O(m^2)$ 枚举这...
[思维]Codeforces700B【Connecting Universities】题解
题目概述一棵 $n$ 个点的树,给出 $2k$ 个关键点,现在要把这 $2k$ 个点组成 $k$ 对,每对的贡献为点之间的距离,求最大贡献。解题报告完全想不到……考虑每条边的贡献,很明显最大是第...
[树形DP]liu_runda NOIP模拟题【蚊子】题解
解题报告这题在现在看来好像不是很难啊……把每对蚊子分开考虑,那么就是考虑每个节点作为LCA时的贡献,而每个节点作为LCA时又可以拆成两半处理,这样问题就简化得比较好处理了。一个叶子到达某个祖先没...
[思维+线性基]BZOJ2115(Wc2011)【Xor】题解
题目概述给出一张有边权的无向图,求从 $1$ 到 $n$ 路径异或最大值,可以重复走点并且可以重复经过 $n$ 。解题报告好妙的题!无向图中的环是可以经过也可以不经过的,所以我们可以把所有环加入...