Q779’s Blog

特征方程 学习笔记 特征方程的原理貌似是线性代数的东西。 但是如果只是使用的话，不需要了解这么多。 特征方程可以用于快速求解一些递推式的通项 一阶线性递推式 设数列 \(\{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

洛谷P2508 [HAOI2008]圆上的整点 题解 题目链接：P2508 [HAOI2008]圆上的整点 题意： 求一个给定的圆 \((x^2+y^2=r^2)\) ，在圆周上有多少个点的坐标是整数。 输入格式： 一个正整数 \(r\) 。 输出格式： 整点个数。 数据范围： \(1\le r\leq 2\times 10^9\) 关键词：高斯素数、复平面、费马平方和定理、乘法原理 圆心为原点，半径为 \(r\) 的圆周上有多少个整点？ 实际上我们可以把这个问题转化为以下的形式 存在多少个整数对 \((a,b)\) 满足 \(a^2 + b^2 = N\) ，其中 \(N \in \mathbb{Z}^+\) 。 对于这样的二元问题，我们可以将二维平面看作复平面。 首先我们要知道这么几个前置知识。 1.高斯整数： 高斯整数是实部和虚部都为整数的复数。（只要知道这个就行了） 所有的高斯整数组成了一个整环，写作 \(\mathbb{Z}[i]\) 。 \[ \mathbb{Z}[i] = \{a+bi \mid a,b \in \mathbb{Z}\} \] 高斯整数组成了...

洛谷P4253 [SCOI2015]小凸玩密室 题解 题目链接：P4253 [SCOI2015]小凸玩密室 题意： 小凸和小方相约玩密室逃脱。 这个密室是一棵有 \(n\) 个节点的完全二叉树，每个节点有一个灯泡，点亮所有灯泡即可逃出密室。 每个灯泡有个权值 \(a_i\)，每条边也有个权值 \(b_i\)。 点亮第一个灯泡不需要花费，之后每点亮一个新的灯泡 \(v\) 的花费，等于上一个被点亮的灯泡 \(u\) 到这个点 \(v\) 的距离 \(D_{u,v}\)，乘以这个点的权值 \(a_v\) 。 在点灯的过程中，要保证任意时刻所有被点亮的灯泡必须连通，在点亮一个灯泡后必须先点亮其子树所有灯泡才能点亮其他灯泡。 请告诉他们，逃出密室的最少花费是多少。 输入格式： 第 \(1\) 行包含 \(1\) 个数 \(n\)，代表节点的个数 第 \(2\) 行包含 \(n\) 个数，代表每个节点的权值 \(a_i\)。 \((i = 1, 2,\)……\(, n)\) 第 \(3\) 行包含 \(n - 1\) 个数，代表每条边的权值 \(b_i\)，第 \(i\) 号边是由第 \...

洛谷P3915 树的分解 题解 题目链接：P3915 树的分解 题意： 给出 \(N\) 个点的树和 \(K\)，问能否把树划分成 \(\frac{N}{K}\) 个连通块，且每个连通块的点数都是 \(K\)。 输入格式： 第一行，一个整数 \(T\)，表示数据组数。接下来 \(T\) 组数据，对于每组数据： 第一行，两个整数 \(N, K\)。 接下来 \(N - 1\) 行，每行两个整数 \(A_i, B_i\)，表示边 \((A_i, B_i)\)。点用 \(1, 2, \ldots, N\) 编号。 输出格式： 对于每组数据，输出 YES 或 NO。 数据范围： 对于 \(100 \%\) 的数据，\(1 \le T \le 10\)，\(1 \le N ,K \le 10^5\)。 贪心好题。 首先 \(n \bmod k \ne 0\) 肯定无解。 考虑从下往上依次考虑每个点 如果它的 \(\mathtt{sz}_u = k\) 那就把它的砍掉，并令 \(\mathtt{sz}_u \gets 0\) 在有解的情况下，这么做一定可以分出来。 如果某个 \(\mat...

洛谷P2949 [USACO09OPEN]Work Scheduling G 题解 题目链接：P2949 [USACO09OPEN]Work Scheduling G 题意： 约翰有太多的工作要做。 为了让农场高效运转，他必须靠他的工作赚钱，每项工作花一个单位时间。 他的工作日从 \(0\) 时刻开始，有 \(10^9\) 个单位时间。 在任一时刻，他都可以选择编号 \(1\) 到 \(N\) 的 \(N(1 \leq N \leq 10^5)\) 项工作中的任意一项工作来完成。 因为他在每个单位时间里只能做一个工作，而每项工作又有一个截止日期，所以他很难有时间完成所有 \(N\) 个工作，虽然还是有可能。 对于第 \(i\) 个工作，有一个截止时间 \(D_i(1 \leq D_i \leq 10^9)\)，如果他可以完成这个工作，那么他可以获利 \(P_i( 1\leq P_i\leq 10^9 )\) 。 在给定的工作利润和截止时间下，约翰能够获得的利润最大为多少。 反悔型贪心经典题。 先把所有的工作按时间限制顺序排序。 然后我们从前往后扫一遍，遇到能做的工作就把它吃了...