C++ 火车头

火车跑得快，全靠车头带。把以下代码放到程序开头，包括了各种 C++ 优化，可大大提高运行效率。注：千万不能在正式比赛中使用，bz 了后果自负qwq，一些 OJ 可能无法使用此优化，如：luogu。 C++ 火车头 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748#p

2022-05-17

CF1438F Olha and Igor 题解

题意有一颗深度为 $h$ 的完全二叉树，共有 $n=2^h-1$ 个节点。你可以最多询问 $n+420$ 次：询问 ? u v w 会返回在以 $u$ 为根的树内 $v,w$ 的 $\tt LCA$ 给出答案 ! r 表示你已经确定的答案。我们发现 $\tt LCA$ 有一个性质，在以 $u$ 为根的子树内，$v,w$ 的 $\tt LCA$ 为子树上为在整棵树上到 $u,v,w$

2022-05-11

CF1114E Arithmetic Progression 题解

题意链接有一个长度为 $n$ 的序列 $a$，保证它从小到大排序后是个等差数列。你不知道这个序列长什么样，但你可以询问： ? i 询问 $a_i$ 的值 > x 询问是否存在大于 $x$ 的数。最多询问 $60$ 次。求出这个等差数列的首项和公差。 $2\le n\le 10^6,0\le a_i\le 10^9$ 显然，我们可以用二分答案+操作 $2$ 询问出区间的最大值，

2022-05-11

随机 gcd 交互

CF364D Ghd 题解

题意给定 $n$ 个数，求至少取出 $\left\lceil\frac{n}{2}\right\rceil$ 个数时的 $\gcd$ 的最大值。我们假设一个数 $x$ 被选取，则 $\gcd$ 一定为 $x$ 的一个约数。我们可以算出每个约数是多少个其他数的约数，如果 $\ge\left\lceil\frac{n}{2}\right\rceil$ 即可成为答案。一个数和 $x$ 共有的

2022-05-10

Tarjan 与图的连通性

注：链式前向星从2开始编号，缩点后的新边也从2开始 tarjan 与无向图连通性 tarjan 求割边（桥） 123456789101112void tarjan(int x, int id) { dfn[x]=low[x]=++num; for (int i=head[x]; i; i=nxt[i]) { int y=ver[i]; if (!dfn[y]) {

2022-05-09

tarjan 缩点图论

CRT & EXCRT

中国剩余定理（CRT）求解同余方程组： $$ \left\{\begin{array}{l}x \equiv a_{1}\left(\bmod m_{1}\right) \\x \equiv a_{2}\left(\bmod m_{2}\right) \\x \equiv a_{3}\left(\bmod m_{3}\right) \\\cdots \\x \equiv a_{n}\left(\

2022-04-21

C++ 鼠标录制

闲着闲着没事写的 C++ 鼠标录制。按 F7 修改，依次点击需要点击的即可。按 F8 后将会自动按原来的顺序不停点击。又臭又长又废的代码： 123456789101112131415161718192021222324252627282930313233343536373839#include <bits/stdc++.h>#include <windows.h>#

2022-04-21

无向图的最小环问题

给定一个无向图，求图中至少包含 $3$ 个点的环。 Dijkstra 令 $dis(u,v)$ 表示不经过边 $(u,v)$ 时 $u$ 和 $v$ 之间的最短路，$w$ 为 $u$ 和 $v$ 之间的边长。无向图的最小环为 $\min(dis(u,v)+w)$ 有向图的最小环为 $\min(dis(v,u)+w)$ 枚举每条边，删除这条边后跑一遍 Dijkstra ，计算答案如上。时间复

2022-04-19

牛马封装矩阵

牛马封装矩阵，包含各种牛马运算，具体看下面。注：没有经过长期测试，有较大的 bz 概率 vector 存储常数较大，建议开 O2 模数可以自己修改模数在 int 范围内不用开 long long 即可使用，模数较大请自行改 long long 如有用到需要求逆的运算，若 p 不为质数会报错，使用 Miller Rabin 判断质数 1234567891011121314151617181

2022-04-13

欧拉定理 & 费马小定理

欧拉定理前置知识：欧拉函数若 $\gcd(a,n)=1$ ，则 $a^{\varphi(n)}\equiv 1\pmod n$。证明设 $n$ 的简化剩余系为 $\left \{ \overline{r_1},\overline{r_2},\overline{r_3},\cdots,\overline{r_{\varphi(n)}} \right \} $ 若 $a\cdot r_i\eq

2022-04-04