menu ZigZagK的博客
account_circle

正在努力加载中QAQ

[插头DP]HHHOJ167【俄罗斯方块】题解
解题报告肯定是插头DP,不过如果把每个俄罗斯方块考虑过去,会累死的……这时候我们就要利用俄罗斯方块的性质:所有大小为 $4​$ 的连通块都是一个俄罗斯方块!所以根本就不用管俄罗斯方块,只需要考虑...
apps HHHOJ
local_offer 查看标签
comment 0 条评论
阅读全文
[凸包]HHHOJ166【蚂蚁】题解
解题报告可能是沙雕题,但是我又做不来又写不来QAQ。只要求出所有直线的凸包(分界点),就可以分类讨论树上倍增搞了。注意分界点相同标号的大小问题,处理不好就会GG。示例程序#include<...
apps HHHOJ
local_offer 查看标签
comment 0 条评论
阅读全文
[树状数组套线段树]HHHOJ165【归并排序】题解
解题报告这题好像挺水的……手玩下会发现如果两个相邻元素没有正确排序,那么他们就会在最终序列里并起来。比如:4 1 3 2 -> (4 1) (3 2) -> (3 2) (4 1) ...
apps HHHOJ
local_offer 查看标签
comment 0 条评论
阅读全文
[期望的线性性+概率DP]HHHOJ164【排列统计】题解
解题报告其实不用管期望……只要算出总贡献然后最后除以 $(n^2)^k​$ 就行了(Manchery:期望就是层壳),不过也可以利用期望的线性性把期望转成概率。算贡献的时候如果真的按照题目中给的...
apps HHHOJ
local_offer 查看标签
comment 0 条评论
阅读全文
[组合+容斥]PE595【Incremental Random Sort】题解
解题报告抄题解时间到,令 $f(i)$ 表示长度为 $i$ 的答案,则可以得出这样的方程:$$ f(1)=0,f(i)=\sum_{j=2}^{i}[f(j)+1]\cdot g(i,j)\\ ...
apps HHHOJ
local_offer 查看标签
comment 0 条评论
阅读全文
[记忆化搜索]NOIP2017Day1【逛公园】题解
解题报告吃我一记万年神坑。考场上我想到了 $f_{i,j}$ 表示到 $i$ 点比最短路多 $j$ 的方案数,但是我不会转移,写了玄学转移骗了60。不会转移?记忆化搜索大法吼啊,令 $dis_i...
apps HHHOJ
local_offer 查看标签
comment 0 条评论
阅读全文
[状压DP]NOIP2017Day2【宝藏】题解
解题报告吃我一记万年神坑。去年考场上做这题的时候一直在想二进制状压,现在回头看看那时候的自己真是蠢爆了。很明显可以三进制状压 $f_{i,s}$ 表示深度为 $i$ 时,每个点的状态 $0/1/...
apps HHHOJ
local_offer 查看标签
comment 0 条评论
阅读全文
[思维]liu_runda NOIP模拟题【斯诺】题解
解题报告补集转化,则统计有数超过区间一半的区间的个数,由于是超过区间一半所以只会是 $012$ 中的一个。分开统计 $012$ ,考虑前缀和,其实就是个逆序对问题,由于 $n=5\times10...
apps HHHOJ
local_offer 查看标签
comment 0 条评论
阅读全文
[树形DP]liu_runda NOIP模拟题【蚊子】题解
解题报告这题在现在看来好像不是很难啊……把每对蚊子分开考虑,那么就是考虑每个节点作为LCA时的贡献,而每个节点作为LCA时又可以拆成两半处理,这样问题就简化得比较好处理了。一个叶子到达某个祖先没...
apps HHHOJ
local_offer 查看标签
comment 0 条评论
阅读全文
[原根+循环矩阵快速幂]liu_runda NOIP模拟题【随】题解
解题报告先来介绍一波原根:如果 $\forall i\not=j,g^i\not\equiv g^j\ (mod\ P)$ ,那么 $g$ 是 $P$ 的一个原根,如果 $P$ 是素数那么一定有...
apps HHHOJ
local_offer 查看标签
comment 0 条评论
阅读全文
keyboard_arrow_up