oi
oi memory
CF1817C Similar Polynomials 直接带入 \[\begin{aligned} \sum_{i=0}^{d}b_ix^i&=\sum_{i=0}^{d}a_i(x+s)^{i}\\ &=\sum_{i=0}^{d}x_i\sum_{j=i}^{d}\binom{j}{i}a_j ......
在 OI 中更易上手的线性规划对偶
怎么线性规划对偶？ 我：写出约束，转为标准型，转置矩阵，对换目标与约束，整理。 zhy：直接给每一个变量设一个变元乘上去整理一下就可以了。 于是在网上查了一下资料，发现了这篇讲稿，感觉这个方式快捷多了啊，于是记了一下。 如果你看过算法导论之类的一些东西（有点记不清是不是这本书了），你发现上面讲解线性 ......
OI练习记录 - 31/12/2023
😆 比赛 Leetcode Weekly Contest 378 比赛传送门 Solved Rank Score New Rating Old Rating ∆ 2/4 5493 7 第二题用了二分来做，以为第三题也是 好像是只需检查最大的三个substring？ 【LGR-170-Div.3】洛 ......
OI 知识点小全
博弈论 基础 Bash Game Wythoff Game Nimm Game SG 函数 Alpha-Beta 剪枝 博弈树 极大极小搜索 树形图博弈 图论 最短路 SPFA 判负环 SLF 优化 LLL 优化 dijkstra 堆优化 dijkstra 线段树优化 dijkstra Floyd ......
关于 OI 学习路线
整理一下我学习 OI 的路线以及我还有什么没学。 2022.07~2022.08：简单语法，STL 的低阶应用，搜索/状压/树形/区间 dp 初探。后者掌握的极为不牢固，可以近似认为不会。 2022.09：最短路，稍微理解了一点点线段树，简单的线性 dp。 2022.10：并查集，快速幂，埃筛，CR ......
OI练习记录 - 30/12/2023
连续打了7小时[1]午餐忘了吃😭 5小时的比赛也是第一次打（虽然最后只ac了最简单的两题🛌） 今天一题非 live contest 题都没做（又偷懒了） 比赛 勤劳比赛懒惰做题 SciOI 2023 Open Contest 比赛传送门 Solved Rank Score Performance ......
OI练习记录 - 29/12/2023
zzz 习题 1917C Watering an Array 题目传送门 代码 Rating Tags 1600 brute force 这题没什么好说的，难点只在于要发现进行一次 operation 2 后最优情况是一直重复 operation 1,2,1,2... 因为把边界误判为 \(\min ......
OI练习记录 - 28/12/2023
悲报： Div 4 打寄了😭（实在太菜） 习题 189A Cut Ribbon 题目传送门 代码 Rating Tags 1300 dp 状态表示 $dp[i]$ 表示以 $i$ 为长度 ribbons 的最大数量 转移方程 $dp[i]=max(dp[i],dp[i-x]+1),x\in\{a, ......
OI练习记录 - 27/12/2023
早安 😴 昨晚比 codechef starters 太晚睡了今天没什么精神。打算写完这篇去补眠zzz 习题 dp什么都不会所以就练了一点 1472B Fair Division 题目传送门 贪心代码 dp代码 Rating Tags 800 dp, greedy 一开始想不到如何套dp进这题，就 ......
OI编程中的一些常见事项
1,浮点数 double 精度可以达到15位，只要是浮点数，直接double float 有效数字精度不够(少于6位)，编程中为了避免精度问题，建议不使用float 2，变量在main()内外的区别 堆 变量放在main(）函数外的被称为堆区，空间大，可以放更多、更大的数据，建议放在这里 栈 变量放 ......
OI 码风规范
本文介绍本人在 OI 中常用的代码规范。 概览 所有 #include 指令必须位于程序开头。 必须使用 using namespace std;。 main 函数必须位于程序末尾。 宏、常量定义 所有宏位于 using namespace std; 后，而常量位于所有宏后。 宏、常量定义不能缩进。 ......
在OI类竞赛中经常使用的C++STL模板类
vector 变长数组 vector的初始化 vector<int> a; // 定义一个空的vector，且元素类型为int vector<int> a(n); // 定义一个长度为n，元素类型为int的vector，且每个元素都是0 vector<int> a(n, x); // 定义一个长度为 ......
[填写 5 题]OI 反诈中心
seq https://www.cnblogs.com/HLAUV/p/9871768.html 诈骗，区间长度大于 P 时必为 0。 发现 MP^2 以下的都可以接受，直接 PlogP 地塞入 std::set 中查前驱即可。 另一个抽屉原理 https://www.luogu.com.cn/pr ......
2023.11.25 日记 OI·与否
我揉了揉疲劳的脖子。 白天是照常的模拟赛，题目简单但我的分数并不如意。 晚上回来做 AtCoder abc。打得也不好，C 题太着急了，思路乱了十几分钟。 F 题现在还没调过。赛前定了切 G 的目标，但好像实力未到。全榜居然只有 3 个人切。 我大概已经有了一个较为放松的 OI 心态了。 我深知自己 ......
OI 生涯记录
OI 生涯记录 初识编程 由于我很早接触到了电脑的原因，我从小对软件产生了浓厚的兴趣，幻想着自己能发明一款软件或者是游戏给别人玩，于是我便有了学习变成的想法。可惜的是，虽然我有想法，但是并没有老师指导，我只能通过网上的一些说法开始自学，听网上说 C# 开发非常方便，于是我便在 b 站开始寻找教程，b ......
OI_problem 玛丽卡_洛谷P1186
题意 一个 \(N\) 个点 \(M\) 条边的带边权无向图，要求输出最小的 \(V\) 使得不管去掉哪一条边，都存在从 \(1\) 到 \(n\) 的路径使得边权和不超过 \(V\) 。 思路 感觉朴素不太好做，考虑二分。 对于一个二分值，即要判断在关于这个值的生成图中， \(1\) 和 \(n\ ......
OI 生涯回忆
你说过的我都不曾忘记 轻飘飘的旧时光 就这么溜走 转头回去看看时 已匆匆数年 或许明日太阳西下倦鸟已归时 你将已经踏上旧时的归途 我没啥天赋，也不够努力。论 OI 生涯取得的成绩，我是失败的。 但是我确实从信息学竞赛里学到了很多普通文化课学不到的东西。 我确实认识了很多外校的，外省的人们。如果不是 ......
OI 生涯回忆录
目录\(\operatorname{OI}\) 生涯回忆录Part Ⅰ 2018Part Ⅱ 2019 上半Part Ⅲ 2019 下半Part Ⅳ 2020 上半Part Ⅴ 2020 下半Part Ⅵ 2021Part Ⅶ 2022 下半Part Ⅷ 2023下半 \(\operatorname ......
OI 回忆录
可能退役了吧。怕 NOIP 测完后太垃圾没心情写于是就先写了。 或许是持续更新的（？ 我是在小学六年级的时候知道了信息学这个东西，不过当时只道这是写写代码之类的东西，也没有开始学。六年级下学期的时候我妈给我报了一个学习 Scratch 的课程，因为当时我爸我妈都不知道原来正统的编程是 C++，只不过 ......
2023 NOIP 游记 & OI 生涯总结
-1.序言 观前提示： 本文大部分篇幅在作者情绪较激动时写成，所以可能会出现一些言语偏激。 长长长文警告。 文中大部分人名会用 X老师 或者英文缩写代替。 作者语文水平不高，所以应该写不出太好的鲜花，这篇文章仅代表我对自己一些经历的总结和看法。 不好取题目所以不取了。 0 我的破木箱 装满枯萎的花 ......
OI 生涯的最后一周
……：在卷文化课，这么卷。你自测四科多少。 我：语文英语还没写。数学 140，物理 90 多吧。 ……：这么强。 ……：doqe 凭这两科都进创了，你文化课这么强，还学这彩票竞赛干嘛。 ……：要不要挑战中科大。 我：（查询后）我这一年的中科大少年班在去年就截止报名了。等少创班。 NOIP2023，差 ......
OI回忆录+退役记
2023年11月17日 明天就是NOIP了，打算打完NOIP就退役，于是在这里写一篇回忆录。 我初中的时候根本不知道有信息竞赛这个东西，甚至对其它的竞赛也不了解，唯一的印象只是竞赛题很难，参加竞赛的人很强，仅此而已。 那时候高一军训之后因为疫情就开始上网课，也是在上课后的没几天，我的班主任在班级群里 ......
OI 中的一些技巧
前言：可能写的很乱，博客中的问题请尽管指出，后面会整理。 参考博客： 比赛进行的时候你应该干什么？ 命令行 命令行可以简单理解成不带图形化需要输指令的工具。 Windows 中有 cmd（和更加强大的 PowerShell），Linux 中有 bash。 由于 OI 中命令行的使用大同小异就一块讲了 ......
#18搞OI不要会证明
Karen and Cards 题面 设符合条件的三元组为 \((x,y,z)\)。枚举 \(x\)，可以将 \(n\) 个三元组分为两类：\(a_i\ge x\) 和 \(a_i<x\)。对于 \(i\in [1,n],a_i\ge x\)，需要满足的条件为 \(b_i<y\) 且 \(c_i<z ......
离散最大似然法与 OI
若总体属于离散型，其分布律在参数 \(\theta\) 作用下 \(P\{X=x\}=p(x;\theta),\Theta=\{\theta\}\) 的形式已知，设 \(X_1,X_2,\dots,x_n\) 是 \(X\) 的样本，则其联合分布律为： \[\prod_{i=1}^np(x_i;\t ......
OI 中的贪心
贪心模型总结 区间最大不相交覆盖/会议安排问题 Statement 有 \(n\) 场会议要使用会议室，第 \(i\) 场会议室的开始和结束时间点为 \(l_i\) 和 \(r_i\)，不同会议时间不能重叠。求最多能安排的会议场数。 Solution 考虑将会议按 \(r_i\) 升序排序。 每次枚 ......
【重学OI】图论大礼包
继上次数学大礼包之后，再度推出图论 出于一定的功利性以及必要，我们部分基本用不到的算法不会提到 本篇没说题号默认就是洛谷有模板题 本文尽可能略去证明，目的就是复习 对于图的储存，我们不讲，代码里一般是用链式前向星(不会bilibili搜索不分解的AgOh) part0 概念 图：一张图 \(G\) ......
OI 中的一些优雅（或不优雅）写法
求 max/min // 当无特殊需求时 inline void Max(int &x, int y) { x = max(x, y); } inline void Min(int &x, int y) { x = min(x, y); } // 若有时需要 long long template<c ......
重学OI #3 DS特别篇
这一篇和前两篇目的不太一样，这里更加偏向于一些好玩的神奇科技 part1 K-D tree 众所周知ben喜欢分块，但是分块不能(难以)处理多维问题 ben不喜欢树套树，但是树套树可以 所以ben决定学 KDT从而减少学树套树( kdt最大的优势在于对脑子需求小，只需要你能码 首先我们考虑kdt是什 ......