CF1592F2 Alice and Recoloring 2 题解
CF1592F2 Alice and Recoloring 2 题解 题目链接:Alice and Recoloring 2 题意: 本题与 CF1592F1 的差异在于花费不同。 给定一个 \(n\) 行 \(m\) 列的目标矩阵,矩阵元素只有 W 或 B ,并且你有一个初始矩阵,元素全为 W 。 现在你可以矩阵实施以下操作: 使用一块钱,选定一个包含 \((1,1)\) 的子矩阵,把矩阵中的元素全部反转( W 变 B , B 变 W )。 使用三块钱,选定一个包含 \((n,1)\) 的子矩阵,把矩阵中的元素全部反转。 使用四块钱,选定一个包含 \((1,m)\) 的子矩阵,把矩阵中的元素全部反转。 使用两块钱,选定一个包含 \((n,m)\) 的子矩阵,把矩阵中的元素全部反转。 现在需要你求出把初始矩阵变为目标矩阵最少需要几块钱。 输入格式: 第一行两个正整数 \(n\) 和 \(m (1 \le n,m\le 500)\) ,意义如上文所述。 接下来 \(n\) 行,每行 \(m\) 个字符 W 或 B 。意义如上文所述。 输出格式: 一行一个整数,表示把初始矩阵变...
CF1539F Strange Array 题解
CF1539F Strange Array 题解 题目链接:Strange Array 题意: \(\texttt{Vasya}\) 有一个长度为 \(n\) 的数组 \(a\)。 对于每一个元素 \(a_i\),进行一次以下操作,可以获得的最大值称为 \(a_i\) 的奇异值: 选取一对 \(l,r\) 使得 \(1\le l\le i\le r\le n\)。 将区间 \([l,r]\) 中的元素从小到大排序,如果有相同元素,则可以任意排列它们的位置。 记 \(a_i\) 现在的位置为 \(x\),定义序列中心 \(y\) 为 \(\lceil\frac{l+r}{2}\rceil\),则距离为 \(|x-y|\)。 请你帮助 \(\texttt{Vasya}\) 求出每一个元素的奇异值,注意每个元素之间互不影响。 数据范围: \(1\le n\le 2\times 10^5,~1\le a_i\le n\) 。 好像是套路题,但我不知道。考虑区间已经确定且 \(a_i\) 升序排序后如何求距离 \(\rm dis\) 。 记 \(a_{\rm mid}\) 为中位数...
CF935F Fafa and Array 题解
CF935F Fafa and Array 题解 题目链接:Fafa and Array 题意: 给出一个序列 \(a\),定义函数 \(f(a)=\sum_{i=1}^{n-1}|a_i-a_{i+1}|\)。 给出两种操作: \(\texttt{1 l r x}\),表示在区间 \([l,r]\) 内找一个位置, 使得把这个位置的值加上 \(x\) 后 \(f(a)\) 最大,求这个最大值(修改是临时的)。 \(\texttt{2 l r x}\),表示把区间 \([l,r]\) 加上 \(x\)。 输入格式 第一行一个正整数 \(n~(3 \le n \le 10^5)\) ,表示数组的长度。 第二行 \(n\) 个正整数 \(a_{1},a_{2},...,a_{n}~(0 < a_i \le 10^9)\) ,表示数组的元素。 第三行一个正整数 \(q~(1 \le q \le 10^5)\) ,表示询问的个数。 接下来 \(q\) 行,第 \(i\) 行有四个整数 \(t_i,l_i,r_i,x_i~(t_i \in\{1, 2\},\,1<l_i ...
CF1685C Bring Balance 题解
CF1685C Bring Balance 题解 题目链接:Bring Balance 题意: qry 有一个长度为 \(2n\) 的括号序列 \(s\),由 \(n\) 个左括号 ( 和 \(n\) 个右括号 ) 组成。她想把这个括号序列变成一个平衡括号序列。 平衡括号序列定义为:能通过插入字符 + 和 1 使之成为合法数学表达式的序列。例如,序列 (())()、() 和 (()(())) 是平衡的,而 )(、(() 和 (()))( 就不是的。 在一次操作中,她可以反转 \(s\) 的任意子串。 请求出最少几次操作可将 \(s\) 转换为平衡括号序列。可以证明,这总是能在 \(n\) 次操作中完成。 输入格式: 本题有多组数据。 第一行一个整数 \(t\)(\(1 \le t \le 2 \cdot 10^4\)),表示数据组数。 每组数据格式如下: 第一行一个整数 \(n\)(\(1 \le n \le 10^5\)),含义如上所述。 第二行为一个长度为 \(2n\) 的括号序列,由 \(n\) 个左括号 ( 和 \(n\) 个右括号 ) 组成。 在一个测试点中,所有...
CF1391E Pairs of Pairs 题解
CF1391E Pairs of Pairs 题解 题目链接:Pairs of Pairs 题目描述: 给定一个包含 \(n\) 个节点和 \(m\) 条边的简单连通无向图。 现在考虑将这 \(n\) 个节点中的某些节点两两配对,要求任意一个节点最多只能属于一个配对。 如果对于任意两对配对 \((a, b)\) 和 \((c, d)\),由这四个节点 \(\{a, b, c, d\}\) 构成的诱导子图中,最多只有 \(2\) 条边(在 \(6\) 条可能的边中),则称该配对是合法的。 请注意,诱导子图指的是仅包含该节点集合中的节点,以及两端都在该集合内的边的子图。 现在,请完成以下两种操作之一: 找出一条包含至少 $ $ 个节点的简单路径。这里的简单路径指的是不会重复经过任何节点的路径。 找出一个合法配对,使得至少有 $ $ 个节点被配对。 可以证明,对于满足题目条件的任意图,至少可以完成上述两种操作之一。 输入格式: 每个测试点包含多个测试用例。第一行包含一个整数 \(t\)(\(1 \le t \le 10^5\)),表示测试用例的数量。接下来是每个测试用例的描述。 ...
CF1348F Phoenix and Memory 题解
CF1348F Phoenix and Memory 题解 题目链接:Phoenix and Memory 题意: qry 有 \(n\) 个朋友,朋友们的编号是 \(1\sim n\)。他的朋友们本来按某种特殊顺序排成一排,但 qry 还没来得及按下快门,就有一只鸭子乱入,把原本排好的顺序搞得乱七八糟。 现在,qry 不得不重新排好顺序,但他记不清了QAQ!他只记得从左数起的第 \(i\) 个朋友的编号大小在 \(a_i\) 和 \(b_i\) 之间。该怎么办?他只好向你请教。请问根据他的记忆有没有唯一一种方法给他的朋友们排序? 形式化的,给定 \(a_i,b_i\) ,问是否存在唯一长 \(n\) 的排列 \(p\) ,满足 \(a_i \leq p_i \leq b_i\) 。 数据保证至少有一个符合题意的排列。 输入格式 第一行一个整数 \(n~(1 \leq n \leq 2 \times 10^5)\),表示 qry 的朋友数。 接下来 \(n\) 行,第 \(i\) 行两个整数 \(a_i\) 和 \(b_i~(1 \leq a_i \leq b_i \leq n...
洛谷P5362 [SDOI2019] 连续子序列 题解
洛谷P5362 [SDOI2019] 连续子序列 题解 题目链接:P5362 [SDOI2019] 连续子序列 题意: 我们定义 \(\textbf{T. M.}\) 序列\(\{T_n\}\)为如下形式得布尔序列: \[ \begin{aligned} & T_0 = 0 \\[6pt] & T_{2n} = T_n \\[6pt] & T_{2n+1} = 1 - T_n \end{aligned} \] 这里我们给出 \(\textbf{T. M.}\) 序列的前若干项 \[ 01101001100101101001011001101001\cdots \] \(\textbf{T. M.}\) 序列是一个无限长度的序列,它有很多连续子序列。 例如 \(0,~1,~10100,~10011\) 和 \(011001\) 都是它的连续子序列,然而 \(111\) 和 \(1000\) 却不是它的连续子序列。 现在给定一个布尔序列(01字符串)\(S\) 和一个非负整数 \(k\),请统计一下一共有多少种 \(\textbf{T. M.}\) 序列的连...
洛谷P7606 [THUPC2021] 混乱邪恶 题解
洛谷P7606 [THUPC2021] 混乱邪恶 题解 题目链接:P7606 [THUPC2021] 混乱邪恶 题意: 给你一个蜂窝网络,你初始在坐标 \((0,0)\) 。这个网络中每个交叉点共有 \(6\) 个相邻的交叉点 共有两种属性 \(L,R\) (守序值和善良值),初始为 \(0\) ,均在\(\bmod p\) 意义下存在。 现在有 \(n\) 张卡片,第 \(i\) 张使用后可以选择向任意方向(\(6\) 个方向)前进一步。 如果向 \(j\) 方向前进,则会使得 \(L\gets L+l_{i,j},\,R\gets R + r_{i,j}\) (在\(\bmod p\) 意义下)。 问是否有一种方案使得自己最后能够回到 \((0,0)\) 且 \(L=L_0,R=R_0\) 。 输入格式: 第一行两个正整数 \(n,p\)。 接下来 \(n\) 行,每行 \(2\times 6\) 个非负整数 \(l_{i,j},r_{i,j}~(1 \le j \le 6)\)。 最后一行两个非负整数 \(L_0,R_0\)。 输出格式: 如果能,输出一行 Chaot...
CF1493E Enormous XOR 题解
CF1493E Enormous XOR 题解 题目链接:Enormous XOR 题意: 定义 \(g(x,y) = x \oplus (x+1) \oplus \dots \oplus (y-1) \oplus y\) 。 设 \(f(l,r)\) 为所有满足 \(l\leq x\leq y\leq r\) 的 \(g(x,y)\) 的最大值。 先给出 \(l,r\) 的二进制形式,求 \(f(l,r)\) 。 数据范围: \(1 \le n \le 10^6\) 。其中 \(n\) 是 \(l,r\) 二进制下的位数。 找规律猜结论题。 注意到如果 \(l,r\) 的位数不同,答案必定为 \(2^n-1\) ,令 \(x=2^{n-1}-1,\,y=2^{n-1}\) 即可 接下来考虑 \(l,r\) 位数相同的情况。这里有一个结论,当 \(x\) 是偶数时,\(x \oplus (x + 1)=1\) 。 于是 \(\bigoplus_{i=0}^{2k+1}(x + i)\) 的值为 \(0\) ,因为两两相互抵消了。考虑利用这个性质。 可以证明,原题的答案的取值只...
CF627D Preorder Test 题解
CF627D Preorder Test 题解 题目链接:Preorder Test 题意: 为了她的计算机科学课程,qry 用小棍和小球构建了一个包含 \(n\) 个节点的树模型。qry 花了 \(a_{i}\) 分钟构建树中的第 \(i\) 个小球。 qry 的老师会评估她的模型,并根据她投入的努力给她打分。然而,老师没有足够的时间来检查整个树以确定这些。qry 知道老师将会检查树的前 \(k\) 个节点(按 dfs 序先序遍历树)。然后他会根据这 \(k\) 个节点中发现的最小 \(a_{i}\) 给 qry 打分。 虽然 qry 没有足够的时间重建她的模型,但她可以选择老师开始检查的根节点。此外,她可以以任何顺序重新排列每个节点的邻居列表。请帮助 qry 在这次作业中获得最佳分数。 输入格式: 输入的第一行包含两个正整数,\(n\) 和 \(k~(2 \leq n \leq 2\times 10^5,~1 \leq k \leq n)\) ,表示 qry 的树中的小球数量和老师将检查的小球数量。 第二行包含 \(n\) 个整数,\(a_{i}~(1 \leq a_{i}...
note[20]
note[20] 题: \[ \min \left\{\left.k^4+3 k^2+3+\frac{1}{k^2} \right\rvert\, 0<k \leq 1\right\} \] 解: 记 \(f(k) = k^4+3 k^2+3+\frac{1}{k^2}\) ,其中 \(k \in (0,1]\) ,那么 \[ \frac{\mathrm{d} }{\mathrm{d}k}f = 4k^3 + 6k - \frac{2}{k^3} \] 那么最小值就在 \(f^{\prime}(k)=0\) 的地方,解一下方程 \[ \begin{aligned} 4k^3 + 6k - \frac{2}{k^3} &= 0 \\[6pt] 2 k^6+3 k^4-1&=0 \end{aligned} \] 记 \(x = k^2\) ,那么式子变为 \[ 2 x^3+3 x^2-1=0 \] 考虑用有理根定理来找到可能的有理根。 有理根定理:如果一个多项式存在有理根 \(\frac{p}{q}\),那么 \(p\) 是常数项的因数,\(q\) 是最高次项系...
AT_agc027_d [AGC027D] Modulo Matrix 题解
AT_agc027_d [AGC027D] Modulo Matrix 题解 题目链接:AT_agc027_d [AGC027D] Modulo Matrix 题意: 构造一个 \(N\times N\) 的矩阵. 要求: 所有元素 \(a_{i,j}\) 互不相同。 满足 \(1\le a_{i,j}\leq 10^{15}\)。 对于任意相邻(上下左右)的数字 ,\(\max(x,y)\bmod \min(x,y)\) 都相等,且均为正整数。 可以证明方案一定存在。 数据范围: \(2 \le N \le 500\) 。 简单跑一跑暴力就会发现符合条件的情况还是很多的 容易想到一种构造,如果 \((i + j) \bmod 2=0\) ,就比较随便的填一个数 否则填周围四个相邻格子的最小公倍数 \(+1\) ,即 \(a_{i,j} = \operatorname{lcm}\left(a_{i-1, j}, a_{i, j-1}, a_{i+1, j}, a_{i, j+1}\right)+1\) 这样子随便搞的话值域大约为 \(\mathcal{O}(n^8)\) ...






![洛谷P5362 [SDOI2019] 连续子序列 题解](/qwq/img/p113.webp)
![洛谷P7606 [THUPC2021] 混乱邪恶 题解](/qwq/img/p146.webp)


![note[20]](/qwq/img/p145.webp)
![AT_agc027_d [AGC027D] Modulo Matrix 题解](/qwq/img/p8.webp)


![洛谷B3883 [信息与未来 2015] 求回文数(加强版) & B3882 题解](/qwq/img/p214.webp)
![洛谷B3879 [信息与未来 2015] 连续数的和(加强版) & B3878 题解](/qwq/img/p230.webp)