Q779’s Blog

CF708E Student’s Camp 题解 题目链接：CF708E Student’s Camp 题意： 有一个 \((n+2) \times m\) 的网格。 给定 \(n,m,a,b,k\) ，记 \(p=\frac{a}{b}\) 除了第 \(0\) 行和第 \(n+1\) 行，其他每一行 白天最左边的格子有 \(p\) 的概率被吹走。 夜晚最右边的格子有 \(p\) 的概率被吹走。 如果网格（包括第 \(0\) 行和第 \(n+1\) 行）被分成了两个及以上连通分量，则称网格不连通。 求 \(k\) 天后，网格始终保持连通的概率。 \(n,m \le 1.5 \times 10^3,~k \le 10^5,~a < b \le 10^9\)，答案对 \(10^9+7\) 取模。 特别🐮🍺的一道题，考虑概率dp。 下文中出现的奇怪变量名（因为参考自 link），先给出对应的代码形式 $_i$ pl[i] ，\(\mathtt{pr}_i \to\) pr[i] \(F_{i,j} \to\) F[i][j] ， \(\mathtt{sl}_{i,j...

CF178F3 Representative Sampling 题解 题目链接：CF178F3 Representative Sampling 题意： 有 \(n\) 个字符串 \(a_i\) ，从中选取 \(k\) 个，使它们两两之间的 \(\text{LCP}\)（最长公共前缀）之和最大。输出这个最大值。 \(k\le n\le 2000,|a_i|\le 500\) 看到最长公共前缀我还愣了一下，这不裸的 \(\tt{trie}\) 树吗，然后想了半天不会。。 考虑建 \(\tt{trie}\) 树然后在上面做树上背包 注意这里背包能选的“物品”只有 \(\tt{trie}\) 树上「是字符串结尾的结点」 方便起见，称「是字符串结尾的结点」为「串结点」 两两串结点的贡献，也就是他们的最长公共前缀（LCP）长度，其实就是他们的LCA深度。 记 \(i\) 的子结点 \(c_1,c_2,\cdots,c_{\lambda_i}\) ，设 \(f_{c_k,j}\) 表示以 \(i\) 为根的子树中，只考虑 \(c_1,c_2,\cdots,c_k\) ，选 \(j\) 个串...

BZOJ2141 排队 题解 题目链接：#2141. 排队 题意： 一句话题意： 给定 \(n\) 个数，\(Q\) 次询问，每次交换两个不同位置的数，然后输出逆序对数。 \(1 \le n \le 2\times 10^4,~1\le Q \le 2 \times 10^3\) 排排坐，吃果果，生果甜嗦嗦，大家笑呵呵。你一个，我一个，大的分给你，小的留给我，吃完果果唱支歌，大家乐和和。红星幼儿园的小朋友们排起了长长地队伍，准备吃果果。 不过因为小朋友们的身高有所区别，排成的队伍高低错乱，极不美观。设第i个小朋友的身高为 \(h_i (1\le h_i \le 10^9)\) ，我们定义一个序列的杂乱程度为：满足 \(h_i>h_j\) 的 \((i, j)\) 数量。幼儿园阿姨每次会选出两个小朋友，交换他们的位置，请你帮忙计算出每次交换后，序列的杂乱程度。为方便幼儿园阿姨统计，在未进行任何交换操作时，你也应该输出该序列的杂乱程度。 这题还是比较水的。 首先朴素的逆序对不会有人不会吧（不会吧不会吧 ，不会的戳这里 考虑一次修改会对答案产生什么影响 设交换 \(a_l\)...

小蓝书 16.1 一、计数原理 1. 加法原理 设完成某件事有 \(m\) 类不同的方法， 第 \(i(1\le i \le m)\) 类方法中有 \(n_i\) 种不同的方法，则完成这件事共有 \[ n_1 + n_2 + \cdots + n_m \] 种方法。 在严格化的数学中，加法原理是有关集合大小的事实。1 断言任意有限多个两两互斥的集合大小之和，等于其并集的大小 以符号表示为，若集合 \(S_1,S_2,\cdots,S_n\) 两两互斥，则有 \[ |S_1|+|S_2| + \cdots + |S_n| = |S_1 \cup S_2 \cup \cdots S_n| \] 容斥原理可以视为加法原理的推广。 2. 乘法原理 设完成某件事需要 \(m\) 个步骤， 做第 \(i\) 步有 \(n_i\) 种不同的方法，则完成这件事共有 \[ n_1 \times n_2 \times \cdots \times n_m \] 在集合论中，乘法原理可以设为基数乘积的定义。2 对于集合 \(S_1,S_2,\cdots,S_n\) ，以 \(|S_i|\) 表示 ...

CF1491F Magnets 题解 题目链接：CF1491F Magnets 题意： 这是一个交互题。 早苗有 \(n\) 块磁石，编号为 \(1,2,\cdots,n\)。每块磁石的磁极可能是正极，负极，也可能没有磁性。她希望你能帮她找出所有没有磁性的磁石。 万幸的是，你有一台磁力检测仪。你每次可以将每个磁石放在这台机器的左托盘，右托盘或者不放。 机器将会返回此时的磁力强度。设托盘左边有 \(n_1\) 个磁石为正极，\(s_1\) 个磁石为负极，托盘右边中有 \(n_2\) 磁石为正极，\(s_2\) 个磁石为负极，则返回的磁力强度为 $ n_1n_2+s_1s_2-n_1s_2-n_2s_1 $。 如果一次测试中磁力强度的绝对值大于 \(n\)，这台机器就会坏掉。 你需要在 \(n+\lfloor\log_2n\rfloor\) 次测试内找到所有没有磁性的磁石的编号，同时不能弄坏机器。 保证存在至少 \(2\) 块磁石有磁性且至少 \(1\) 块磁石没有磁性。 输入格式： 仅一行，包含一个正整数 \(T\)（\(1\leq T\leq 100\)），表示数据的组数。 ...

洛谷P2396 yyy loves Maths VII 题解 题目链接：P2396 yyy loves Maths VII 题意： 一群同学在和 yyy 玩一个游戏。 每次,他们会给 yyy \(n\) 张卡片，卡片上有数字，所有的数字都是“幸运数字”，我们认为第 \(i\) 张卡片上数字是 \(a_{i}\)。 每次 yyy 可以选择向前走 \(a_{i}\) 步并且丢掉第 \(i\) 张卡片。当他手上没有卡片的时候他就赢了。 但是呢，大家对“厄运数字”的位置布置下了陷阱，如果 yyy 停在这个格子上，那么他就输了。注意：即使到了终点，但是这个位置是厄运数字，那么也输了。 现在，有些同学开始问：yyy 有多大的概率会赢呢？ 大家觉得这是个好问题，有人立即让 yyy 写个程序：“电脑运行速度很快！\(24\) 的阶乘也不过就 \(620\,448\,401\,733\,239\,439\,360\,000\)，yyy 你快写个程序来算一算。” yyy 表示很无语，他表示他不想算概率，最多算算赢的方案数，而且是对 \(10^9+7\) 取模后的值。 大家都不会写程序,只好妥协。 ...

CF1073E Segment Sum 题解 题目链接：CF1073E Segment Sum 题意： 给定 \(l,r,k\) ，求 \([l,r]\) 有多少个数满足「不包含超过 \(k\) 个数码」，输出他们的和 \(\bmod {998244353}\) 。 \(0 \le k\le 10,~1\le l ,r \le 10^{18}\) 做了这题才发现自己对数位dp的掌握很烂 其实很水，用个状态 st 记录每个数码是否出现过 设 \(f_{i,j}\) 表示只考虑前 \(i\) 位（从低位向高位计数），数码状态为 \(j\) 的数字的个数 设 \(g_{i,j}\) 表示只考虑前 \(i\) 位（从低位向高位计数），数码状态为 \(j\) 的数字的和 则 \[ f_{i,j} = \sum f_{i-1,j^{\prime}}\\ \\g_{i,j} = \sum 10^{i-1} \times d \times f_{i-1,j^{\prime}} + g_{i,j^{\prime}} \] 其中 \(d\) 表示第 \(i-1\) 位要填啥， \(j^{\pri...

SP10606 BALNUM - Balanced Numbers 题解 题目链接：SP10606 BALNUM - Balanced Numbers 题意： 一个数被称为是平衡的数 当且仅当对于所有出现过的数位（即 \(0\) 到 \(9\) ） 每个偶数出现奇数次，每个奇数出现偶数次。 给定 \(A,B\)，请统计出 \([A,B]\) 内所有平衡数的个数。 \(1\leq A\leq B\leq 10^{19}\) 数位dp就是套板子，然后我现在还没记住板子（ 考虑记录每个数的奇偶性，用状态 st 表示 第 \(i(1\le i \le 9)\) 位为 \(0\) 表示出现次数为偶，否则为 \(1\) 再记录一个 vis ，表示这个数是否出现了 这两个东西可以压到一个 pair 里，这样方便开数组（和其他题解学的 因为这道题是统计出现次数的，所以前导零会影响计数 所以还要记录一下有没有前导零，代码里用 qd0 表示了（ 最后 check 一下状态啥的，就好了（ 代码： #include <iostream> #include <string> #includ...

UOJ66 新年的巧克力棒 题解 题目链接：#66. 新年的巧克力棒 题意：马上就要到羊年了，羊村一片欢腾，懒羊羊则懒洋洋地躺在草坪上吃新年的巧克力棒。 他手上的巧克力棒是个由 \(n\) 个巧克力单元格组成的长度为 \(n\) 的长条，现在懒羊羊想把巧克力棒掰开成一个个小单元格。 初始时懒羊羊会把这根巧克力棒丢在草坪上，然后每次懒羊羊会从草坪上拿起一根长度大于 \(1\) 的巧克力棒，然后从某两个相邻的单元格的间隙处掰开变成两根巧克力棒，然后把这两根巧克力棒丢在草坪上。懒羊羊初始愉悦值为 \(0\)，每次掰开巧克力棒后如果这两根巧克力棒长度相等，那么懒羊羊将提升 \(1\) 点愉悦值。 当然，草坪上全是长度为 \(1\) 的巧克力棒时懒羊羊就会停止操作。现在懒羊羊想知道，他能获得的愉悦值最多是多少？ 设 \(f_i\) 表示长度为 \(i\) 的巧(áo)克(lì)力(gèi)能获得的最大价值，则 \[ f_i = \max\limits_{1 \le j < i}\left\{f_j + f_{i-j} + [j=i-j]\right\} \] 然后这东西是 \(O...

洛谷P2292 [HNOI2004] L 语言 题解 题目链接：P2292 [HNOI2004] L 语言 题意： 标点符号的出现晚于文字的出现，所以以前的语言都是没有标点的。现在你要处理的就是一段没有标点的文章。 一段文章 \(T\) 是由若干小写字母构成。一个单词 \(W\) 也是由若干小写字母构成。一个字典 \(D\) 是若干个单词的集合。我们称一段文章 \(T\) 在某个字典 \(D\) 下是可以被理解的，是指如果文章 \(T\) 可以被分成若干部分，且每一个部分都是字典 \(D\) 中的单词。 例如字典 \(D\) 中包括单词 \(\texttt{is},\texttt{name},\texttt{what},\texttt{your}\)，则文章 \(\texttt{whatisyourname}\) 是在字典 \(D\) 下可以被理解的，因为它可以分成 \(4\) 个单词：\(\texttt{what},\texttt{is},\texttt{your},\texttt{name}\)，且每个单词都属于字典 \(D\)，而文章 \(\texttt{whatisyo...

洛谷P1305 新二叉树 题解 题目链接：P1305 新二叉树 题意： 输入一串二叉树，输出其前序遍历。 输入1： 6 abc bdi cj* d** i** j** 输出1： abdicj 虽然是大水题，但是有个解法还是很妙的 利用前序遍历的性质，它的子树一定在它后面。 直接贴代码了，感觉很妙： #include <iostream> #include <string> #include <vector> #include <algorithm> #include <cstdio> #include <cstdlib> #include <cstring> #include <cmath> #include <iomanip> #include <random> using namespace std; #define int long long #define INF 0x3f3f3f3f3f3f3f3f #define N (int)() int n; string s,t; signed main() &#...

洛谷P1229 遍历问题 题解 题目链接：P1229 遍历问题 题意： 我们都很熟悉二叉树的前序、中序、后序遍历，在数据结构中常提出这样的问题：已知一棵二叉树的前序和中序遍历，求它的后序遍历，相应的，已知一棵二叉树的后序遍历和中序遍历序列你也能求出它的前序遍历。然而给定一棵二叉树的前序和后序遍历，你却不能确定其中序遍历序列，考虑如下图中的几棵二叉树： 所有这些二叉树都有着相同的前序遍历和后序遍历，但中序遍历却不相同。 输出可能的中序遍历序列的总数，结果不超过长整型数。 首先这个遍历方式都知道吧 前序遍历：根左右 后序遍历：左右根 等等，如果根只有一个儿子怎么办？ 好问题，我们并不知道他到底是左儿子还是右儿子 根据乘法原理，设有 \(k\) 个结点 \(u_i\) 满足 \(\left|\left\{v \mid v \in \text{son}(u)\right\}\right|=1\) 则答案为 \(2^k\) 。直接 \(O(n^2)\) 跑一下就好啦！ 代码： #include <iostream> #include <string> #include...