Q779’s Blog

本文统计截止于 2022年09月28日 ，有空再来统计这个。 其实还有很多模板或者 Trick 在洛谷没有被标出来。 难度 通过数/总数 完成度 普及- 7/7 100% 并查集 ok 堆 ok 快速幂 ok 最小生成树 ok 线性筛 ok 快速排序 ok 字符串哈希 ok 普及/提高- 16/16 100% 树状数组 1 ok 乘法逆元 ok LCA ok 线段树1 ok 树状数组 2 ok KMP ok 负环 ok ST 表 ok 矩阵加速（数列） ok 单调栈 ok 单源最短路 1 ok 单源最短路 2 ok 裴蜀定理 ok 字典树 ok 普及+/提高 13/16 81.25% 有理数取余 ok 边双连 欧拉路径 ok 威佐夫博弈 nim 游戏 缩点 ok 线段树 2 ok 全源最短路 ok 割点 ok 二分图最大匹配 ok exgcd ok 最长公共子序列 ok 边双连 提高+/省选- 24/34 70.58% 普通平衡树 1 ok 左偏树 ok 最小费用最大流 ok ...

洛谷P6134 [JSOI2015]最小表示 题解 题目链接：P6134 [JSOI2015]最小表示 题意： 对于一个 \(N\) 个点（每个点从 \(1\) 到 \(N\) 编号），\(M\) 条边的有向图，cxy 发现，如果从图中删去一些边，那么原图的连通性会发生改变；而也有一些边，删去之后图的连通性并不会发生改变。 cxy 想知道，如果想要使得原图任意两点的连通性保持不变，我们最多能删掉多少条边呢？ 为了简化一下大家的工作量，这次 cxy 保证他给定的有向图一定是一个有向无环图（cxy：大家都知道对于给任意有向图的问题，最后都能转化为有向无环图上的问题，所以就干脆简化一下大家的工作）。 输入格式： 第一行包含两个正整数 \(N\) 和 \(M\)。 接下来 \(M\) 行，每行包含两个 \(1\) 到 \(N\) 之间的正整数 \(x_i\) 和 \(y_i\)，表示图中存在一条从 \(x_i\) 到 \(y_i\) 的有向边。 输入数据保证，任意两点间只会有至多一条边存在。 输出格式： 输出一行包含一个整数，表示cxy最多可以删掉的边数。 数据范围： 对于 \(100...

UOJ176 新年的繁荣 题解 题目链接：#176. 新年的繁荣 题意： 在这新年的第一天，神族首领 cxy 打算重新规划一下神族领地的交通。 神族领地中有 \(n\) 个城市，其中第 \(i\) 座城市的繁荣度为 \(a_i\)。神族领地中任意两个城市之间都可以修建双向道路，在第 \(i\) 座城市和第 \(j\) 座城市之间修建道路可以给新的一年带来 \(a_i \mathbin{\mathrm{and}} a_j\) 的繁荣度。其中 \(\mathbin{\mathrm{and}}\) 表示按位与运算，例如 \(2 \mathbin{\mathrm{and}} 3=2\)，\(1 \mathbin{\mathrm{and}} 0=0\)，\(1 \mathbin{\mathrm{and}} 1=1\)。 为了彰显自己的功绩，神族首领 cxy 决定修建若干条道路，使得任意两个城市之间都可以只通过他新修建的道路直接或者间接到达，为了发扬节约精神，他决定修建恰好 \(n-1\) 条道路。一个修建方案的繁荣度是所有要修建的道路带来的繁荣程度之和。 作为一个英明的首领， cxy 决...

泰勒级数&麦克劳林级数 在数学上，对于一个在实数或复数 \(a\) 邻域上，以实数或复数作为变量的函数， 并且是无穷可微的函数 \(f(x)\) ，它的泰勒级数是以下这种形式的幂级数： \[ \sum_{n=0}^{\infty}\dfrac{f^{(n)}(a)}{n!}(x-a)^n \] 当 \(a=0\) 时，可以称这个级数为麦克劳林级数。即 \[ \sum_{n=0}^{\infty}\dfrac{f^{(n)}(0)}{n!}x^n \] 对于 \(e^x,\sin x\) 这种函数，如果我们想求它的较精确近似值，可以考虑麦克劳林级数。 常用麦克劳林级数 当变量 \(x\) 是复数时，这些等式依然成立。 几何级数： \(\forall x : |x| < 1\) \[ \dfrac{1}{1-x} = \sum_{n=0}^{\infty} x^n = 1+x+x^2 + \cdots + x^n + \cdots \] 拓展： \(\forall x : |x| < 1,~ k \in \mathbb{Z}^{+}\) \[ \dfrac{1}{...

特征方程 学习笔记 特征方程的原理貌似是线性代数的东西。 但是如果只是使用的话，不需要了解这么多。 特征方程可以用于快速求解一些递推式的通项 一阶线性递推式 设数列 \(\{a_n\}\) 满足 \[ a_1 = b \\ a_{n} = ca_{n-1} + d,~n>1 \] 其中 \(c \ne 0 \land c\ne 1\) ，求这个数列的通项公式。 定义 \(x=cx+d\) 为原递推式的特征方程。 设上述特征方程的根为 \(x_0\) ，则 当 \(x_0 = a_1\) 时，\(\{a_n\}\) 为常数列，即 \(a_n=a_1\) 。 当 \(x_0 \ne a_1\) 时， \[ a_n = (a_1-x_0) \cdot c^{n-1} + x_0 \] 例： 已知数列 \(\{a_n\}\) 满足 \[ a_1 = 4 \\ a_n = -\dfrac{1}{3} a_{n-1} - 2,~n>1 \] 求 \(a_n\) 的通项。 解：特征方程为 \(x +\dfrac{1}{3}x + 2=0\) ，解得 \(x_0 = -\df...

UOJ174 新年的破栈 题解 题目链接：#174. 新年的破栈 题意： 在这新年的第一天，神族首领 cxy 自然是要接受来自宇宙各国的朝贡的。在种类繁多的礼品中， q779 送来的栈引起了她的注意——她发现这个栈的大小正好适合来装她的核弹。 神族首领 cxy 有 \(n\) 个核弹，编号为 \(i\) 的核弹的威力是 \(A_i\)，而且任意两颗核弹的威力都是不同的。现在她想用这个栈来整理这些核弹，每时每刻她可以进行下面三种操作中的一种： 入栈：如果当前还有核弹没有被放入过栈中，那么就把剩下的核弹中编号最小的放到栈中（作为新的栈顶）。 出栈：如果当前栈中有核弹，那么就把栈顶（即栈中最后被放入的）的核弹取出来。 打开阀门：如果当前栈中有核弹，那么就把栈底（即栈中最先被放入的）的核弹取出来。 在所有核弹都从栈中取出后， cxy 按照核弹出栈的时间顺序排成一排，再把这些核弹的威力记录下来，这样就得到了一个数列 \(B\)。现在 cxy 想让这个数列的字典序尽可能的小，但是因为她日理万机，没有时间来想这种简单的小问题，于是她就让你来帮她求出字典序最小的数列 \(B\)。 对于两个...

UOJ233 【IOI2015】Sorting 题解 题目链接：#233. 【IOI2015】Sorting 题意： Aizhan 有一个由 \(N\) 个互不相同的整数组成的序列 \(S[0], S[1], \ldots, S[N - 1]\)，其中 \(S[i]\) 取值范围是 \([0, N - 1]\)。Aizhan 试图通过交换某些元素对的方法将这个序列按照升序排序。Aizhan 的朋友 Ermek 也想交换某些元素对，Ermek 的交换未必有助于 Aizhan 的排序。 Ermek 和 Aizhan 打算通过若干轮次来修改这个序列。在每一轮，Ermek 首先做一次交换，然后 Aizhan 做另一次交换。更确切地说，做交换的人选择两个有效的下标并交换这两个下标的元素。请注意这两个下标可能相同。如果它们相等，则对这个元素自身做交换，并不改变这个序列。 Aizhan 知道 Ermek 并不关心对序列 \(S\) 排序的事情。Aizhan 还知道 Ermek 将会选择哪些下标。Ermek 打算参加 \(M\) 轮交换，将这些轮次从 \(0\) 到 \(M - 1\) 编号。...

UOJ279 【UTR #2】题目交流通道 题解 题目链接：#279. 【UTR #2】题目交流通道 题意： 定好了难度，雄心勃勃的 cxy 开始寻找智慧的神犇星球的居民出题。 然而 cxy 没有料到，神犇星球的居民告诉 cxy ：“今年神犇星球经济不景气，大家都想宅在家里，哪有心思出来出题呢？” 为了挽救这一局面， cxy 决定为神犇星球建一些高速传送通道促进该星球各地区之间交流题目。 神犇星球有 \(n\) 座小城。对于任意两座小城 \(v, u\)（\(v \neq u\)）， cxy 想在 \(v, u\) 之间建立一个传送时间为 \(w(v, u)\) 的无向传送通道，其中 \(w(v, u)\) 为不超过 \(k\) 的非负整数。建成后，神犇星球的居民可从一座小城出发经过一个或若干个传送通道到达另一座小城交流题目，花费的时间为所有经过的传送通道的传送时间之和。 cxy 还没有决定每一个传送通道的传送时间取值，只是对于任意两座小城 \(v, u\)，决定了从 \(v\) 出发到达 \(u\) 的最短时间要恰好等于 \(d(v, u)\)。但 cxy 日理万机，于是他找...

复数及其几何意义 施工中，咕咕咕。。。 复数的定义： \[ \mathbb{C} = \{a+bi \mid a,b \in \mathbb{R} \} \] 其中 \(i\) 为虚数单位，满足 \(i^2 = -1\) 。

洛谷P2056 [ZJOI2007] 捉迷藏 题解 题目链接：P2056 [ZJOI2007] 捉迷藏 题意： cxy 和 q779 是一对好基友，并且他们有很多狗子。某天，cxy、q779 和狗子们决定在家里玩捉迷藏游戏。他们的家很大且构造很奇特，由 \(N\) 个屋子和 \(N-1\) 条双向走廊组成，这 \(N-1\) 条走廊的分布使得任意两个屋子都互相可达。 游戏是这样进行的，狗子们负责躲藏，cxy 负责找，而 q779 负责操纵这 \(N\) 个屋子的灯。在起初的时候，所有的灯都没有被打开。每一次，狗子们只会躲藏在没有开灯的房间中，但是为了增加刺激性，狗子们会要求打开某个房间的电灯或者关闭某个房间的电灯。为了评估某一次游戏的复杂性，cxy 希望知道可能的最远的两个狗子的距离（即最远的两个关灯房间的距离）。 我们将以如下形式定义每一种操作： C i 改变第 \(i\) 个房间的照明状态，若原来打开，则关闭；若原来关闭，则打开。 G 开始一次游戏，查询最远的两个关灯房间的距离。 输入格式： 第一行包含一个整数 \(N\)，表示房间的个数，房间将被编号为 \(1,2,3...

note[6] 例：求以下错误的二分代码的平均时间复杂度。 来源 \(1 \le s \le n \le 10^4\) 。 #include<bits/stdc++.h> using namespace std; int l=1,r=10000,mid; int main() { int n; cin>>n; r=n; int s,cnt=0; cin>>s; while(l<=r) { ++cnt; mid=(l+r)/2; if(mid==s) break; else if(mid>s) r=mid-1; else ++l; // here is wrong } printf("%d\n",cnt); return 0; } 解： 首先不难发现最坏有 \(T(n) = O(n)\) 考虑正常的分析。 \[ \begin{aligned} T(n) &= \frac{1}{2}T\le...

OI总结 本系列属于早期文章，有待进一步完善。 【OI数学总结】 系列 【数学】标签涵盖的有亿点多（（ Parts 包含内容 OI数学总结-基础公式&结论 就是一些基础公式，可能比较杂乱 OI数学总结-数论 积性函数、完全积性函数、最大公约数 gcd、裴蜀定理、扩展欧几里德算法(Exgcd)、费马小定理、逆元、欧拉函数、欧拉定理、扩展欧拉定理、Lucas定理、中国剩余定理、扩展中国剩余定理、莫比乌斯函数、莫比乌斯反演、拉格朗日定理、原根、二次剩余 OI数学总结-组合数学 排列组合、容斥原理、鸽巢原理（抽屉原理）、第二类斯特林数、伯努利数、贝尔数（Bell数） OI数学总结-群论 群的基本概念、群的主要类别、Burnside 引理 OI数学总结-博弈论 博弈论基础 OI数学总结-其他 「施工中。。」 【OI易错点】 系列 还在咕咕咕，因为当时没怎么好好整理。 目前只有一篇 OI易错点-C++语法 【DP总结】 系列 还在咕咕咕，因为整理的比较散乱而且其实基本没有整理 目前只有一篇 DP总结-状压dp