Q779’s Blog

SP34020 ADAPET - Ada and Pet 题解 题目链接：SP34020 ADAPET - Ada and Pet 题意： cxy 刚刚领养了一只新宠物。她正在考虑给它取一个名字。她已经想出了一个漂亮的名字，但现在她觉得这个名字还不够”特别”。她想要找到一个新名字，其中至少包含原始名字作为子串出现 \(K\) 次（以强调其重要性）。由于 cxy 不希望宠物的名字太长，她希望找到最短的名字——你能找到它的长度吗？ 输入格式： 输入的第一行将包含 \(T\)，表示测试用例的数量。接下来的 \(T\) 行中，每行包含一个非空字符串 \(s\)，由小写英文字母和数字 \(1\) 组成（表示给定名字在新名字中出现的次数）。 所有测试用例中字符串长度的总和不会超过 \(5\times 10^5\)。 输出格式： 对于每个测试用例，请打印出新名字的最小长度。 结论：最小长度为 \[ (n - \mathrm{fail}(n)) \times (k - 1) + n \] 证明么，我们只需要用 \(n - \mathrm{fail}(n)\) 的那段在原串后面无限拼就好了，其...

UVA12436 Rip Van Winkle’s Code 题解 题目链接：UVA12436 Rip Van Winkle’s Code 题意： cxy 对除了妹纸和编程之外的一切都感到厌烦。 有一天，她发现了一个问题，需要执行三种类型的更新操作 \(\mathtt{A,B,C}\)， 以及一个查询操作 \(S\) ，针对一个数组 \(\mathtt{data[]}\) ，初始时，\(\mathtt{data}\) 的所有元素都等于 \(0\) 。 虽然 cxy 要和妹纸玩耍，而且她的代码也非常慢， 但你需要以高效的方式执行相同的更新操作，并输出查询操作 \(S\) 的结果。 long long data[250001]; void A( int st, int nd ) { for( int i = st; i <= nd; i++ ) data[i] = data[i] + (i - st + 1); } void B( int st, int nd ) { for( int i = st; i <= nd; i++ ) da...

UVA10036 Divisibility 题解 题目链接：UVA10036 Divisibility 题意： 考虑一个任意的整数序列。我们可以在序列中的整数之间放置+或-运算符，从而得到不同的算术表达式，其计算结果不同。例如，让我们考虑序列：\(17,5,-21,15\)。有八种可能的表达式： \[ \begin{aligned} & \texttt{17 + 5 + -21 + 15 = 16} \\ & \texttt{17 + 5 + -21 - 15 = -14} \\ & \texttt{17 + 5 - -21 + 15 = 58} \\ & \texttt{17 + 5 - -21 - 15 = 28} \\ & \texttt{17 - 5 + -21 + 15 = 6} \\ & \texttt{17 - 5 + -21 - 15 = -24} \\ & \texttt{17 - 5 - -21 + 15 = 48} \\ & \texttt{17 - 5 - -21 - 15 = 18} \e...

[ABC139E] League 题解 题目链接：[ABC139E] League 题意： 将有 \(N\) 个选手参加一场网球比赛。我们将称他们为 Player 1，Player 2，直到 Player N。 比赛采用循环赛制，总共将进行 \(\frac{N(N-1)}{2}\) 场比赛。是否可能安排这些比赛，以满足以下所有条件？ 如果答案是肯定的，还要找出所需的最小天数。 每个选手一天最多进行一场比赛。 每个选手 \(i\)（\(1 \leq i \leq N\)）按照顺序与选手 \(A_{i,1}\)，\(A_{i,2}\)，…，\(A_{i,N-1}\) 进行一场比赛。 提示：可以同时进行比赛，但是一天只有举办一次比赛的时间。 输入格式： \[ \begin{array}{llll} N\\ A_{1,1} & A_{1,2} & \ldots & A_{1, N-1} \\ A_{2,1} & A_{2,2} & \ldots & A_{2, N-1} \\ : & & & \\ A_{N, ...

洛谷P6509 [CRCI2007-2008] JEDNAKOST 题解 题目链接：洛谷P6509 [CRCI2007-2008] JEDNAKOST 题意： 给定一个形如 A=B 的字符串，其中 \(A\) 和 \(B\) 都是不含前导零的正整数。请给 \(A\) 的一些相邻数位之间加上加号，要求添加的加号数量最少，使得等式成立。 在 \(A\) 加上加号后，每个加数允许有多个前导 \(0\)。包括 \(0\) 在内。也即允许形如 \(000 \ldots\) 的数作为加数。 数据保证有解。 输入格式： 输入只有一行一个形如 A=B 字符串，表示给定的等式。 输出格式： 本题存在 Special Judge。 输出一行一个字符串，表示加上加号以后的成立的等式。 数据范围： 保证 \(1 \leq A \lt 10^{1000}\)，\(1 \leq B \leq 5 \times 10^3\)，\(A \neq B\)。 看上去只有 dfs 能解，因此考虑记忆化搜索。 设 \(f(i,j)\) 表示走到 \(i\) ，还差 \(j\) 就能使式子的和等于 \(B\) ，则 ...

SP32079 ADAGF - Ada and Greenflies 题解 题目链接：SP32079 ADAGF - Ada and Greenflies 题意： 给定 \(a_i\) ，求 \[ \sum_{1\le i \le j \le n} \gcd(a_i,a_{i+1},\cdots,a_j) \] 数据范围： \(1\le n \le 3\times 10^5,~0 \le a_i \le 10^6\) 。 很经典的题。我记得我第一次做好像是用二分做的，复杂度比现在的做法应该多一个 log 。 容易发现 \(j\) 固定时，区间 \([i,j]\) 的 \(\gcd\) 会单调递减。并且每次至少减少一半（除以 \(2\) ） 所以实际上只有 \(\log M\) 段，于是我们可以动态地维护这个段，每段对 \(a_j\) 取 \(\gcd\) 。 时间复杂度 \(\mathcal{O}(n\log M)\) ，应该比二分快多了。 代码： #include <bits/stdc++.h> using namespace std; #define int lon...

UVA124 Following Orders 题解 题目链接：UVA124 Following Orders 题意： 顺序是数学和计算机科学中的一个重要概念。例如，佐恩引理（Zorn’s Lemma）指出：“一个偏序集合中，每个链都有一个上界，那么该集合中必存在一个极大元素”。顺序在推理程序的不动点语义中也很重要。 这个问题既不涉及佐恩引理，也不涉及不动点语义，但涉及到顺序。给定一组形式为 \(x<y\) 的变量约束，你需要编写一个程序，打印出与这些约束一致的变量排序。 例如，给定约束 \(x<y\) 和 \(x<z\)，存在两种与这些约束一致的变量 \(x\)、\(y\) 和 \(z\) 的排序：\(x \ y \ z\) 和 \(x \ z \ y\)。 输入格式： 输入由一系列约束规范组成。每个规范由两行组成：第一行是变量列表，第二行是约束列表。约束由一对变量组成，其中 “\(x y\)” 表示 \(x<y\)。 所有的变量都是小写字母，并且只包含一个字符。每个规范中至少会有两个变量，且不超过 20 个变量。每个规范中至少会有一个约束，且不超过 ...

CF33B String Problem 题解 题目链接：CF33B String Problem 题意： 萌妹纸 cxy 喜欢字符串和妹纸。而且她更喜欢它们相同。这就是为什么在闲暇时间里，cxy 会玩以下游戏。她拿任意两个由小写拉丁字母组成的字符串，并试图使它们相同。根据游戏规则，每次移动，cxy可以将字符串中的任意字符\(A_i\)改变为任意字符\(B_i\)，但她必须为每次移动付出一定的金钱，金额等于\(W_i\)。她可以根据需要进行任意次移动。由于cxy是个非常节俭的妹纸，从不浪费她的钱，她请教你这位经验丰富的程序员，帮她回答这个问题：cxy应该拥有多少最少的金钱才能得到相同的字符串。 输入格式： 第一行输入包含两个初始非空字符串\(s\)和\(t\)，由小写拉丁字母组成。每个字符串的长度不超过\(10^5\)。接下来的一行包含整数\(n(0 \leq n \leq 500)\)，表示可能的更改次数。然后是\(n\)行，每行包含字符\(A_i\)和\(B_i\)（小写拉丁字母）以及整数\(W_i\left(0 \leq W_i \leq 100\right)\)，表示可...

UVA10603 倒水问题 Fill 题解 题目链接：UVA10603 倒水问题 Fill 题意： 三个容量分别为 \(a, b, c\) 的容器，初始状态只有 \(c\) 装满，\(a, b\) 都为空，需要计算出如何最少需要倒多少升水才能让其中某一个杯子中的水有 \(d\) 升。如果能够找到这样的 \(d\) ，你还是需要计算出其中某一个杯子达到 \(d\) 升时，最少需要倒多少升水。 数据范围： \(1\le a,b,c,d \le 200\) 。 把状态用 \((a,b,c)\) 表示，倒水就变成了一个最短路问题 难点是代码吧，需要理清思路再写。 时间复杂度 \(\mathcal{O}(n^3\log n)\) 代码： #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; } void down(int...

CF706D Vasiliy’s Multiset 题解 题目链接：CF706D Vasiliy’s Multiset 题意： 有 \(q\) 次操作和一个集合 \(A\) ，开始时集合中只有一个数 \(0\) ，下面有三种类型的操作： + x 把 \(x\) 插入集合 \(A\) 。 - x 把 \(x\) 从集合 \(A\) 中删去，保证 \(x\) 已存在于集合 \(A\) 中。 ? x 给一个数 \(x\) 在集合 \(A\) 中找一个 \(y\) 使得 \(x\operatorname{xor} y\) 最大，并求出这个值。 数据范围： \(1\leq q\leq 2\times 10^5,1\leq x_i\leq10^9\) 猫猫图镇楼（我一定要养一只这样的猫猫！） 考虑建一个 01trie 。插入操作就是一条线上都加个 \(1\) ，删除就是一条线上加个 \(-1\) 。 查询稍复杂一丢丢，设下一位为 \(c = 0,1\) ，我们看 \(\neg c\) 是否有数经过，有就往那走，这样一定能找到最大的。 时间复杂度 \(\mathcal{O}(n \l...

SP8547 MAIN74 - Euclids algorithm revisited 题解 题目链接：https://www.luogu.com.cn/problem/SP8547 题意： 我们经常用大名鼎鼎的欧几里得算法（辗转相除法）来计算两个数的最大公约数。 对于 \((7,3)\)，上述代码中的 while 循环将运行两次： \((7,3)\rightarrow(3,1)\rightarrow(1,0)\) 现在给你一个整数 \(N(0\le N\le10^{18})\)，你需要找出和最小的二元组 \((a,b)\) 满足 \((a\ge b\ge0)\) 且上面提到的代码 while 循环将恰好运行 \(N\) 次 原文： Consider the famous euclid algoithm to calculate the GCD of two integers \((a, b)\): int gcd(int a, int b) { while (b != 0) { int temp = a; a...

洛谷P7973 [KSN2021] Binary Land 题解 题目链接：P7973 [KSN2021] Binary Land 题意： 给定一张 \(N\) 个点的图，每个点有权值 \(A_i\) 和价值 \(B_i\)。 两个点 \(x,y\) 之间存在一条无向边当且仅当 \(A_x\text{ xor }A_y>\max(A_x,A_y)\)。 你需要对于 \(i=1,2,\cdots n\) 依次求出点 \(i\) 所在连通块中所有点的价值和。 输入格式： 第一行输入一个正整数 \(N\)。 第二行输入 \(N\) 个正整数 \(A_i\)。 第三行输入 \(N\) 个正整数 \(B_i\)。 输出格式： 输出 \(N\) 行，第 \(i\) 行包含一个整数，代表点 \(i\) 所在连通块中所有点的价值和。 数据范围： 对于所有数据，\(1 \leq N \leq 10^5\)，\(1 \leq A_i \leq 2^{30}-1\)，\(1 \leq B_i \leq 10^9\)。 根据常规套路，钦定 \(A_x \ge A_y\) ，则边 \((x,y)...