U227762 试卷排序

题目背景

期末考试临近了，yz 和 zzw 收到了来自老师的试卷关爱，但是试卷太多了，足足有 \(10^{6}\) 张，他们已经无法排好试卷了。

所以在 zzy 的建议下，他们把这个问题交给了你。

P2472 蜥蜴 - 洛谷

P2472 蜥蜴 - 洛谷

最大流 考虑将问题转化为最多有几只蜥蜴能逃离。

把柱子的点拆成入点出点两部分，它们间的连边的容量就是柱子的高度（能跳出的次数）。

柱子的出点与所有距离 d 以内的柱子的入点和场外点连容量正无穷的边。

源点和有蜥蜴的柱子的入点连容量为 1 的边，场外点和汇点连容量正无穷的边。

简介

线段树，是用来存放给定区间内对应信息的一种数据结构，是一种二叉搜索树。可用来处理数组相应的单点、区间修改操作，也可以进行区间最值、区间和等的查询。

二叉堆

介绍

二叉堆主要支持的操作有：插入一个数 \(O(\log n)\)、查询最小值 \(O(1)\)、删除最小值 \(O(\log n)\)。

二叉堆是一棵完全二叉树，其每个节点都有一个值，且每个节点的值都大于等于/小于等于其父亲的值。每个节点的值都大于等于其父亲值的堆叫做小根堆（即根最小），否则叫做大根堆。STL 中的 priority_queue 其实就是一个大根堆。

模板——图论

Floyd 算法，SPFA 算法（慎用），Dijkstra 算法，Tarjan 算法，Prim 算法，Kruskal 算法，欧拉路，Dinic（最大流/最小割）， Dinic（费用流），2-SAT，最小环。

模板——杂项

KMP，SG 函数，二进制相关，数位 DP，对抗搜索，神秘康托展开，cout 输出流控制，三分（整数三分，实数三分），upper_bound 相关，CDQ 分治，莫队，sort + unique 离散化。

模板——数据结构

ST 表，Trie 树，并查集，Bitset，线性基，链表，笛卡尔树。

模板——数学

快速幂，质数线性筛，质因数分解，欧几里得（gcd），扩展欧几里得（exgcd），求欧拉函数 \(\varphi(x)\)，欧拉定理，扩展欧拉定理，中国剩余定理（CRT），在任意模意义下的逆元，同余最短路，组合数，Lucas 定理，卡特兰数，递推求逆元，拉格朗日插值，康托展开，高斯消元，矩阵快速幂，费马平方和定理。

• https://codeforces.com/gym/104090/problem/D

找规律 经过手动模拟几轮发现，设钱数总和为 \(s\)，则第一个人分得 \(2s/(n+1)\)，其余人分得 \(s/(n+1)\)。收敛速度很快。

I. Guess Numbers

https://codeforces.com/gym/104828/problem/I

• 求：! x y \(x\) 和 \(y\) 的值。
• 问：? a b 返回 \(\gcd(x+a,y+b)\) 的值。
• 限制询问次数：\(200\)。
• \(0≤x,y<2^{60},0≤a,b<2^{61}\)。