Q779’s Blog

洛谷P2630 图像变换 题解 题目链接：P2630 图像变换 题意： 给定 \(3\) 行 \(3\) 列的图像各像素点灰度值，给定最终图像，求最短、字典序最小的操作序列。 其中，可能的操作及对应字符有如下四种： A：顺时针旋转 \(90\) 度； B：逆时针旋转 \(90\) 度； C：左右翻转； D：上下翻转。 输入格式： 一个矩阵，表示初始的图像。 一个矩阵，表示最终的图像。 输出格式： 最短、字典序最小的操作序列，保证长度不超过 \(10^8\)，不保证有解。 若长度不超过 \(10^8\) 无解则输出 Poland cannot into space!!! 。 这种题目就是一眼暴搜。但是仔细观察可以发现有些操作其实是重复的 实际上一共只有 \(8\) 种情况，否则无解 A 顺时针转 90° B 逆时针转 90° C 左右翻转 D 上下翻转 = 左右翻转 + 转 180° AA 转 180° AB 不动 AC 左右翻转 + 顺时针转 90° BC 左右翻转 + 逆时针转 180° 显然我一开始没发现这样的性质。 但是至少可以发现两次 C 和两次 D 是浪费...

CF421D Bug in Code 题解 题目链接：CF421D Bug in Code 题意： 最近，在 “低聚果糖” 代码公司发现了一个严重的 bug！“低聚果糖” 公司的负责人 cxy 想找到罪魁祸首并惩罚他。为了这个，她组合了一场会议，主题是：谁写出了 bug？会议上一共有 \(n\) 个程序员，其中每个人都说：“我知道，一定是 \(x\) 或 \(y\) 之一！” cxy 决定选择两名嫌疑人并请到他的办公室。自然地，她需要考虑这 \(n\) 个人的观点。她想要选择这样两个人 \(u, v\)，满足 \(n\) 个人的至少 \(p\) 个人同意。一个人同意指的是，他认为 (是嫌犯) 的两个人中，至少有一个是 \(u\) 或 \(v\)。cxy 想知道，一共有多少种方案选择两名嫌疑人？ 输入格式： 第一行包含两个非负整数 \(n, p~(3 \leq n \leq 3 \times 10^5, 0 \leq p \leq n)\) ，表示 “低聚果糖” 公司中程序员的数量和需要同意的人的最小数目。 接下来的 \(n\) 行，每行包含两个整数 \(x_i, y_i~(1 ...

note[3] 例1：五个本质不同的点在没有重边或者自环的情况下，组成不同的无向图的个数是？ 解： 首先 \(5\) 个点有 \(\mathrm{C}_5^2 = 10\) 条边 每条边显然可以连也可以不连 则总方案数为 \(2^{10} = 1024\) 。 例2： 同时扔出 \(k\) 枚完全相同的六面骰子，每个骰子上有 \(1\) 到 \(6\) 的数字 将得到的点数排序后，有多少种不同的结果？ 解： \(6\) 个元素选 \(k\) 个，可以重复。显然可重组合。 \[ \mathrm{C}_{6+k-1}^{k} \]

CF1728C Digital Logarithm 题解 题目链接：CF1728C Digital Logarithm 题意： 我们定义 \(f(x)\) 表示取出 \(x\) 在十进制下的位数。( 如 \(f(114514) = 6, \; f(998244353) = 9\) )。形式化讲，就是 \(f(x) = \lfloor \log_{10} x \rfloor\) 给定两个数组 \(a\) 和 \(b\)，求执行若干次以下操作后使得 \(a\) 和 \(b\) 排序后相等的最小操作次数。 操作方法如下： 选择一个下标 \(i\)，将 \(a_i\) 赋值为 \(f(a_i)\) 或者将 \(b_i\) 赋值为 \(f(b_i)\)。 输入格式： 第一行一个整数 \(T \; (1 \le T \le 10^4)\) 表示测试样例组数。 对于每组测试样例，第一行为一个整数 \(n \; (1 \le n \le 2 \cdot 10^5)\) 表示数组长度。 接下来的两行分别有 \(n\) 个整数，表示数组 \(a\) 和 \(b \; (1 \le a_i,b_...

洛谷P1196 [NOI2002] 银河英雄传说 题解 题目链接：P1196 [NOI2002] 银河英雄传说 题意： 一共有 \(n=30000\) 个人，给定 \(Q ~(1\le Q \le 5\times 10^5)\) 次操作 M i j 表示将 \(i\) 所在队伍拼接到 \(j\) 所在队伍队尾。 C i j 表示询问 \(i,j\) 在队伍中相差多少个人（ \(i,j\) 不算在内） 如果他们不在一个队伍中，请输出 \(-1\) 。 带权并查集模板题，欠了快大半年才去研究 说实话，以前怎么看都看不懂，现在看就很显然，不知道为什么。 第一个操作显然是可以用并查集维护的（难不成你用左偏树？） 考虑如何维护第二个操作。注意到并查集其实维护了一个森林。 而带权并查集，实际上就是把普通并查集维护的森林带上了边权。 我们记录两个数组 \(d_i\) 和 \(s_i\) （代码里是 d[] 和 sz[]） \(d_i\) 表示当前结点到根的距离 \(s_i\) 表示它所在的树的结点个数 void init(int n) { for(int i=1;...

洛谷P2515 [HAOI2010]软件安装 题解 题目链接：P2515 [HAOI2010]软件安装 题意： 现在我们的手头有 \(N\) 个软件，对于一个软件 \(i\) ，它要占用 \(W_i\) 的磁盘空间，它的价值为 \(V_i\) 。我们希望从中选择一些软件安装到一台磁盘容量为 \(M\) 计算机上，使得这些软件的价值尽可能大（即 \(V_i\) 的和最大）。 但是现在有个问题：软件之间存在依赖关系，即软件i只有在安装了软件 \(j\) （包括软件 \(j\) 的直接或间接依赖）的情况下才能正确工作（软件 \(i\) 依赖软件 \(j\) )。幸运的是，一个软件最多依赖另外一个软件。如果一个软件不能正常工作，那么它能够发挥的作用为 \(0\) 。 我们现在知道了软件之间的依赖关系：软件 \(i\) 依赖软件 \(D_i\) 。现在请你设计出一种方案，安装价值尽量大的软件。一个软件只能被安装一次，如果一个软件没有依赖则\(D_i=0\)，这时只要这个软件安装了，它就能正常工作。 输入格式： 第1行：\(N,M(0\leq N\leq 100, 0\leq M\leq ...

UOJ246 【UER #7】套路 题解 题目链接：#246. 【UER #7】套路 题意： 反攻正在进行中，按照套路，跳蚤国将会很快获得最终的胜利。跳蚤国的情报局也没闲下来，他们正打算派遣一批 “菲克蚤” 前往跳晚国窃取有关三星 note7 的资料。 cxy 是这批 “菲克蚤” 的教练，他教会他们各种 Fake 的技术，以便更好混入敌方内部。共 \(n\) 只菲克蚤，由 \(1\) 到 \(n\) 编号。cxy 给每个菲克蚤都算了特征值 \(a_1, \dots, a_n\)，两个菲克蚤的相似度定义成这两个菲克蚤的特征值的差的绝对值，即第 \(i\) 只菲克蚤与第 \(j\) 只菲克蚤的相似度为 \(\lvert a_i - a_j \rvert\)。 现在这批菲克蚤排成一列在 cxy 面前，cxy 需要在其中选出一些菲克蚤合成一个行动小队。按照套路，他会选取连续一整段的菲克蚤 \(a_l, a_{l + 1}, \dots, a_r\)。很显然，这个行动小队越大越好，但是按照套路，小队内的跳蚤最好都各不相同，假如有两只跳蚤长得很像的话很可能会引起跳晚们的怀疑。为此 cxy ...

洛谷P1963 [NOI2009] 变换序列 题解 题目链接：P1963 [NOI2009] 变换序列 题意： 对于 \(N\) 个整数 \(0, 1, \cdots, N-1\) ，一个变换序列 \(T\) 为这 \(N\) 个整数的一个置换。 定义 \(x\) 和 \(y\) 之间的距离（\(x,y = 0,1,\cdots,n-1\)） \[ D(x,y)=\min\{|x-y|,N-|x-y|\} \] 给定每个 \(i\) 和 \(T_i\) 之间的距离 \(D(i,T_i)\) 你需要求出一个满足要求的且字典序最小的变换序列 \(T\) 。 说明：对于两个变换序列 \(S\) 和 \(T\) ，如果存在 \(p<N\) ，满足对于\(i=0,1,\cdots,p-1\)， \(S_i=T_i\) 且 \(S_p<T_p\) ，我们称 \(S\) 比 \(T\) 字典序小。 原题真的废话连篇还特别丑，已经删减过了。 输入格式： 第一行包含一个整数 \(N\) ，表示序列的长度。接下来的一行包含 \(N\) 个整数 \(D_i\) ，其中 \(D_i\) 表...

洛谷P2272 [ZJOI2007]最大半连通子图 题解 题目链接：P2272 [ZJOI2007]最大半连通子图 题意： 一个有向图 \(G=\left(V,E\right)\) 称为半连通的，如果满足：\(\forall u,v\in V\)，满足 \(u\to v\) 或 \(v\to u\)，即对于图中任意两点 \(u,v\)，存在一条 \(u\) 到 \(v\) 的有向路径或者从 \(v\) 到 \(u\) 的有向路径。 若 \(G'=\left(V',E'\right)\) 满足 \(V'\subseteq V\)，\(E'\) 是 \(E\) 中所有跟 \(V'\) 有关的边，则称 \(G'\) 是 \(G\) 的一个导出子图。若 \(G'\) 是 \(G\) 的导出子图，且 \(G'\) 半连通，则称 \(G'\) 为 \(G\) 的半连通子图。若 \(G'\) 是 \(G\) 所有半连通子图中包含节点数最多的，则称 \(G'\) 是 \(G\) 的最大半连通子图。 ...

洛谷P4981 父子 题解 题目链接：P4981 父子 题意： 对于全国各大大学的男生寝室，总是有各种混乱的父子关系。 那么假设现在我们一个男生寝室有不同的 \(n\) 个人，每个人都至多有一个“爸爸”，可以有多个“儿子”，且有且只有一个人没有“爸爸”(毕竟是室长，还是要给点面子，当然了，室长人人当嘛)。 那么现在问题来了，对于一个有 \(n\) 个人的寝室，最多可能存在多少种父子关系，当然每个人之间都必须要有直接或间接的父子关系。 输入格式： 第一行一个 正整数 \(t\)，表示有组数据。 接下来 \(t\) 行，每行一个整数 \(n\)，表示有 \(n\) 个人。 输出格式： 共 \(t\) 行，每行一个整数，求关系个数。 由于答案可能较大，则我们需要输出答案对 \(10^9+9\) 取模的值。 数据范围： 对于 \(100\%\) 的数据，\(t≤10^4\)，\(n≤10^9\)。 \(n\) 个不同结点的有根树数量 显然等于「 \(n\) 个不同结点的无根树的数量」 乘以 \(n\) 根据 Cayley 公式，前者就是 \(n^{n-2}\) （不知道戳这里） \[...

洛谷P2532 [AHOI2012]树屋阶梯 题解 题目链接：P2532 [AHOI2012]树屋阶梯 题意： 有点搞笑的是，我刚刚写的 浅谈卡特兰数 （Catalan数） 恰好提到了这个。 所以它就是卡特兰数。当然观察样例手推也可以发现，1,1,2,5,14嘛。 当然这个题也是有理论依据的。 考虑证明它是一个 Catalan number。先去搬几张图（逃 设 \(f_i\) 表示 \(i\) 层高的阶梯的方案数，边界：\(f_0=1,f_1=1\) 考虑 \(n=5\) 的情况，下图中红色的部分表示我们将要填充的块 可以发现它的方案数为 \(f_0 \times f_{4}\) 。 考虑填充第二块 可以发现它的方案数为 \(f_1 \times f_3\) 。 还没看出来吗？那再来一个。 可以发现它的方案数为 \(f_2 \times f_2\) 。 根据卡特兰数的某常用公式，不难发现这是卡特兰数（？ \[ C_n =\sum_{i=1}^{n}C_{i-1}C_{n-i} \] 只不过这里换成了 \(f\) 。然后我们就做完这题了 代码：（又是高精度。。） n...

浅谈卡特兰数 （Catalan数） 卡特兰数的定义 卡特兰数是组合数学中一个常在各种计数问题中出现的数列。 卡特兰数的一般项公式为 \[ C_n = \frac{1}{n+1} \dbinom{2n}{n} = \frac{(2n)!}{n!(n+1)!}\quad (n\in \mathbb{N}) \tag{1} \] 还有以下常见公式 \((n \in \mathbb{N})\) \[ C_0=1,~C_1=1\\ C_n = \sum_{i=1}^{n} C_{i-1}C_{n-i},\quad n \ge 2\tag{2} \] \[ C_n = \frac{(4n-2)C_{n-1}}{n+1} \tag{3} \] \[ C_n = \dbinom{2n}{n}-\dbinom{2n}{n-1} \tag{4} \] OEIS A000108 这张表很重要。因为有时候想不出来可以手推前几项猜卡特兰数。 \(n\) 0 1 2 3 4 5 6 \(\cdots\) \(C_n\) 1 1 2 5 14 42 132 \(\cdots\) 我们可以用...