Q779’s Blog

CF1391E Pairs of Pairs 题解 题目链接：Pairs of Pairs 题意： 给出一张无向连通图，选择以下任意一个任务完成： 找到图中一条至少包含 \(\lceil \frac {n} {2} \rceil\) 个点的简单路径。 找到图中偶数（至少 \(\lceil \frac {n} {2} \rceil\) ）个点，满足任意两个点对包含的 \(4\) 个点的导出子图至多存在 \(2\) 条边。 若完成任务 \(1\)，则输出 PATH，并输出简单路径包含的点数与该路径依次经过的点。 若完成任务 \(2\)，则输出 PAIRING，并输出选出的点对数及每一组点对。 可以证明，符合条件的一张图一定可以完成其中一个任务。 输入格式： 每个测试包含多个测试用例。 第一行包含测试用例的数量 \(t~(1 \le t \le 10^5)\) 。接下来是每个测试用例的描述。 每个测试用例的第一行包含两个整数 \(n, m~(2 \le n \le 5 \times 10^5,1 \le m \le 10^6)\)，分别表示节点数和边数。 接下来的 \(m\) 行...

CF1348F Phoenix and Memory 题解 题目链接：Phoenix and Memory 题意： cxy 有 \(n\) 个朋友，朋友们的编号是 \(1\sim n\)。他的朋友们本来按某种特殊顺序排成一排，但 cxy 还没来得及按下快门，就有一只鸭子乱入，把原本排好的顺序搞得乱七八糟。 现在，cxy 不得不重新排好顺序，但他记不清了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)\)，表示 cxy 的朋友数。 接下来 \(n\) 行，第 \(i\) 行两个整数 \(a_i\) 和 \(b_i~(1 \leq a_i \leq b_i \leq n...

洛谷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] 混乱邪恶 题意： 给你一个蜂窝网络，你初始在坐标 \((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 题解 题目链接：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 题解 题目链接：Preorder Test 题意： 为了她的计算机科学课程，cxy 用小棍和小球构建了一个包含 \(n\) 个节点的树模型。cxy 花了 \(a_{i}\) 分钟构建树中的第 \(i\) 个小球。 cxy 的老师会评估她的模型，并根据她投入的努力给她打分。然而，老师没有足够的时间来检查整个树以确定这些。cxy 知道老师将会检查树的前 \(k\) 个节点（按 dfs 序先序遍历树）。然后他会根据这 \(k\) 个节点中发现的最小 \(a_{i}\) 给 cxy 打分。 虽然 cxy 没有足够的时间重建她的模型，但她可以选择老师开始检查的根节点。此外，她可以以任何顺序重新排列每个节点的邻居列表。请帮助 cxy 在这次作业中获得最佳分数。 输入格式： 输入的第一行包含两个正整数，\(n\) 和 \(k~(2 \leq n \leq 2\times 10^5,~1 \leq k \leq n)\) ，表示 cxy 的树中的小球数量和老师将检查的小球数量。 第二行包含 \(n\) 个整数，\(a_{i}~(1 \leq a_{i}...

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\) 是最高次项系...

[AGC027D] Modulo Matrix 题解 题目链接：[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)\) ，过不了。 注意到 \(\operatornam...

CF512E Fox And Polygon 题解 题目链接：Fox And Polygon 题意： 狐狸 Ciel 设计了一种叫“多边形”的智力游戏！它是通过把一个 \(n\) 边形分成三角形来进行的。 目标是通过一些复杂的规则把一种分法转换成另一种分法。 \(n\) 边形的一种“分法”是 \(n - 3\) 条不相交的对角线构成的集合。 每一步可以选择一条对角线（但不能是 \(n\) 边形的边）然后翻转这条对角线。 对于一条对角线 \(AB\) ，假设它的两边分别是 \(\triangle ABC\) 和 \(\triangle ABD\) 。 “翻转”对角线 \(AB\) ，就是删除对角线 \(AB\) ，并添加对角线 \(CD\) 。 Ciel 证明了对于任何一个起点和终点都有合法的翻转方式 她想让你对于任何一个 \(n \le 1000\) 的局面，在 \(20000\) 次操作内完成。 输入格式 第一行是一个整数 \(n\)， 表示多边形的边数。 接下来 \(n - 3\) 行， 每一行有两个正整数 \(A_i\) 和 \(B_i\) ，表示开始有对角线 \(A_...

洛谷P4639 [SHOI2011] 编译优化 题解 题目链接：P4639 [SHOI2011] 编译优化 题意： 就像 PASCAL 语言和 C/C++ 语言一样， SH 语言也是一种编程语言。 SH 语言共有 \(26\) 个寄存器，用大写拉丁字母 A, B, … , Z 表示。 SH 语言的程序中，第一行依次是这 \(26\) 个寄存器的初始值，用空格分隔。程序的第二行起，每一行都是一条命令。 SH 语言有三种命令，如下表所示（在格式这一列中，用下划线代替实际语言中的一个空格）。 ADD命令 格式：ADD_R1_R2 功能：将寄存器 R2 的值加到寄存器 R1 上。 限制：无。 GOTO 命令 格式：IF _R_ < _I1_ GOTO _LINE_ I2 功能：如果寄存器 R 的值小于立即数 I1 ，则跳转至第 I2 （ \(\ge 2\) ）行，否则继续执行下一行。限制：至多出现一次，且只可能出现在第 I2 行之后。 PRINT 命令 格式：PRINT_R 功能：打印寄存器 R 的值。限制：出现且仅出现在最后一行。 现给定一个 SH 语言的程序，请输出 PR...

洛谷B3704 [语言月赛202301] HACK IT! 题解 题目链接：B3704 [语言月赛202301] HACK IT! 题意： 本题是提交答案题。 给你三道题和三个错误的程序，请你构造数据 hack 掉他们。 问题1： 给定两个整数 \(a, b\) ，请求出 \(a + b\) 的值。 问题2： 给定一个仅包含小写字母的字符串 \(s\)，求 \(s\) 中有多少个小写 a 字母。 问题3： 给定一个长度为 \(n\) 的数组 \(a\)（下标从 \(0\) 开始） 对所有的 \(i\) 满足 \(0 \leq i < n\)，设 \(b_i = a_{i + 1 \bmod n} - a_i\) ，请求出 \(b\) 数组。 代码1： #include <iostream> using namespace std; int main() { int a, b; cin >> a >> b; cout << a + b << endl; } 代码2： #include <cstring>...

洛谷P9659 [ICPC2021 Macao R] Shortest Path Fast Algorithm 题解 题目链接：P9659 [ICPC2021 Macao R] Shortest Path Fast Algorithm 题意： 最近，cxy 学习了最短路径快速算法（SPFA，或更正式地说，贝尔曼–福特–摩尔算法）以有效地解决最短路径问题。她意识到，如果用优先队列代替先进先出队列，该算法看起来与 Dijkstra 算法非常相似，并向你展示了下面的伪代码。 「选择 \(Q\) 中最佳顶点」表示选择具有最小 priority 值的顶点（如果有多个顶点具有最小 priority 值，则选择其中索引最大的顶点）。 作为未来的计算机科学家，你发现 cxy 修改后的 SPFA 算法在某些精心构造的图中运行速度非常慢。然而，cxy 确信她的算法很好，除非你向她展示一个简单的无向图，在该图中，SPFA 函数中的变量 \(\tt{cnt}\) 在某个时刻不少于某个 \(k\)。为方便起见，SPFA 函数的源顶点被指定为顶点 \(1\)。 就给她个教训吧！ 输入格式： 每个测试文件...