Q779’s Blog

洛谷P4573 [CQOI2013]新数独 题解 题目链接：P4573 [CQOI2013]新数独 题意： 下面是一个没有数字，只有大小关系（没错，那些尖角都是“大于符号”）！的数独： 除了大小关系外（注意相邻格子不能相同），还需要满足通常的数独规则： 每个格子都是 \(1\sim 9\) 的数字 每行都是 \(1 \sim 9\) 的排列 每列都是 \(1 \sim 9\) 的排列 每个 \(3\times 3\) 的子矩阵（上图中用粗线隔开，一共有 \(3\times 3\) 个这样的子矩阵）都是 \(1\sim 9\) 的排列 为了美观，每个 \(3\times 3\) 子矩阵的所有 \(12\) 对相邻格子的大小关系都将给出。 输入格式： 一共 \(15\) 行，包含一个新数独的实例。第 \(1,3,5,6,8,10,11,13,15\) 行包含左右方向的符号（< 和 >），其余行包含上下方向的符号（^ 和 v） 输出格式： 包含 \(9\) 行，每行 \(9\) 个 \(1\sim 9\) 的数字，以空格隔开。输入保证唯一解。 想了半天，感觉跟 t...

洛谷P5081 Tweetuzki 爱取球 题解 题目链接：P5081 Tweetuzki 爱取球 题意： Tweetuzki 有一个袋子，袋子中有 \(N\) 个无差别的球。Tweetuzki 每次随机取出一个球后放回。求取遍所有球的期望次数。 取遍是指，袋子中所有球都被取出来过至少一次。 输入格式： 一行一个整数 \(N\) \((1 \le N \le 10^7)\)。 输出格式： 一行一个整数，表示期望次数。由于这个数可能很大，输出对 \(20040313\) （是个质数）取模。 数据范围： 对于 \(100\%\) 的数据，\(1 \le N \le 10^7\)。 引理：设成功完成事情 \(A\) 的概率为 \(P\) ，如果不成功就继续。则期望 \(\dfrac{1}{P}\) 次完成这件事。 证明：设期望 \(k\) 次完成事情 \(A\) 。根据定义有 \[ k = 1 + p\times 0 + (1 - p)\times k \] 其中 \(1\) 表示初始的一次尝试，\(p\) 表示本次成功，\((1-p)\) 表示本次失败。移项得 \(k = \df...

CF913C Party Lemonade 题解 题目链接：CF913C Party Lemonade 题意： 新年派对少了柠檬水就不是真正的新年派对！ 如往常一样，你期望有很多客人，购买柠檬水已成为一种愉快的必需品。 你最喜欢的商店以不同容量和不同价格销售柠檬水。 一瓶第 \(i\) 类型的柠檬水容量为 \(2^{i-1}\) 升，价格为 \(c_i\) 卢布。商店中每种类型的柠檬水瓶数可以被认为是无限的。 你想购买至少 \(L\) 升的柠檬水。你需要花费多少卢布呢？ 输入格式： 第一行包含两个整数 \(n\) 和 \(L\left(1 \leq n \leq 30 ; 1 \leq L \leq 10^9\right)\) - 商店中瓶子类型的数量和所需的柠檬水数量（升）。 第二行包含 \(n\) 个整数 \(c_1, c_2, \ldots, c_n\left(1 \leq c_i \leq 10^9\right)\) - 不同类型柠檬水瓶子的价格。 输出格式： 输出一个整数 - 为了购买至少 \(L\) 升柠檬水，你需要支付的最少卢布数。 注意到如果 \(2w_{i ...

洛谷P6015 [CSGRound3]游戏 题解 题目链接：P6015 [CSGRound3]游戏 题意： 小 Y 和小 Z 是一对好朋友，他们在玩一个游戏。游戏只有一个回合。 有一个牌堆，一共有 \(n\) 张牌，第 \(i\) 张牌上有一个数 \(a_i\)，其中第一张牌是堆顶。 小 Z 先取牌，他可以从堆顶开始取连续若干张牌（可以取 \(0\) 张），取完的牌拿在手上，也就是不在牌堆里了。 然后小 Y 取牌，同样，她也可以从堆顶开始取连续若干张牌（可以取 \(0\) 张）。 如果一个人手上的牌的数字和大于 \(X\)，那么他的分数就是 \(0\)，否则分数就是数字和。 分数高的人获胜，如果一样高，则无人获胜。 小 Z 为了获胜，使用了透视挂，即他知道牌堆里每张牌上写的数。 现在问你对于满足 \(1 \leq X \leq K\) 的所有整数 \(X\)，哪些可以使得小 Z 有必胜策略，即小 Z 取完后，不管小 Y 怎么取都一定会输。 输入格式： 第一行一个整数 \(n\)，表示牌堆里有几张牌。 第二行 \(n\) 个整数 \(a_{1\dots n}\)，表示每张牌上写的...

SP22393 KATHTHI 题解 题目链接：SP22393 KATHTHI 题意： 多组数据。每组数据给定一个 \(n\times m\) 的方格，每个格子里有一个小写字母。 每次移动操作可以移到四连通的格子内。如果目标格子的字母与当前格子相同，则花费 \(0\) ，否则花费 \(1\) 。 求 \((1,1)\) 到 \((n,m)\) 的最小花费。 显然是 01bfs ，不知道怎么标的蓝。 对于网格上的最短路，我们一般把它直接看成图，也就是网格图。 由于边权只有 0 或 1 ，所以我们可以用 01bfs ，也就是用一个双端队列维护 bfs 。 如果当前移动没有消耗，则我们把它放到队头，再次移动。这样可以保证每次先跑的一定是优的。 时间复杂度 \(\mathcal{O}(\sum nm)\) 代码：（题解区随便扒的） #include<iostream> #include<cstring> #include<cstdio> #include<deque> #define ll long long #define rgt register int ...

SP18202 HG - HUGE GCD 题解 题目链接：SP18202 HG - HUGE GCD 题意： 求 \[ \gcd\left(\prod_{i=1}^N A_i, \prod_{i=1}^M B_i\right) \] 保留 \(9\) 位数字。 \(1\le N,M \le 10^3,1 \le A_i, B_i \le 10^9\) 。 这个题很明显，我们只需要把两侧的数全都质因数分解， 然后扫一遍，每个质因数取两侧最小的值即可。比如左边有 \(2^33^2\) ，右边有 \(2^23^3\) ，那就取 \(2^23^2\) 。 这样做的复杂度应该是 \(\mathcal{O}(n \log^2 n + n \sqrt{M})\) ，其中 \(M\) 为 \(A_i,B_i\) 的值域。 不过这个做法需要对每个数都进行一次质因数分解，cxy 觉得这样很粗鲁，所以我们讲一种不需要分解的做法 我们依次考虑每个 \(A_i\) ，然后枚举 \(B_j\) 。记 \(d = \gcd(A_i, B_j)\) ，然后令 \(A_i,B_j\) 除以 \(d\) ，答...

CF1056E Check Transcription 题解 题目链接：CF1056E Check Transcription 题意： cxy 在一座巨大的射电望远镜工作。几十年前，该望远镜向一个遥远的星系发送了一个信号 \(s\) 。最近，她收到了一个回应 \(t\) ，她认为这是外星人的回应！科学家们现在想要检查信号 \(t\) 是否与 \(s\) 相似。 原始信号 \(s\) 是由 0 和 1 组成的序列（大家都知道二进制是宇宙通用语言）。然而，返回的信号 \(t\) 看起来并不像 \(s\) 那样简单，但是科学家们并没有放弃！她将 \(t\) 表示为一个英文字母的序列，并且说如果你可以用某个字符串 \(r_0\) 替换 \(s\) 中的所有零，并用另一个字符串 \(r_1\) 替换 \(s\) 中的所有一，得到 \(t\)，那么 \(t\) 就与 \(s\) 相似。字符串 \(r_0\) 和 \(r_1\) 必须是不同且非空的。 请帮助 cxy ，找出将 \(s\) 转换为 \(t\) 的可能的零和一的替换次数（字符串 \(r_0\) 和 \(r_1\) 的对数）。 输...

CF1706D2 Chopping Carrots (Hard Version) 题解 题目链接：CF1706D2 Chopping Carrots (Hard Version) 题意： 这是该问题的困难版本。两个版本间的区别仅为 \(n\)、\(k\)、\(a_i\) 和 \(\sum n\) 的上界。 注意不正常的空间限制。 给出长度为 \(n\) 的整数数组 \(a_1, a_2, \ldots, a_n\)，以及一个整数 \(k\)。 一个长度为 \(n\) 的整数数组 \(p_1, p_2, \ldots, p_n\) 的花费为 \(\max\limits_{1 \le i \le n}\left(\left \lfloor \frac{a_i}{p_i} \right \rfloor \right) - \min\limits_{1 \le i \le n}\left(\left \lfloor \frac{a_i}{p_i} \right \rfloor \right)\)。 此处，\(\lfloor \frac{x}{y} \rfloor\) 表示 \(x\) ...

CF41E 3-cycles 题解 题目链接：CF41E 3-cycles 题意： 最近，Berland的科学家们在研究中发现古代Berland有 \(n\) 个城市，它们通过双向路径相连。任意两个城市之间最多只有一条路径相连，且没有路径将城市与自身相连。根据众所周知的传统，道路网络的建设是为了确保不可能选择三个城市，其中每个城市都可以直接到达其他任何一个城市。也就是说，不存在长度为 \(3\) 的环。不幸的是，道路地图并没有保存到现在。现在科学家们想知道古代Berland发展到了什么程度。帮助他们找出国家可能存在的最大道路数量，并恢复其中任意一种可能的道路地图。 输入格式： 第一行包含一个整数 \(n\) \((1 \leq n \leq 100)\)，表示Berland的城市数量。 输出格式： 第一行输出一个整数 \(m\)，表示Berland可能存在的最大道路数量。接下来的 \(m\) 行每行包含两个整数，表示给定道路连接的城市编号。城市编号从 \(1\) 到 \(n\)。如果有多种解决方案，请随意输出其中之一。 根据抽屉原理，每三个节点就有两个节点没有连边，我们可以认...

[ABC266G] Yet Another RGB Sequence 题解 题目链接：[ABC266G] Yet Another RGB Sequence 题意： 给定整数 \(R, G, B\) 和 \(K\)。 求有多少个由 \(\tt{R}\)、\(\tt{G}\) 和 \(\tt{B}\) 组成的字符串 \(S\) 满足以下所有条件？计算结果取模 \(998244353\) 。 字符串 \(S\) 中 \(\tt{R}\)、\(\tt{G}\) 和 \(\tt{B}\) 的出现次数分别为 \(R, G\) 和 \(B\)。 字符串 \(S\) 中连续出现的子字符串 \(\tt{RG}\) 的个数为 \(K\)。 数据范围： \(1 \leq R, G, B \leq 10^6,~0 \leq K \leq \min (R, G)\) 。 一道有意思的计数题。记 \(\mathtt{rg}\) 为 \(🤡\) 。 则原题转化为求 \(R-k\) 个 \(\mathtt{r},~ G-k\) 个 \(\mathtt{g}, ~B\) 个 \(\mathtt{b}\)...

洛谷P5005 中国象棋 - 摆上马 题解 题目链接：P5005 中国象棋 - 摆上马 题意： cxy 有一个 \(X\) 行 \(Y\) 列的棋盘，还有很多完全相同的马（你可以认为有无数个）。现在在棋盘上摆上马（或者不摆），求任何马无法攻击另一匹马的方案总数。 中国象棋的马和国际象棋的马不同。 注意：实际问题中是没有兵的。 当然由于方案可能过多，请输出对 \((10^9+7)\) 取模的值。 输入格式： 第一行两个正整数 \(X,Y\)。 输出格式： 方案对 \((10^9+7)\) 取模的值。 数据范围： 对于 100% 的数据，有 \(1\le X\leq100\)，\(1\le Y\leq6\)。 设 \(f(i,j,k)\) 表示考虑前 \(i\) 行，当前行的状态为 \(j\) ，上一行的状态为 \(k\) 时的方案数，则 （ \(\uparrow\) 表示 += ） \[ f_{i,j,k} \uparrow f_{i-1,k,l} \] 这个转移方程很容易得出，但是它的前提是 \((j,k),(s,k),(s,j)\) 均不冲突。判断的代码如下： int a...

CF954C Matrix Walk 题解 题目链接：CF954C Matrix Walk 题意： 你有一个大小未知（假设为 \(x\times y\)）的矩阵，这个矩阵中的格子的编号的排列有规律，比如说 \((i,j)\) 号格子的编号为 \(y\times (i - 1) + j\)。 但是现在这个矩阵的大小是未知的，我们的任务是算出来这个矩阵的任意一种可能的大小。 接下来，你有一个长度为 \(n\) 序列，表示你在矩阵中行动时走到的格子的编号。（你在矩阵中只能上下左右行动，不能走出矩阵） 如果说有符合这种序列的矩阵，那么输出 YES，并输出矩阵的任意一种可能的大小 ；否则输出 NO。 输入格式： 第一行一个整数 \(n\)。 第二行 \(n\) 个整数，表示这个序列。 输出格式： 我们需要的矩阵的大小。 数据范围： \(1 \le n\le 2 \times 10^5\)，序列中任意的数字都小于等于 \(10^9\)，矩阵大小小于 \(10 ^ 9\times 10^9\)。 简单的小结论题。容易发现上下两个数相差 \(y\) ，并且这道题跟 \(x\) 基本没有关系。...