wqs 二分 学习笔记
引言AGC018C Coins 因为不想写反悔贪心所以去学 wqs 二分。 wqs 二分 最初由王钦石在他的 2012 年国家集训队论文中提出,而从 IOI 2016 的 Aliens 题目开始,这种方法开始逐步在竞赛圈中有了一定的地位。在国内一般称为「wqs 二分」,而在国外一般称为「Alien Trick」。 算法引入 有 $n$ 个物品,物品...
Atcoder
AtCoder Regular ContestARC069D Flags | Solution 将 $n$ 个标志放在数轴上。第 $i$ 个标志可以放置在坐标 $a_i$ 或 $b_i$ 上,求出两个标志之间最小距离的最大值。 $n\le10^4$ 很显然的二分答案,成功将问题转化为在 $O(n \log n)$ 或 $O(n \sqrt{n}...
Todo list
About blogwqs 二分 AT 总结 DP 所有 AT929 序列带修问题 About problem(NOIP 真题) (wqs)P5308 [COCI2018-2019#4] Akvizna (wqs,反悔贪心)AT2672 [AGC018C] Coins About NOIp动态规划 树形,状压,数位,期望 数据结构 分块,单调栈...
动规凸包奇妙相遇夜
动规凸包一相逢,便胜却 oi 无数 CF1146H Satanic Panic 二维平面上有 $n$ 个点,找出来五个点使得形成一个五角星,求方案数。 首先五角星可以转化成 $5$ 个点的凸包,然后就可以用计算几何来求解。 怎么判断是否合法呢?可以用叉积,当然也可以通过极角排序保证合法,我用的是后者。 然后就是统计答案,这里用 DP,$f[i...
SimpleIni 使用指北
SimpleIniSimpleIni 提供用于读取和写入 INI 样式配置文件的 API。使用 MIT 许可证以开源和免费形式发布。 Offical docs Api (simple) Api Description void SetUnicode(bool a_bIsUtf8 = true); 设置数据的存储格式,参数为 true 时保...
考试题总结
数据结构树Problem给定一棵 $n$ 个点的树,每条边有个正整数边权。有 $q$ 次修改操作,每次会修改一条边的边权。 在所有修改之前以及每次修改后,你需要求出有多少个无序点对满足它们之间的最短路径上所有边权的最大公约数 $=1$。 Solution首先考虑莫比乌斯反演,变为统计 $k∣gcd$ 的点对数量。 对于每个边权,首先去掉重...
多项式学习笔记
摘要:多项式全家桶 照例先 % Dalao | Dalao 前置单位根 在复平面上画一个以 $(0,0)$ 为圆心的圆,将圆 $n$ 等分,并规定 $(1,0)$ 为第零个等分点,逆时针标号,就得到了第 $0$ 到 $n-1$ 个等分点,也就是第 $0$ 到 $n-1$ 个 $n$ 次单位根,记做 $\omega_n^0,\omega_n^1,...
数论笔记 III
摘要:莫反,贝尔数,多项式 引入求($T,n,m\le10^5$): $$\sum_{i=1}^{n}\sum_{j=1}^{m}\mathrm{Bell}_{gcd(i,j)}$$ 出处:FJOI 模拟赛 / 原题重做赛 T4 前置 多项式全家桶 P3803 【模板】多项式乘法(FFT) P4238 【模板...
ci 透彻指南
原标题:ConsolePauserPlusPlus 透彻指南 Q: 为什么叫这个名字? A: ConsolePauserPlus & ConsolePauser 这篇文章可以看作是对 solstice23 Dalao 的补充,所以又加了一个 Plus,简称 CPPP。 在 CPPP 基础上再次增加新功能,命名为 ci,精简版为 ci_m...
DP_Part II

摘要:计数 dp,数位 dp,概率与期望 dp(+有后效性 dp)