Q779’s Blog

CF1141F2 Same Sum Blocks (Hard) 题解 题目链接：CF1141F2 Same Sum Blocks (Hard) 题意： 这个问题有两个版本，它们唯一的不同之处在于对数值 \(n\) 的约束。 给定一个整数数组 \(a_1,a_2,\ldots,a_n\)。一个块是由连续的元素 \(a_l, a_{l+1}, \ldots, a_r\) （\(1 \leq l \leq r \leq n\)）构成的序列。因此，一个块由一对索引 \((l, r)\) 定义。 找到一组块 \((l_1, r_1), (l_2, r_2), \ldots, (l_k, r_k)\)，使得： 它们不相交（即它们是不相交的）。形式化地，对于每对块 \((l_i, r_i)\) 和 \((l_j, r_j)\)（其中 \(i \neq j\)）要么 \(r_i < l_j\)，要么 \(r_j < l_i\)。 对于每个块，其元素的总和相等。形式化地，\(a_{l_1} + a_{l_1+1} + \ldots + a_{r_1} = a_{l_2} + a_{...

UVA12299 RMQ with Shifts 题解 题目链接：UVA12299 RMQ with Shifts 题意： 萌妹纸 cxy 想要维护一个数据结构，支持以下操作（询问由字符串给出）： shift(a,b,c...) 该字符串表示把位于 \(\langle a,b,c\cdots\rangle\) 的数移动为 \(\langle b,c\cdots,a \rangle\) query(l,r) 该字符串表示查询 \([l,r]\) 的最小值。 因为 cxy 忙着和妹纸玩，所以这个任务就交给你啦！ 数据范围： \(1\le n,q\le 10^5\) ，询问字符串的长度不超过 \(30\) 。 注意到询问的字符串长度不超过 \(30\) ，因此需要移动的位置在 \(10\) 个左右，记为 \(\varepsilon\) 我们直接维护一个单点修改的线段树，然后把每个要移动的位置改一下值就好了 时间复杂度 \(\mathcal{O}(\varepsilon n \log n)\) 代码：（摘自参考文献[1]） #include <bits/stdc++.h> ...

[ARC119C] ARC Wrecker 2 题解 题目链接：[ARC119C] ARC Wrecker 2 题意： 在 AtCoder 街道上有 \(N\) 座建筑物，从西到东编号为 \(1\) 到 \(N\)。初始时，建筑物 \(1, 2, \ldots, N\) 的高度分别为 \(A_1, A_2, \ldots, A_N\)。 cxy 是 ARC Wrecker 公司的总裁，她计划选择整数 \(l\) 和 \(r\) \((1 \leq l < r \leq N)\)，并使得建筑物 \(l, l+1, \ldots, r\) 的高度全部变为 \(0\)。为了达成这个目标，她可以任意次数任意顺序地使用以下两种操作： 设置一个整数 \(x\) \((l \leq x \leq r-1)\) 并使得建筑物 \(x\) 和 \(x+1\) 的高度各增加 \(1\)。 设置一个整数 \(x\) \((l \leq x \leq r-1)\) 并使得建筑物 \(x\) 和 \(x+1\) 的高度各减少 \(1\)。这种操作仅当这两座建筑物的高度都大于等于 \(1\) 时才...

CF1737D Ela and the Wiring Wizard 题解 题目链接：CF1737D Ela and the Wiring Wizard 题意： Ela 需要通过机器网络，从机器 \(1\) 发送一个大型包裹到机器 \(n\)。目前，由于网络条件不好，她抱怨网络太慢，包裹无法及时到达。幸运的是，一位电线向导向她伸出了援手，据说叫cxy。 网络可以用一个无向连通图表示，其中有 \(n\) 个节点，每个节点代表一台机器。用 \(m\) 条电线连接它们。第 \(i\) 条电线用于连接机器 \(u_i\) 和 \(v_i\)，并具有权重 \(w_i\)。如果大型包裹经过第 \(i\) 条电线，则会在恰好 \(w_i\) 微秒内从机器 \(u_i\) 移动到机器 \(v_i\)（或反之亦然）。电线向导可以随意使用她的魔法，对于每个魔法，她将选择连接机器 \(u_i\) 和 \(v_i\) 的第 \(i\) 条电线，并按照以下步骤重新布线： 选择一个与此电线连接的机器。不失一般性，假设我们选择 \(v_i\)。 选择一个当前连接到 \(v_i\) 的机器（包括 \(u_i\...

[ARC133C] Row Column Sums 题解 题目链接：[AGC004D] Teleporter 题意： 我们有一个 \(H\) 行 \(W\) 列的网格。 Snuke 要在每个格子里写一个介于 \(0\) 和 \(K-1\) 之间的整数。必须满足以下条件： 对于每个 \(1 \le i \le H\)，第 \(i\) 行的整数之和对 \(K\) 取模的结果为 \(A_i\)。 对于每个 \(1 \le i \le W\)，第 \(i\) 列的整数之和对 \(K\) 取模的结果为 \(B_i\)。 确定是否可能在方格中写入整数以满足条件。如果可能，还需找到所写整数的最大可能和。 输入格式： \(H~W~K\) \(A_{1}~A_{2}~\cdots~A_{H}\) \(B_{1}~B_{2}~\cdots~B_{W}\) 输出格式： 如果不可能在方格中写入整数以满足条件，则输出 -1。如果可能，输出所写整数的最大可能和。 数据范围： \(1 \le H, W \le 2\times10^5,~2 \le K \le 2\times 10^5,~0 \le A_i ...

[AGC004D] Teleporter 题解 题目链接：[AGC004D] Teleporter 题意： cxy 王国中有 \(N\) 个城镇，方便地从 \(1\) 到 \(N\) 编号。城镇 \(1\) 是首都。 该王国中的每个城镇都有一个传送门，该设施可立即将人传送到另一个地方。城镇 \(i\) 的传送门的目的地是城镇 \(a_i\)（\(1\leq a_i\leq N\)）。保证可以通过使用传送门从任何城镇到达首都。 国王 cxy 喜欢整数 \(K\)。自私的国王希望更改传送门的目的地，以满足以下条件： 从任何城镇开始，使用传送门正好 \(K\) 次后，将到达首都。 找到需要更改目的地的传送门的最小数量，以满足国王的愿望。 输入格式： 输入以以下格式从标准输入中给出： \(N\) \(K\) \(a_1\) \(a_2\) … \(a_N\) 数据范围： \(2\leq N\leq 10^5,~1\leq a_i\leq N,~1\leq K\leq 10^9\) 数据保证可以通过使用传送门从任何城镇到达首都。 输出格式： 输出需要更改目的地的传送门的最小数量，以满足 ...

SP279 INUMBER - Interesting number 题解 题目链接：INUMBER - Interesting number 题意： 对于给定的数 \(n\)，求出能被 \(n\) 整除的最小正整数，其位数之和为 \(n\)。 输入格式： 第一行，输入一个整数 \(T\)，是测试用例的数量。 接下来的 \(T\) 行，每行输入一个整数 \(n\) 。 输出格式： 共 \(T\) 行，答案。 数据范围： \(1 \le T \le 50,~1 < n \le 10^3\) 。 这个题貌似是05年的题，比 cxy 还大。 （但是 cxy 是萌妹子/oh） 看上去就是个搜索题。考虑 bfs 。记状态 \((x,y)\) 表示当前位数的和为 \(x\) ，实际数\(\bmod n\) 的值为 \(y\) 。 初始状态 \((0,0)\) ，我们需要的是 \((n,0)\) 。其实还是蛮套路的，主要考察的就是模 \(n\) 这个优化。 时间复杂度 \(\mathcal{O}(n^2)\) 代码： #include <bits/stdc++.h> using...

AT_jag2017autumn_c Prime-Factor Prime 题解 题目链接：C - Prime-Factor Prime 题意： 设正整数 \(x\) 的质因数分解式为 \(x=\prod_{i=1}^k p_i^{\alpha_i}\) 。定义 \(f(x)=\sum_{i=1}^k \alpha_i\) 。 给出 \(l, r\) ，求对所有 \(i \in[l, r]\) ，有多少 \(f(i)\) 是质数。 \(1 \leq l \leq r \leq 10^9,~ 0 \leq r-l<10^6\) 。 注意到 \(r - l < 10^6\) ，但是直接枚举然后暴力拆的复杂度过于高了。 容易发现一个数的质因数个数最多有 \(\log_2 x\) 个，则若从质因数的角度出发可以节省很多时间。 套路地，筛出 \(2\) 到 \(\sqrt{10^9}\) 的所有质数，然后对于每个质数暴力计算贡献。 时间复杂度 \(\mathcal{O}((r - l) \log r)\) 代码： #include <bits/stdc++.h> us...

洛谷P3045 [USACO12FEB]Cow Coupons G 题解 题目链接：P3045 [USACO12FEB]Cow Coupons G 题意： FJ 准备买一些新奶牛。市场上有 \(N\) 头奶牛，第 \(i\) 头奶牛价格为 \(P_i\)。FJ 有 \(K\) 张优惠券，使用优惠券购买第 \(i\) 头奶牛时价格会降为 \(C_i\)，当然每头奶牛只能使用一次优惠券。FJ 想知道花不超过 \(M\) 的钱最多可以买多少奶牛？ \(1 \le K \le N \le 5 \times 10^4,~1 \le C_i \le P_i \le 10^9,~1 \le M \le 10^{14}\) 这种贪心题还是比较经典的反悔型贪心。 首先我们先把上界算出来，也就是选 \(k\) 个最小的 \(C_i\) ，然后在剩下的 \(P_i\) 里选 \(n-k\) 个最小的。 考虑如何更新答案。我们实际上只有一种选择：原价买 \(x\) ，并把 \(x\) 用了的优惠券用于买新的 那么这个 \(x\) 怎么选合适呢？肯定优先选优惠力度小的啊！也就是 \(P_i-C_i\)...

洛谷P7114 [NOIP2020] 字符串匹配 题解 题目链接：P7114 [NOIP2020] 字符串匹配 题意： cxy 和妹纸一起学习完了字符串匹配的相关内容，现在她正在做一道习题。 对于一个字符串 \(S\)，题目要求她找到 \(S\) 的所有具有下列形式的拆分方案数： \(S = ABC\)，\(S = ABABC\)，\(S = ABAB \ldots ABC\)，其中 \(A,B,C\) 均是非空字符串，且 \(A\) 中出现奇数次的字符数量不超过 \(C\) 中出现奇数次的字符数量。 更具体地，我们可以定义 \(AB\) 表示两个字符串 \(A,B\) 相连接，例如 \(A = \texttt{aab}\)，\(B = \texttt{ab}\)，则 \(AB = \texttt{aabab}\)。 并递归地定义 \(A^1=A\)，\(A^n = A^{n - 1} A\)（\(n \ge 2\) 且为正整数）。例如 \(A = \texttt{abb}\)，则 \(A^3=\texttt{abbabbabb}\)。 则 cxy 的习题是求 \(S = {(...

洛谷P1043 [NOIP2003 普及组] 数字游戏 题目链接：P1043 [NOIP2003 普及组] 数字游戏 题意： cxy 最近沉迷于一个数字游戏之中。这个游戏看似简单，但 cxy 在研究了许多天之后却发觉原来在简单的规则下想要赢得这个游戏并不那么容易。游戏是这样的，在你面前有一圈整数（一共 \(n\) 个），你要按顺序将其分为 \(m\) 个部分，各部分内的数字相加，相加所得的 \(m\) 个结果对 \(10\) 取模后再相乘，最终得到一个数 \(k\)。游戏的要求是使你所得的 \(k\) 最大或者最小。 例如，对于下面这圈数字（ \(n=4,~m=2\) ）： 要求最小值时，\(((2-1)\bmod10)\times ((4+3)\bmod10)=1\times 7=7\)，要求最大值时，为 \(((2+4+3)\bmod10)\times (-1\bmod10)=9\times 9=81\)。特别值得注意的是，无论是负数还是正数，对 \(10\) 取模的结果均为非负值。 cxy 请你编写程序帮他赢得这个游戏。 输入格式： 输入文件第一行有两个整数，\(n\)...

CF603A Alternative Thinking 题解 题目链接：CF603A Alternative Thinking 题意： 现有一个长度为 \(n\) 的 01 串, 可以进行一次区间翻转 ( 起点终点随意, 并且区间里的值 1 变 0, 0 变 1 ), 得到一个新的 01 串, 使得得到的新的 01 串中的一个子串最长 (子串不一定连续), 且这个子串是 01 间隔的，没有连续两个字符相同。比如 0101 , 101 和1010 是合法的, 100, 1100 是不合法的。试求翻转后最长 01 间隔子串的长度. 输入格式： The first line contains the number of questions on the olympiad \(n ~(1\le n \le 10^5)\). The following line contains a binary string of length \(n\) representing Kevin’s results on the USAICO. 输出格式： Output a single integer...