CF512E Fox And Polygon 题解
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] 编译优化 题解 题目链接: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! 题解 题目链接: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 题解 题目链接:P9659 [ICPC2021 Macao R] Shortest Path Fast Algorithm 题意: 最近,qry 学习了最短路径快速算法(SPFA,或更正式地说,贝尔曼–福特–摩尔算法)以有效地解决最短路径问题。她意识到,如果用优先队列代替先进先出队列,该算法看起来与 Dijkstra 算法非常相似,并向你展示了下面的伪代码。 「选择 \(Q\) 中最佳顶点」表示选择具有最小 priority 值的顶点(如果有多个顶点具有最小 priority 值,则选择其中索引最大的顶点)。 作为未来的计算机科学家,你发现 qry 修改后的 SPFA 算法在某些精心构造的图中运行速度非常慢。然而,qry 确信她的算法很好,除非你向她展示一个简单的无向图,在该图中,SPFA 函数中的变量 \(\tt{cnt}\) 在某个时刻不少于某个 \(k\)。为方便起见,SPFA 函数的源顶点被指定为顶点 \(1\)。 就给她个教训吧! 输入格式: 每个测试文件...
P9510 题解插图及源码
P9510 题解插图及源码 题解链接:洛谷P9510 「STA - R3」高维立方体 题解 插图一 源码: \documentclass{standalone} \usepackage{tikz} \begin{document} \begin{tikzpicture} \draw[->] (0, 0) -- (6, 0); \draw[->] (0, 0) -- (0, 9); \node[below = 4pt, left] at (0, 0) { $O$ }; \node[below] at (6, 0) { $x$ }; \node[left] at (0, 9) { $y$ }; \draw[very thin, color = gray] (0, 9) grid (6, 0); \draw[blue, line width = 1pt] (0, 0) -- (5, 0)...
洛谷P9510 「STA - R3」高维立方体 题解
洛谷P9510 「STA - R3」高维立方体 题解 题目链接:P9510 「STA - R3」高维立方体 题意: 如下定义斐波那契数列: \[ \operatorname{fib}(n)=\begin{cases}1&n\le 2\\\operatorname{fib}(n-1)+\operatorname{fib}(n-2)&n>2\end{cases} \] 现在我们定义一个函数(注意在 \(n<1\) 时这个函数的值是 \(0\) ): \[ f(n)=\sum_{i=1}^n\operatorname{fib}^2(i) \] 由于求斐波那契数列的前缀和太简单了,你需要求出: \[ \sum_{i=1}^n\operatorname{fib}(i)\cdot(f(i-2)+\operatorname{fib}^2(i)+\operatorname{fib}(i)) \] 的值,答案对输入的 \(p\) 取模。 注:\(\operatorname{fib}^2(x)\) 表示 \(\operatorname{fib}(x)\) 的平方。 输入...
CF1957F2 Frequency Mismatch (Hard Version) 题解
CF1957F2 Frequency Mismatch (Hard Version) 题解 题目链接:Frequency Mismatch (Hard Version) 题意: 给定一棵 \(n\) 个点的树,每个点 \(v\) 有颜色 \(a_v\)。 现在有 \(Q\) 次询问,每次给出两条路径 \(u_1\leadsto v_1\) 和 \(u_2\leadsto v_2\) 还有一个数 \(K\),令 \(x_c\) 为颜色 \(c\) 在路径 \(u_1\leadsto v_1\) 上出现的次数,\(y_c\) 为颜色 \(c\) 在路径 \(u_2\leadsto v_2\) 上出现的次数,请列出 \(K\) 个颜色 \(c\) 满足 \(x_c\neq y_c\),如果不满 \(K\) 个则全部列出。 数据范围: \(1\le n\le 10^5,1\le a_i\le 10^5,1\le Q\le 10^5,1\le K\le 10\)。 经典的 sum hash ,不知道可以看这篇 考虑给每个点随机赋一个权值,然后在树上建立主席树,维护到根节点的链上所有权...
CF1201E2 Knightmare (hard) 题解
CF1201E2 Knightmare (hard) 题解 题目链接:Knightmare (hard) 题意: 本题是交互题。 Alice 和 Bob 在 \(n \times m\) 的国际象棋棋盘上下棋,\(n,m\) 都是偶数。 棋盘上有一个黑棋 \(\unicode{x265E}\) 和一个白棋 \(\unicode{x2658}\) ,白棋先手,走法同国际象棋中的骑士(同中国象棋的马)。 现在双方要将棋子跳到目标点。白棋的目标点是 \(\left(\frac{n}{2}, \frac{m}{2}\right)\),黑棋的目标点是 \(\left(\frac{n}{2} + 1, \frac{m}{2}\right)\)。 游戏胜利的条件如下: 棋子到达了目标点,且当前对方棋子不能攻击到目标点。 吃掉了对方的棋子。 如果 \(350\) 回合后游戏未结束,则视为平局。 请你帮助 Alice 选择黑棋 \(\unicode{x265E}\) 或白棋 \(\unicode{x2658}\) 以赢得这场游戏。可以证明一定 Alice 存在必胜策略。 交互格式: 读入 \...
CF1580B Mathematics Curriculum 题解
CF1580B Mathematics Curriculum 题解 题目链接:Mathematics Curriculum 题意: 求长度为 \(n\) 且恰好有 \(K\) 个 \(m\) – 好数 的排列个数: 称一个数是 \(m\) – 好数 当且仅当 所有包含这个数的区间中,不同的最大值的个数恰有 \(m\) 个。 答案对 \(P\) 取模。 输入格式 第一行给出四个整数 \(n, m, K, P~(1 \le n \le 100, 1 \le m \le n, 1 \le K \le n, 1 \le P \le 10^9)\) 输出格式 输出方案数模 \(P\) 的结果。 设 \(f(i,j,k)\) 表示长度为 \(i\) 且恰好有 \(j\) 个 \(k\) – 好数的方案数。考虑转移。 枚举最大值的位置 \(p\) ,那么划分方案数等于剩下的 \(i-1\) 个数里选 \(p-1\) 个放到左侧(内部顺序不考虑) 由于跨越 \(p\) 的区间都会吃到 \(p\) 给的贡献 \(1\) ,所以我们要从 \((k-1)\) – 好数转移,那么 \[ f(i, ...
CF961F k-substrings 题解
CF961F k-substrings 题解 题目链接:k-substrings 题意: 给定一个长度为 \(n\) 的字符串 \(S\) 对于 \(1 \le j \le \left\lceil\frac{n}{2}\right\rceil\) ,求 \(S[k,\, n-k+1]\) 的最长且长度为奇数的 border 的长度。 输入格式: 输入的第一行是一个整数 \(n(2 \le n \le 10^6)\),表示字符串的长度。 输入的第二行是一个长度为 \(n\) 的字符串。 输出格式: 输出 \(\lceil \frac n 2 \rceil\) 个数,其中第 \(i\) 个数为 满足 \(t\) 是 \(i\) 子串的前缀和后缀的字符串 \(t\) 的最大长度。 设 \(f_i\) 为 \(k=i\) 时的答案,那么显然有 \(f_i \le f_{i + 1} + 2\) 于是我们只需要把 \(k\) 从大到小枚举并用字符串哈希计算 \(f\) 即可。 时间复杂度 \(\mathcal{O}(n)\) 代码: #include <bits/stdc++.h...
CF1185G2 Playlist for Polycarp (hard version) 题解
CF1185G2 Playlist for Polycarp (hard version) 题解 题目链接:Playlist for Polycarp (hard version) 题意: 你现在正在选择歌曲。现在共有 \(n\) 首歌,每首歌有一个时长 \(t_i\) 和一个编号 \(g_i\) 。 您需要求出有多少种选出若干首歌排成一排的方案, 使得任意相邻两首歌的编号不同,且所有歌的时长和恰好为 \(T\) 。 输入格式 第一行是两个整数 \(n,t ~(1\le n\le 50,1\le T\le 2500)\)。 接下来 \(n\) 行,每行两个正整数 \(t_i , g_i\) ,表示第 \(i\) 首歌曲的时长和编号。\((1\le t_i\le 50,1\le g_i\le 3)\) 输出格式 输出一个整数表示方案数。 答案对 \(10^9 + 7\) 取模。 注意到歌总共就三种,考虑提前 dp 出一些有用的东西方便后面合并。 设 \(a_{i,t}\) 为第一种歌用了 \(i\) 次,总时长为 \(t\) 的方案数。 设 \(b_{i,j,t}\) 为第二种...
洛谷P7597 「EZEC-8」猜树 加强版 题解
洛谷P7597 「EZEC-8」猜树 加强版 题解 题目链接:P7597 「EZEC-8」猜树 加强版 题意: 这是一道交互题。 有一棵以 \(1\) 为根的 \(n\) 个点的有根树,您需要通过若干次询问得到这棵树的结构。 您可以使用两种询问: ? 1 u v 通过这种询问,您可以获得 \(u\) 和 \(v\) 之间的距离。 ? 2 u 通过这种询问,您可以获得 \(u\) 子树的大小和 \(u\) 子树中的所有节点。 请通过使交互库输出不超过 \(40000\) 个数,得到这棵树的结构。 交互方式: 输入树的大小 \(n\) 以开始交互。 交互过程中,您可以进行题目描述中的两种询问。 对于第一种询问,交互库将会返回一个非负整数,表示 \(u\) 节点和 \(v\) 节点间的距离。 对于第二种询问,交互库将会先返回一个正整数 \(x\),表示 \(u\) 子树的大小。接下来会在同一行中返回 \(x\) 个正整数,表示 \(u\) 子树中的所有节点(节点顺序会被打乱)。 在您确定答案后,请以 ! fa[2] fa[3] … fa[n] 的形式输出一行,停止交互。其中 \(...

![洛谷P4639 [SHOI2011] 编译优化 题解](/qwq/img/p200.webp)
![洛谷B3704 [语言月赛202301] HACK IT! 题解](/qwq/img/p113.webp)
![洛谷P9659 [ICPC2021 Macao R] Shortest Path Fast Algorithm 题解](/qwq/img/p144.webp)









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