【教程】为 OI 设计的自由软件 IDE CP Editor 的介绍和使用
前注 CP Editor 的介绍 ouuan 大佬在他的知乎里说得已经非常地清楚了。我的多言只会是无用地重复。所以关于 CP Editor 的文字介绍将全部来自 ouuan 大佬的知乎回答。 这篇文章的主要内容将是关于 CP Editor 使用环境的配置（C++&&Windows 1 阅读更多…
【教程】[CTF] 关于文件包含
文件包含 蒻姬我最开始接触这个 是一道 buuoj 的 web 签到题 进入靶机，查看源代码 <!DOCTYPE html> <html lang=”en”> <head> <meta charset=”UTF-8″> <meta name=”v 阅读更多…
【题解】滑动窗口 拆贡献+单调栈 -永无岛
题目 有一个数列，长度为 $n$ 。有 $q$ 个询问，每次询问所有长度为 $k$ 的区间的最大值之和。 $q\leq 1e6$ ，$n\leq 1e6$，$k\in [1,n]$ 。 题解 先拆一波贡献，把答案转化为每一个数对与每一个询问的贡献。 可以发现，一个数对一个询问有贡献 (即被当做最大值 阅读更多…
【题解】Everything on It 容斥 ARC096C —Qiuly
题意： 给你 $n$ 种酱。 你需要若干碗拉面，并且满足： 你可以在每碗拉面上放若干酱，也可以不放，容易发现方案数为 $O(2^n)$ 。 不能出现放的酱一样的两碗甚至更多拉面。 每一种酱至少在两碗拉面中加了。 求拉面集合的方案数。 考虑容斥，设 $S(i)$ 表示有 $i$ 个不合法的酱，其他的 阅读更多…
【题解】Number of Binominal Coefficients 数位 DP CF582D —Qiuly
首先你得知道什么是库默尔定理： 对于 $n\choose n+m$ 和一个质数 $p$ ，存在一个最大的 $a$ 使得 $p^a|{n\choose n+m}$ ，有 $a=f(n+m,p)$ ，其中 $f(a,b)$ 表示 $a$ 在 $b$ 进制下的进位次数。 于是可以数位 $\rm{DP}$ 阅读更多…
【题解】Campus 树状数组 CF571D —Qiuly
建两个森林，每次合并两棵树的时候新建一个点作为两棵树的根的父亲，就像 $\rm{Kruskal}$ 重构树一样。 考虑修改操作和询问操作，对于每一个询问操作维护一个 $[l,r]$ $(1\leq l\leq r\leq m)$，表示该询问操作的有效时间，也就是说 $l=1$ 或者 $l-1$ 是一 阅读更多…
【题解】Walking! 贪心, 堆 CF578E —Qiuly
题意转化过来就是，你需要将原序列拆分成尽可能少的形如 LR….RLR 或者 RL….LRL 子序列，最终的答案就是子序列数 $-1$ 。 首先令 AB 表示 A 为子序列开头，B 为子序列结尾的子序列，上面的分别是 LR 和 RL 子序列。 需要注意的是，假设只存在 LR 和 RL 子序列， 阅读更多…
【数学】傅里叶大家族 -boshi
傅里叶变换大家族 信息学中经常用到的 “快速傅里叶变换”，其实只是傅里叶大家族的冰山一角。这篇文章将带你了解真实的傅里叶变换家族。 一. 傅里叶变换 (FT) 1. 傅里叶变换的物理意义 简单来说，傅里叶变换是一个从 “时域” 到 “频域” 的变换。 什么意思呢？ 它可以将一个有关时间的函数 $f( 阅读更多…
【算法】Matrix Tree 定理证明 ——hzy
原博客链接 老久没更了，冬令营也延期了（延期后岂不是志愿者得上学了？）最近把之前欠了好久的债，诸如 FFT 和 Matrix-Tree 等的搞清楚了（啊我承认之前只会用，没有理解证明……），FFT 老多人写，而 MatrixTree 没人证我就写一下吧…… Matrix Tree 结论 Matri 阅读更多…
【算法】容错传输：Reed-Solomon 算法和 Berlekamp–Welch 算法 -boshi
容错传输 假设我们需要传输 $k$ 个数，但是传输过程可能发生错误，我们就会通过这 $k$ 个数计算出 $n$ 个 $n\geq k$ 个数字进行容错传输。由于信息量变大了，容错率也就变高了。 一种典型的容错传输算法叫做 “里德·所罗门” 算法，该算法通过传输 $n$ 个点值来传输一个 $k-1$ 阅读更多…