Q779’s Blog

CF1714F Build a Tree and That Is It 题解 题目链接：CF1714F Build a Tree and That Is It 题意： 树是一个没有环的无向连通图，注意，在本题中，我们讨论的是无根树 现有四个整数 $ n, d_{12}, d_{23} $ 和 $ d_{31} $ 。构建一颗满足以下条件的树: 包含从 $ 1 $ 到 $ n $ 的 \(n\) 个节点, 从节点 $ 1 $ 到节点 $ 2 $ 的距离（最短路的长度）为 $ d_{12} $ , 从节点 $ 2 $ 到节点 $ 3 $ 的距离为 $ d_{23} $ , 从节点 $ 3 $ 到节点 $ 1 $ 的距离为 $ d_{31} $ 。 输出满足条件的任意一棵树；若不存在，请证明。 输入格式： 第一行包含一个整数 $ t $ ( $ 1 t ^4 $ ) 表示测试组数. 接下来 $ t $ 组, 每组一行数据包含 \(4\) 个整数 $ n, d_{12}, d_{23}, d_{31} $ ( $ 3 n ^5,~1 d_{12}, d_{23}, d_{31} n...

CF1312C Adding Powers 题解 题目链接：CF1312C Adding Powers 题意： 多组数据。假设你正在执行以下算法： 初始时，有一个填满零的数组 \(v_1, v_2, \ldots, v_n\)。 该算法会多次对数组进行以下操作： 在第 \(i\) 步（从 \(0\) 开始），你可以： 要么选择位置 \(\mathrm{pos}\) \((1 \leq \mathrm{pos} \leq n)\) 并将 \(v_{\mathrm{pos}}\) 增加 \(k^i\)。 要么不选择任何位置，跳过这一步。 你可以选择算法在每一步中的行为以及何时停止。 问题是：能否在某一步后使数组 \(v\) 等于给定的数组 \(a\)（对于每个 \(j\)，有 \(v_j=a_j\) ）？ 数据范围： \(1\le T \le 10^3,~1 \le n \le 30, 1\le k \le 100, 0\le a_j \le 10^{16}\) 这个题还是蛮简单的，如果目标数组能够达成，那么所有 \(a_j\) 在 \(k\) 进制分解后一定不存在重复出...

UVA10118 Free Candies 题解 题目链接：UVA10118 Free Candies 题意： cxy 正在玩一个游戏。她想要赢得尽可能多的糖果。 有 \(4\) 堆糖果，每堆包含 \(N\) 个糖果。cxy 被给予一个篮子，最多可以容纳 \(5\) 个糖果。每次，她将一颗糖果放在一堆的顶部放入篮子中，如果篮子中有两颗相同颜色的糖果，她可以将它们都拿出篮子，放入自己的口袋。当篮子已满且篮子中没有两颗相同颜色的糖果时，游戏结束。如果游戏完美进行，游戏结束时堆中将没有剩余糖果。 例如，cxy 可能会这样玩游戏\((N=5)\)： 注意，不同的数字表示不同的颜色，共有 \(20\) 种颜色，编号为 \(1\) 到 \(20\) 。 “看起来很难…” cxy 非常困惑。 她最多能带回家多少对糖果？ 输入格式： 输入将包含不超过 \(10\) 个测试用例。每个测试用例以包含一个整数 \(n(1 \leq n \leq 40)\) 的行开始，表示堆的高度。接下来的 \(n\) 行中，每行包含四个整数\(x_{i_1}, x_{i_2}, x_{i_3}, x_{i_4}\)...

[ABC141E] Who Says a Pun? 题解 题目链接：[ABC141E] Who Says a Pun? 题意： 给定长度为 \(N\) 的字符串 \(S\) 。找出在 \(S\) 中作为连续子串出现两次或更多次的非空字符串的最大长度，且这些子串不重叠。更正式地说，找到满足以下条件的最大正整数 len ，使得存在整数 \(l_1\) 和 \(l_2\) \((1 \leq l_1, l_2 \leq N-\text{len}+1)\) ，满足： \(l_1 + \text{len} \leq l_2\) 对于 \(i=0,1, \ldots, \text{len} -1\) ，有 \(S[l_1+i] = S[l_2+i]\) 。 如果不存在这样的整数 len ，则输出0。 数据范围： \(2 \leq N \leq 5 \times 10^3,~|S| = N\) 。 \(S\) 由小写英文字母组成。 考虑二分这个最大长度，然后用哈希检验。注意这道题要求不重叠，所以要注意一下。 如果用双哈希的话会稍微慢一丢丢，不过我还是用了（大雾） 时间复杂度 \(\ma...

CF173B Chamber of Secrets 题解 题目链接：CF173B Chamber of Secrets 题意： “密室再次被打开了。”——这个消息传遍了霍格沃茨，而一些学生因为看到蛇怪而被石化。虽然邓布利多被迫离开了学校，但哈利正尝试进入密室。而这对伏地魔可不是什么好消息。他不希望任何人进入密室。因为他正在吸取金妮的灵魂。 密室是一个\(n×m\)的矩形网格，其中一些单元格有柱子。光线（蛇怪的凝视）可以穿过柱子而不改变方向。但是通过一些魔咒，我们可以让柱子在接收光线时反射所有光线向四个方向射去。如下图所示。 左边光线穿过没有施魔法的柱子，右边光线穿过施魔法的柱子，效果如图。蛇怪在密室的右下角，向左边凝视。据传说，直接看见蛇怪的眼睛就会马上死亡，而看到通过柱子的反射光线就会被石化。我们知道，密室的入口在左上角，而进入的人必须注视他所要移动的方向。图片就是第一个样例。 给定密室的大小，和普通柱子的位置，伏地魔想要让你对最少的柱子施法，使所有人不能进入密室；或者表示不能完成保护密室的任务。 输入格式： 输入的第一行包含两个整数\(n\)和\(m\) \((2<...

CF1771C Hossam and Trainees 题解 题目链接：CF1771C Hossam and Trainees 题意： cxy 有 \(n\) 个学员。她为第 \(i\) 个学员指定了一个数字 \(a_i\)。 如果存在一个整数 \(x(x \geq 2)\)，满足 \(x\) 能同时整除 \(a_i\) 和 \(a_j\)，则第 \(i\) 个和第 \(j\) 个学员构成一对成功的学员。 cxy 想知道是否存在一对成功的学员。 由于 cxy 现在非常累（因为和妹纸玩了很久），她请求你的帮助！ 输入格式 输入包含多个测试用例。第一行包含一个整数 \(t\left(1 \leq t \leq 10^5\right)\)，表示测试用例的数量。接下来是每个测试用例的描述。 每个测试用例的第一行包含一个整数 \(n\left(2 \leq n \leq 10^5\right)\)。 每个测试用例的第二行包含 \(n\) 个整数 \(a_1, a_2, \ldots, a_n\)（\(1 \leq a_i \leq 10^9\)）。 保证所有测试用例中 \(n\) 的总和...

[ABC260G] Scalene Triangle Area 题解 题目链接：[ABC260G] Scalene Triangle Area 题意： 我们有一个 \(N \times N\) 的网格。在这个网格中，从顶部数起的第 \(i\) 行、从左侧数起的第 \(j\) 列的方格被称为 \((i, j)\)。 网格的每个方格最多放置一个棋子。网格的状态由 \(N\) 个字符串 \(S_i\) 给出： 如果 \(S_i\) 的第 \(j\) 个字符为 0，则 \((i, j)\) 上有一个棋子； 如果 \(S_i\) 的第 \(j\) 个字符为 X，则 \((i, j)\) 上没有棋子。 给定一个整数 \(M\)。使用这个 \(M\)，我们定义当位于 \((s, t)\) 的棋子 \(P\) 覆盖方格 \((u, v)\) 时，需要满足以下所有条件： \(s \leq u \leq N\) \(t \leq v \leq N\) \((u-s)+\frac{(v-t)}{2}<M\) 对于 \(Q\) 个方格 \((X_i, Y_i)\)，找出有多少个棋子覆盖了...

UVA11214 Guarding the Chessboard 题解 题目链接：UVA11214 Guarding the Chessboard 题意： 多组数据。输入一个 \(n×m\) 的棋盘（ \(n,m<10\) ），某些格子有标记。 用最少的皇后守卫（即占据或者攻击）所有带标记的格子。 显然是搜索，这道题的特点在于搜索的深度可能及其大，所以我们需要用迭代加深搜索 (IDA star)。 所谓迭代加深搜索，就是限制一个搜索深度的上限，在本题中我们可以限制放的棋子数量。 因为 \(8\times 8\) 的棋盘都只需要 \(5\) 个皇后，所以实际运行的效率还是比较高的。 时间复杂度 \(\mathcal{O}(\text{ok})\) 代码： #include <bits/stdc++.h> using namespace std; #define int long long #define INF 0x3f3f3f3f3f3f3f3f void up(int &x,int y) { x < y ? x = y : 0;
...

CF794C Naming Company 题解 题目链接：CF794C Naming Company 题意： 下面是修正后的文本，使用Markdown格式和行内公式： A,B 两人各有一个长度为 \(n\) 的，由小写字母构成的字符串 \(s\) 和 \(t\)，还有一个长度为 \(n\)，初始时由 ? 组成的目标串 \(f\)。 现在，A和B轮流进行如下操作： 在自己的字符串中选出一个字符 \(x\)。 将 \(f\) 中的一个 ? 替换为 \(x\)。 将 \(x\) 从自己的字符串中删去。 当 \(f\) 中没有 ? 时游戏结束。 A 的目标是让 \(f\) 的字典序尽量小，而 B 的目标是让字典序尽量大。 现在设 A 为先手，你需要求出游戏结束后的 \(f\)。 注意： \(s\) 和 \(t\) 中可能有多个重复的字符，每次只删除一个。 数据范围： \(1 \le n \le 3\times 10^5\) 一个显然的贪心方案，让双方都在最前面填上符合自己利益的字符。 这个贪心是不正确的，因为当 A 最小的字符大于 B 最大的字符时，原有方案会得到较大的答案。 ...

AT_codefestival_2015_qualB_d Squares, Pieces and Coloring 题解 题目链接：AT_codefestival_2015_qualB_d Squares, Pieces and Coloring 题意： 有 \(10^{100}\) 个方块排成一行。这些方块从左到右编号为 \(1\) 到 \(10^{100}\)。 我们有 \(N\) 个编号为 \(1\) 到 \(N\) 的棋子，以及一个计数器，可以存储介于 \(0\) 和 \(10^{100}\) 之间（包括边界值）的整数。 我们将使用这些工具执行 \(N\) 个过程。初始时，方块为白色。第 \(i\) 个过程（\(1 \leq i \leq N\)）如下： 将棋子 \(i\) 放在方块 \(S_i\) 上，并将计数器设置为 \(0\)。 查看棋子 \(i\) 所在方块的颜色。若方块为白色，则将其涂为黑色，并将计数器增加 1。 否则（若方块为黑色），将棋子 \(i\) 向右移动一个方块。因此，一个方块可能包含多个棋子。 如果计数器的值等于 \(C_i\)，则终止该过程...

CF1768E Partial Sorting 题解 题目链接：CF1768E Partial Sorting 题意： 给定整数 \(n\) 和质数 \(M\)。 对于一个 \(1\sim 3n\) 的排列 \(p\)，你可以进行下列操作： 将 \(p\) 的前 \(2n\) 个元素从小到大排序。 将 \(p\) 的后 \(2n\) 个元素从小到大排序。 可以证明任意 \(1\sim 3n\) 的排列都能通过若干次上述操作从小到大排序。 记 \(f(p)\) 表示将 \(p\) 从小到大排序所需的最小总操作次数。 你需要求出对于所有 \(1\sim 3n\) 的排列 \(p\)，其 \(f(p)\) 总和对 \(M\) 取模后的值。 输入格式： 输入一行两个整数 \(n,M(1\leq n\leq10^6;10^8\leq M\leq10^9)\)，保证 \(M\) 是质数。 输出格式： 输出一行一个整数表示 \(f(p)\) 的总和对 \(M\) 取模后的值。 一个显然的操作上界是 \(3\) 次。下面我们来依次考虑 \(f(p)\) 的取值： \(f(p) \le ...

[ARC129C] Multiple of 7 题解 题目链接：[ARC129C] Multiple of 7 题意： 给定一个整数 N。 找到一个由数字 1 到 9 组成的字符串 s，满足以下条件： s 的长度 \(\vert s \vert\) 最多为 \(10^6\)。 有恰好 N 对整数 \((l,r)\) \((1 \leq l \leq r \leq \vert s \vert)\) 满足以下条件。 当将 s 的第 l 到第 r 个字符提取出来看作一个数时，该数能被 \(7\) 整除。 在这个问题的约束条件下，我们可以证明一定存在一种解法。 数据范围： \(1 \leq N \leq 10^6\) 这个 \(7\) 真的是非常独特啊，因为它是个位数中最大的质数。 同时样例2的 \(\tt{77}\) 也提示了我们，这道题可能需要构造若干 \(\tt{77777}\) 的子串，并拼接他们。 可以发现长度为 \(k\) 的 \(\mathtt{77777}\) 串的贡献为 \(\frac{k(k+1)}{2}\) ，在 \(10^6\) 的限制下实际串上 \(...