tricks oi

# 定义 单位函数$\epsilon(n)=[n=1]$ 幂函数$Id_k(n)=n^k$特别的$Id(n)=n$ 除数函数$\sigma_k(n)=\sum_{i\mid n}i^k$ 欧拉函数$\phi(n)=\sum_{i=1}^n[\gcd(i,n)=1]$ 莫比乌斯函数$\mu(n)=\b ......

## 图论 1. 有关于树/DAG 的构造等，可以考虑从叶子/入读为零的节点开始删点。 ## 树据结构 1. 有关于维护下标大小信息的合并，可以借助线段树上本身的左儿子下标小于有儿子下标简单处理。 2. 维护一个三元组 $(a,b,c)$ 的信息，看看是否能拆成 $(a,b)+c$ 的形式更易维护。 ......

记一下遇到的 `trick`。 一些来自 [xgf](https://www.cnblogs.com/xugangfan/) 大神。 1. 区间问题。 如果要求 $l\in[L,R],r\in[L,R]$ 并且答案可以预处理的话，将其抽象为二维平面。令 $(l,r)$ 表示 $[L,R]$ 的答案， ......

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

# 技巧部分 - 离线可能会使询问、操作的配置变得不那么怪异，甚至具有某种性质，类似去掉了某一维度的限制。 - ACAM 尝试在 Trie 树上或者 $fail$ 树上进行 DP。（这不是很显著吗啊喂！） - 注意到一些**上限**可以使那些看起来是暴力的做法变得优越。 - 对于连续的或运算，结果只 ......

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

1. 用可持久化线段树维护非递归线段树的树链信息可以高效地解决区间半群问题。 2. 线段树维护的序列长度要保持不变。 3. 关于 $d$（约数个数函数）：$d ( n m ) = \sum _ { x \mid n } \sum _ { y \mid m } [ \gcd ( x , y ) = 1 ......

## slope trick ### 概述 在 $dp$ 过程中，可以维护凸函数的方法，要求 $dp$ 值呈凸函数且其斜率均为整数。 具体来说，是记录凸函数斜率的变化值，即在什么位置斜率$\plusmn 1$，例如凸函数 $f(x) = |x|$，它由一条斜率为 $-1$ 和 一条斜率为 $1$ 的 ......

- [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)$。$ ......

## 一些不常见的关于哈希表的 trick ### 效率对比 一般 常见的四个 hash 表的效率比较如下: **map ``` 常用的函数有： 1. count(x) 返回指定元素的出现次数 2. size() 返回元素个数 3. empty() 返回是否为空，为空时返回 true 4. find ......

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

事先声明：本文并非线段树教学。只是一些理解Trick。若您需从0学起线段树建议您移步其他博文呢qwq 感谢 Idea 提供 [尺子姐姐的博客！](https://www.cnblogs.com/ruierqwq/)，尺子好闪，拜谢尺子！ 我们在学习线段树的时候，对于乘法“lazy tag 先乘再加” ......

# 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 ......

前言 刚发现Dedecms更新了发布版本，顺便测试一下之前的day有没有修复，突然想到了新的tricks去实现RCE。 文章发布的时候估计比较晚了，一直没时间写了。 利用 /uploads/dede/article_string_mix.php /uploads/dede/article_templ ......

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

一眼顶针，鉴定为 **implement** 不足，我写不出来。 先通过 Trick 转化 $a_i = 0 \to -1，a_i = 1 \to 1$。 那么显然把 $[l, r]$ 全部摊为 1 的贡献就是 $a_{l \to r}$。转化为 n - 最大贡献。 然后我们可以转化以下。 $$f_ ......

时常看到很多人说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 ......

# Slope Trick 学习笔记 ~~看算法名的时候还以为就是斜率优化~~ 一种维护 DP 的方法，需要满足 DP 式与斜率修改关系较大，比如：$$f_{i,j}=\min_{k<=j}(f_k)+|a_i-j|$$ 可以发现 $f_i$ 关于 $j$​ 的函数为凸函数，其斜率为正的部分显然没有 ......

# 网络流 - 最小割的可行边和必须边判定 - 可行边： - 满流。 - 在残余网络中找不到 $u\rightarrow v$ 的路径。 - 必须边： - 满流 - 残余网络中源点能到入点, 出点能到汇点。 [证明](https://www.cnblogs.com/Linnyx/p/17444810 ......

一点点显然但是会忘记的东西。 # **结论题，事实上很多时候贪心全选是对的。** ## 扫描线 **P7530 [USACO21OPEN] United Cows of Farmer John P** 没地方写导致的 $qwq$。 > 我们发现大致要写一个麻烦的偏序，但是如果我们维护一个扫描线，仅仅 ......

#### 高次整除分块 对 $\large\lfloor\frac{n}{i^2}\rfloor$ 整除分块，$\large r=\sqrt{\lfloor\frac{n}{\lfloor\frac{n}{l^2}\rfloor}\rfloor}$. 容易发现对于 $i\le n^{\frac{1} ......

本文主体译自 [Collection of little techniques](https://codeforces.com/blog/entry/100910) 并有所删改 前言略 # 1.bitset优化空间 考虑 **DAG上的可达性** ，给定一个 $n$ 个节点和 $m$ 条边的 DAG ......

# trick大意 我对于这个trick的理解为：支持位运算的高精度 维护一个以 $b$为基数的大数 $N$，并支持以下功能： - 给定（可能是负）整数 $|x|, |y| \leqslant n$，将 $x b^y$加到 $N$。 - $N \geqslant 0$时，给定$k$，打印$N$的第$ ......

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

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

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