oi

2023牛客OI赛前集训营-提高组（第二场）B.出租 B-出租_2023牛客OI赛前集训营-提高组（第二场） (nowcoder.com) 目录2023牛客OI赛前集训营-提高组（第二场）B.出租题目大意思路 题目大意 在一条路上有 \(n\) 个栋楼，每栋楼上有 \(k\) 个房间出租。 现在有 ......

2023牛客OI赛前集训营-提高组（第三场）C.分糖果 目录2023牛客OI赛前集训营-提高组（第三场）C.分糖果题目大意做法对于 \(30pts\)对于 \(20pts\)对于 \(100pts\) C-分糖果_2023牛客OI赛前集训营-提高组（第三场） (nowcoder.com) 题目大意 ......

观前须知:本文顺序较为混乱，根据本人复习顺序写的，难度严格不递增 dp不像数据结构可以套路性的将，以例题为主吧 part 1:树形dp 树是一种非常好的结构，其天然的递归形态保证了最优子结构，使得dp有很好的发挥空间 一般状态与子树和路径有关，也有时扯到叶子节点，所以不套路化，特殊情况可能会一大把 ......

这里希望通过一个小系列(即重学OI)复习学过的一些重要内容 本系列偏向速通式的快速复习或学前预习，不会有大量例题，重在知识点复习，目的在最短的时间内掌握尽可能多的不会的东西 因此更偏向文字解释而不是图解，需要一定想象力 这是 第一集 数据结构基础篇，本篇与提高篇和特别篇交错更新 本集简介:(单调)栈 ......

1.考试的时候先考虑dp和线段树 2.记得检查数组空间 3.考虑尽量卡常 4.尽量考虑退式子 5.看到关于01爆搜选择的一定要先考虑01背包，不要直接写爆搜 6.清楚要不要文件读写和子文件夹 7.树上边权转点权转移到儿子节点，但是特别注意多余信息处理（尤其是树剖的时候） 比如树剖结束的时候处理最后一 ......

