抱歉,您的浏览器无法访问本站

本页面需要浏览器支持(启用)JavaScript


了解详情 >

YangTY's Blog

王侯将相宁有种乎

2021年10月 OI学习记录

private

推荐阅读

主要是学习路途中阅读到的他人撰写的宝藏博客。 大佬们的博文 分治/二分/倍增等基础算法 wqs 二分 洛谷日报 by 小跳蛙 cdq 分治 by __stdcall DP O(NW) 的树形背包 by Planet6174 斜率优化 by 辰星凌 [OI笔记]数位DP合集 & 对数位DP的一点理解 by s_r_f 树上问题 dfs...

本站导航

前言 你好,陌生人,这里是 YangTY。详细资料可以看关于页面。 该页面将列出一些比较值得看的文章(雾)。可能会出现写作时间跨度过大以至码风不一样的情况,但不影响阅读。 学习笔记 如果发现有什么错误,欢迎在 QQ 上爆 D 我/kk。 数据结构 平衡树笔记:写了三种主流平衡树的写法以及详细实现。 莫队:咕咕咕。 分块:更新了 LOJ 分块 1-9 题之后就烂尾了,待修。 树上问题杂记:点...

P4284 [SHOI2014]概率充电器

Description 一棵树,节点为电子元件,边为导线。每个电子元件有 p_i 的概率自己被充电,每个导线有 q_i 的概率连通。一个元件被充电当且仅当自己被充电或者通过相邻的导线充电。求期望充电的元件个数。 要求 O(n) 。 Solution 相当于求所有元件被充电的概率之和。可惜不能高斯消元,考虑 dp...
OIsol

几种 IO 方式效率的实验

前言 CSP 前颓废的成果。本文的目的在于测试出各 IO 方式的效率并进行粗略的比对并选择使用。 控制变量似乎不是很严谨( 但是能得出大概的结论( 如果发现有写的不对的地方欢迎直接在评论区 D 我( 或者加我 QQ 也🉑以。😘 输入效率测试 目前我们考虑读入 10^7 个正整数。 目前大家熟知的读入方式有下面若干种:C 库的 scanf() 函数,std::...
OInotes

P3305 [SDOI2013]费用流

Description 给定一张网络,Alice 先选择一种最大流方案,Bob 给每条边定单位费用,要求每条边单位费用之和为 P 。 Alice 希望费用最小,Bob 希望费用最大。Bob 在定费用的时候已经知道 Alice 的方案。 如果两人都足够聪明,求网络的最大流和费用。 Solution 我们知道,如果 Bob 已经知道了流的方案,有个很显然的贪心就是他肯定会往流量最...
OIsol

P6810 「MCOI-02」Convex Hull 凸包

Description 给定 1\le n, m\le 2\times 10^6 , 1\le p\le 10^9 ,求 \sum_{i = 1}^n\sum_{j = 1}^m\tau(i)\tau(j)\tau(\gcd(i, j)) ...
OIsol

P5495 Dirichlet 前缀和

Description 给定 \{a_n\} ,求 \{b_n\} 满足 b_i = \sum_{k\mid i}a_k\bmod 2^{32} 输出 \bigoplus_{i = 1}^nb...
OIsol

计算几何全家桶

前言 最近模拟赛好像比较爱考😢有点虚。毕竟在 NOI 大纲上的等级比较低。 计算几何还是比较烦的一个东西。如果以后打 ICPC 的话还是需要会点的。 先考虑二维计算几何。三维是甚么毒瘤东西 基本定义 一些约定 类型名和宏 12345678#define FOR(i, a, b) for (int i = (a); i <= (b); ++i)#define DEC(i, a, b) ...
OInotes

OI 中的 STL 食用指南

前言 坑。 鉴于在各种题目中,STL 的应用十分广泛,故在此总结 STL 的用法。 基本概念 容器:一些封装数据结构的模板类,例如 vector 等。 迭代器:访问容器内元素的“中介”,和指针很类似。 algorithm 库 排序函数 二分查找 next_permutation std::upper_bound() std::vector STL 集合容器 std::set
OInotes

莫队小记

莫队简介 一种将询问离线下来,调整回答询问的次序以降低复杂度的算法。 普通版本一般只能处理序列上的不带修查询问题。 有树上莫队,回滚莫队,带修莫队,莫队二次离线等变种。
OInotes

LOJ#2874. 「JOISC 2014 Day1」历史研究

Description 定义一段区间的加权众数为一个数字乘上其出现次数的最大值。 10^5 次询问区间加权众数。 Solution 莫队可以做区间众数我们是知道的。 但是这个题的众数带权,莫队的删除操作非常不好实现。这个时候就需要一个叫回滚莫队的科技,使得我们没有删除操作: 将每个询问按以左端点所在块为第一关键字,右端点所在块为第二关键字排序。 按顺序处理询问...
OIsol

P3175 [HAOI2015]按位或

Description 一开始有数字 0 ,每秒随机选一个 [0, 2^n - 1] 的数字然后按位或上去,选择 i 的概率为 p_i ,问期望多少秒后变成 2^n - 1 。 Solution 拆开每一位。设 x_k ...
OIsol

1 / 18




Blog content follows the [Attribution-NonCommercial-ShareAlike 4.0 International (CC BY-NC-SA 4.0) License](https://creativecommons.org/licenses/by-nc-sa/4.0/deed.en)
本站总访问量为 访客数为
Use Volantis as theme