文章

传送门酱：「AHOI2014」支线剧情 题意：给你一张有向图，每次从 $1$号节点开始走，可以在任意节点停止。每走一次的费用是路径上所有边的边权和，求所有边都至少走过一次后的最小花费。 刚开始想这道题的时候坚定地认为这是 NP-Hard, 大概是看算导看蠢了 QAQ 其实如果知道一个东西叫做有上下界 阅读更多…

Flight Safety (BZOJ1020) 题意 世界上有很多岛屿，可以看成是 C 个边形 ($C\leq20$，每个点数 M 不超过 30，可以非凸)。一架飞机沿一条 N 点折线飞行 ($N\leq20$)，求航线上一个点，最大化其到最近岛屿的距离。给出的所有点都是 $[-1000,1000 阅读更多…

1. 题目 BZOJ 传送门=￣ω￣= LuoGu 传送门=￣ω￣= 2. 题解 做了好久呀 QvQ 所以记录一下 考虑不带修改点权的树链第 K 大问题： 首先建主席树（权值线段树），其中 root[i] 以 root[fa[i]] 为基础上加入点 i 的点权，这样 root[i] 所代表的权值线段树表示 阅读更多…

1. 题目 传送门 2. 题解 连着做两道这种等比数列字符串哈希的题了。。。 感觉有点玄学。 哈希方法简单讲下吧，就是如果原字符串是 $str[1,len]$ 那么它的哈希值就是 $\sum _ {i=1}^{len} 233^i \times str[i]$（这里面的 $233$可以改，最好大于 阅读更多…

传送门：序列求和 $1$ 求：$\sum_{i = 1}^n i ^ k\quad(1 <= N <= 10^{18}, 1 <= K <= 2000)$ 我才不会告诉你们那天晚上我去学伯努利数的时候弃坑了 感觉伯努利数的写法构造性太强了 $QwQ$而且似乎也只能写自然数幂和 阅读更多…

1. 题目 传送门=￣ω￣= 题目是少见的良心中文题面，就不写大意了。 2. 题解 母函数模板题耶 QvQ 设 $a_i$表示价值为 $i$的单词的个数。 构造母函数： $$G(x)=a_1x+a_2x^2+a_3x^3+…$$ 对于价值为 $i$个字符，设它有 $p$个，则对于它来说母 阅读更多…

快速沃尔什变换 ($Fast Walsh-Hadamard Transform$, 简称 $FWT$)，是一种可以加速集合卷积的算法 会 $FFT$的同学肯定知道，$FFT$加速多项式乘法实际上就是加速了一个卷积。在 $FFT$里，卷积的形式是长这个样子的： $$C(k)=\sum_{i+j=k}A 阅读更多…

题意： 给定一个”A-structure” 的定义： If V=(A,B,C,D) and E=(AB,BC,CD,DA,AC), we call G as an “A-structure”. 求图 G 中有多少个”A-structure& 阅读更多…

这里是可爱的传送门酱~：[APIO2011] 方格染色 题意： 给一个 $n \times m$的表格图，你可以给它的每一个格子涂红色或者蓝色，且每一个 $2 \times 2$的子表格图内必须有奇数个红色格子，现在有人已经涂了一部分格子了，求你完成这个表格图的方案数。 这道题好可怕呀刚开始想的时候 阅读更多…

1. 编译时加入-fsanitize=address，可以检测程序运行时是否访问了非法内存地址。 比如编译后运行如下代码段： #include<bits/stdc++.h> int a[10]; int main(){ a[10]=1; return 0; } 终端中将会显示出一大段内容 阅读更多…