【教程】[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( 阅读更多…
【算法】容错传输：Reed-Solomon 算法和 Berlekamp–Welch 算法 -boshi
容错传输 假设我们需要传输 $k$ 个数，但是传输过程可能发生错误，我们就会通过这 $k$ 个数计算出 $n$ 个 $n\geq k$ 个数字进行容错传输。由于信息量变大了，容错率也就变高了。 一种典型的容错传输算法叫做 “里德·所罗门” 算法，该算法通过传输 $n$ 个点值来传输一个 $k-1$ 阅读更多…
【题解】Trinity NTT,DP AGC021F
考虑设 $f(i,j)$ 表示 $i$ 行每行都有至少一格黑色的大小为 $i\times j$ 的表格的方案数。 最终的答案就是 $\sum {n\choose i}f(i,m)$ 。 考虑如何转移，每一次加入一列，并且加入若干行，最终的行数分成小于等于 $i$ 和大于 $i$ 两种。 考虑小于等于 阅读更多…
【题解】[NOI2019] 序列 主席树+二分+单调栈 Loj3158 —Qiuly
可以猜测，对于最优的 $\rm{B}$ 中的区间 $[L,R]$ 满足该区间内所有数相等，那么如果这个数为 $x$ ，则 $A_L$ 到 $A_R$ 的平均数为 $x$ ，显然这个猜测成立。 然后还有一个显然的结论：区间 $[L,R]$ 的长度越小越好，这也是显然的。 我们考虑没有修改的情况，用单调 阅读更多…