莫队算法是由莫涛提出的算法,可以解决一类离线区间询问问题,适用性极为广泛。同时将其加以扩展,便能轻松处理树上路径询问以及支持修改操作。 普通莫队 设定块大小 $T$,将 $m$ 个询问 $[l,r]$ 离线下来...
【LGR-071】洛谷 4 月月赛 & MdOI Round 2 Div.1 题解
【LGR-071】洛谷 4 月月赛 & MdOI Round 2 Div.1 Odyssey 首先预处理所有数的分解式,次数模上 $k$。 然后 DP,设 $f_{i,j}$ 为到点 $i$ 且上一条边的权值为 $j$ 的最短路,DAG 转移即可,有效的状态...
组合计数 学习笔记
其实不是什么学习笔记,只是稍微整理一下。 排列组合 排列 从 $n$ 个元素中有序的选择 $k$ 个元素的方案数: $$ n(n-1)(n-2)\cdots(n-k+1) = \frac{n!}{(n-k)!} = n^{\underline{k}} $$ 组合 从 $n$ 个...
Codeforces Round #631 (Div. 1) – Thanks, Denis aramis Shitov! 题解
Codeforces Round #631 (Div. 1) - Thanks, Denis aramis Shitov! Dreamoon Likes Coloring 简单构造题。 首先判无解,无解的情况只有两种,要么所有数的和加起来 $<n$,要么第 $i$ 个数大于 $n-i+1$。...
生成函数 学习笔记
生成函数即母函数,是组合数学中尤其是计数方面的一个重要理论和工具。 普通型生成函数 (OGF) 对于一个数列 $f_n$,定义它的普通型生成函数为 $F(x)$。则: $$ F(x) = \sum_{n \ge 0} f_nx^n $$ $$ f_n =...
《整型溢出》修订版修改内容
本文只记录客观上的修改内容,并不给出任何主观结论。 原版 修订版 Page 5 第 7 章的标题由各方面的敌人修改为四面楚歌。 Page 8~9 删除了一部分“杜子德”。 Page 35 涞阳八中修改为衡阳八中,涞阳...
模拟退火 学习笔记
又是个之前学过现在忘光了的算法。。。 简介 模拟退火是一种随机化算法,在优化型题目(选手得分依赖于其输出结果与最优解的比较)中非常有用,而这类题目通常为提交答案题。 使用条件 方案的数量极大甚...
JOISC 2020 题解
JOISC 2020 Day1 ビルの飾りつけ 4 (Building 4) 先考虑 $n \le 2 \times 10^3$ 怎么做。 设 $f_{i,j,0/1}$ 表示考虑前 $i$ 个数,在 $a$ 中选了 $j$ 个数,第 $i$ 个数选的是 $a/b$ 是否可行。 那么 $\...
Codeforces Global Round 7 题解
Codeforces Global Round 7 Bad Ugly Numbers 特判掉 $n=1$ 的情况,然后 $8999\cdots 9$ 就符合要求。 inline void solve() { int n; rd(n); if (n == 1) return puts("-1"), void(); pu...
动态 DP 学习笔记
动态 DP 在 NOIP2018D2T3 考察后风靡 OI 圈,然而我却一直没学。 引入 考虑这样一个问题: 给定一棵 $n$ 个点的树,点有点权 $w_i$。 有 $m$ 次操作,每次操作给定 $x,y$,表示将 $w_x$ 修改为 $y$。...