第一章 定义超几何函数 \[F(a_1,a_2\dots a_n;b_1,b_2\dots b_m;z)=\sum_{k\ge 0}\frac{a_1^{\overline{k}}\dots a_n^{\overline {k}}z^k}{b_1^{\overline k}\dots b_n^{\o ......

记录一些见到的感觉很有用的 tricks。 平均值 对于和的平均值（形式化地，\(\bar a = \dfrac{\sum_{i = 1} ^ n a_i}{n}\)），可以转化成 \(a_i - \bar a\) 然后和 \(0\) 乱搞。 异或哈希 就是 xor hash，可以在 CF 上找到详 ......

记录一些见到的感觉很有用的 tricks。 平均值 对于和的平均值（形式化地，\(\bar a = \dfrac{\sum_{i = 1} ^ n a_i}{n}\)），可以转化成 \(a_i - \bar a\) 然后和 \(0\) 乱搞。 异或哈希 就是 xor hash，可以在 CF 上找到详 ......

前言 2023.09.14：转眼间已经快大三开学了，突然翻到了这篇写的半半拉拉的回忆录。快速地扫了一遍后，发现这里面写的很多细节现在已经不记得了……为了防止记忆再一次退化把那些片段全部抹去，我决定还是把剩下的一部分补完。如果有人愿意看的话，我甚至还可以再补个爽文大结局（现在的我确实是当时的我能想象的 ......

Bindian Signalizing 题面 断环为链，令 \(l_i\) 表示 \(i\) 左边第一个高于 \(i\) 的，\(r_i\) 表示 \(i\) 右边第一个高于 \(i\) 的，\(cnt_i\) 表示区间 \([l_i,r_i]\) 中高度等于 \(i\) 的，因为为了防重，所以只记 ......

# [Mahjong](https://www.luogu.com.cn/problem/AT_arc160_d) > 找到可以通过以下两种操作，使得长度为 $N$、元素之和为 $M$ 的数列 $A$ 全为 $0$ 的 $A$ 的个数，再取模 $998244353$。 > 1. 在 $A$ 中选一个 ......

这段配置基本通用 但是需要vim支持clipboard才能复制到系统剪切板 下面是配置正文 .vimrc ``` let mapleader = "\" vnoremap y "+y inoremap jk nnoremap e :w:!g++ % -o % nnoremap e :w:!g++ % ......

- [CSP-J 2020 游记](https://www.cnblogs.com/GaodeSean/articles/17654415.html) - [CSP-S 2021 游记](https://www.cnblogs.com/GaodeSean/articles/17654417.html ......

# B > 给定一棵树。多次询问 $l_1,r_1,l_2,r_2$ 求 $\operatorname{lca}([l_1,r_1],[l_2,r_2])=\bigoplus\limits_{u\in[l_1,r_1],v\in[l_2,r_2]}\operatorname{lca}(u,v)$。$ ......

## 0822 复赛模拟 今天题挺符合胃口，打得挺舒服 ### T1 > [洛谷 P8295](https://www.luogu.com.cn/problem/P8395) ~~一眼爆搜~~ 其实是道数学题，可以观察余数来写下代码，运用到的无非就是用 $4 \times 5$ 转 $5 \time ......

# 8.18 ### T1 推式题．推式能力不强，消耗了大量时间． 由期望的线性，可以对每个位置分开计算贡献． 每个位置的地位对等． 对于每个位置，考虑进行 $m$ 次操作后仍在该位置的信封仍在原位置的概率．考虑递推 $F_i$ 表示 $i$ 操作后仍在原位置的概率． $$ F_i=(\frac{n ......

## 0821 复赛模拟 ### T1 > [洛谷 P7398](https://www.luogu.com.cn/problem/P7398) 裸的模拟，对得丑陋 ```cpp #include using namespace std; const int N = 1e4 + 50; int an ......

#### t1 火柴 设计 $f[i]$ 为 $i$ 跟火柴最多的长度，$g[i]$ 为 $i$ 根火柴应选哪个放在首位。 考虑到前一位的重要性吊打后一位，显然让 $f[i]$ 尽量大优先，不然就是 $g[i]$ 取大。考虑记忆化搜索（DP）即可。 ```cpp #include #define i ......

时常看到很多人说OI最简单，或者OI对升学没有什么用，也有些人说近些年的OI 出的很好，体现了思维性和竞赛的意义。有些人说竞赛就是为了选拔人才，不需要选那么多。起初我还会反驳，见的多了，也就懒得了。 我觉得，OI（信息学竞赛）的目的就是为了让更多的人接触更深刻更前沿的计算机科学，就是做一个普及，或者 ......

##背包DP [背包DP](https://oi-wiki.org/dp/knapsack/) ##区间DP [区间DP](https://oi-wiki.org/dp/interval/) ##DAG上的DP [DAG上的DP](https://oi-wiki.org/dp/dag/) ##树形D ......

# 动态规划的形式理论 动态规划是一类特殊的组合最优化问题的求解方式。 组合最优化问题是在给定有限集合的所有具某些特性的子集簇中，寻找使某种指标达到最优的子集的问题。也即，给定一个基础集合 $P$，在 $P$ 的所有子集（记作 $2^P$，由于可以决定每个元素选或不选）的某个子集 $S \subse ......

留给后人了属于是。 来讲一讲如何速通 OI 吧。 ### 最优原地 OI 速通方法（AFO） 原地退役。 耗时：$\epsilon$。 能够总结出来的好用的速通方法也就是上面那个了。 不同人之间的思维方式差异较大，所以能够总结出来一个普适性的方法也是很不容易了。。。 本来闲话里也有提到，有意向写一写 ......

1. 可持久化线段树 query 的时候两结点的 sz 相减的时候一定是左儿子相减； 2. 可持久化线段树建新点要将原来的不更改的节点连接上； 3. 动态规划也可以倒着考虑； 4. P3957的单调队列是先加入后删除，否则加入的也不一定满足条件； 5. `-Wl,--stack=536870912` ......

7月30日。【我与oi的故事】 其实这个故事并没有结束，因为我至少目前还不会退役。 但是命运又将驶向何方呢？或许11月就退役了吧。 淼哥离开的时候可以昂着头说：“我的故事是一个充满勇气和坚持的故事。” 但是我做不到。 我的故事充满了欺骗，颓废，自卑与苦涩。 尽管如此，我想我的经历应当还是独一无二的。 ......

此处存放本喵写过的各种 cpp 模板一共不时之需，不喜勿喷~ 基本算法 for (int i = 1; i <= n; i ++) { cin >> arr[i]; sum[i] = sum[i - 1] + arr[i]; } 前缀和 for (int i = 1; i <= n; i ++) { ......

## P1525 关押罪犯 题意翻译：给定一张图，将图中结点分为两个互补的集合，求集合间边权最小值 知识点：并查集 做法：对权值排序，尽量分成两个不同的集合（如果一方无敌人，则另一方成为其敌人；否则将另一方丢到另一监狱里面），出现矛盾时的权值即为答案 ## P2024 食物链 知识点：并查集 做法： ......

# 前言 合并操作一直是 OI 中一大考点，今天请各位跟着笔者来梳理一下各种合并操作。 # 启发式合并 几乎可以说是最经典的合并了。 假定我们可以在 $O(k)$ 的时间内往某个集合中插入一个数，那么我们就可以在 $O(n \log n k)$ 的时间内合并若干个**元素总量为 $n$ 的集合。** ......

本来吧，像我这种水平的选手退役，是没有资格写游记的。但是奈何感慨颇多，只得愤愤写下。 小时候就对计算机编程之类的东西感兴趣，家里却也就报了点兴趣班，基本都是小一群孩子在玩。小时候成绩是不好的，也可以说是比较差的，家里自然没有考虑让我学习OI或者MO，当然他们也不知道这些东西。到了初一的时候，学校和外 ......

# 零、写在前面 `癸卯年七月中，Z老师讲解调试技。愿今年，RP人和，百事聚兴，乃重写终端篇，增其旧志，刻OI巨佬技巧于其上，属予作文以记之` （若无特殊说明，默认在 $\texttt{Linux}$ 下操作） # 壹、终端便利篇 ## 一、目录表示 1. `./` 本级目录 2. `../` 上级 ......

模运算 ```cpp //加法 x=(a+b)%p; x=(0ll+a+b+c)%p; x=((a+b)%p+c)%p; //减法 x=((a-b)%p+p)%p; //乘法 x=1ll*a*b%p; x=1ll*a*b%p*c%p; ``` 高精度： 正数的高精度读入，输出，储存，和 $+,-,\ ......