Q779’s Blog

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」高维立方体 题意： 如下定义斐波那契数列： \[ \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) 题解 题目链接：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) 题解 题目链接：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 题解 题目链接：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 题解 题目链接：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) 题解 题目链接：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」猜树 加强版 题意： 这是一道交互题。 有一棵以 \(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] 的形式输出一行，停止交互。其中 \(...

洛谷P2178 [NOI2015] 品酒大会 题解 题目链接：P2178 [NOI2015] 品酒大会 题意： 一年一度的“幻影阁夏日品酒大会”隆重开幕了。大会包含品尝和趣味挑战 两个环节，分别向优胜者颁发“首席品酒家”和“首席猎手”两个奖项，吸引了众多品酒师参加。 在大会的晚餐上，调酒师 Rainbow 调制了 \(n\) 杯鸡尾酒。这 \(n\) 杯鸡尾酒排成一行，其中第 \(n\) 杯酒 (\(1 ≤ i ≤ n\)) 被贴上了一个标签 \(s_i\) ，每个标签都是 \(26\) 个小写 英文字母之一。设 \(\text{str}(l, r)\) 表示第 \(l\) 杯酒到第 \(r\) 杯酒的 \(r - l + 1\) 个标签顺次连接构成的字符串。若 \(\text{str}(p, p_0) = \text{str}(q, q_0)\)，其中 \(1 \le p \le p_0 \le n\), \(1 \le q \le q_0 \le n\), \(p \ne q\)，\(p_0-p+1 = q_0 - q + 1 = r\) ，则称第 \(p\) 杯酒与第 \...

CF1227F2 Wrong Answer on test 233 (Hard Version) 题解 题目链接：Wrong Answer on test 233 (Hard Version) 题意： cxy 要参加一场考试，这场考试有 \(n\) 道选择题，每个选择题有 \(k\) 个选项。 但是 cxy 昨天玩某中文二字英文七字游戏玩过头了，导致她这次考试时十分困倦以至于居然填错了答题卡！ 具体地，cxy 错误地将第 \(i\) 道选择题的答案填到第 \((i \bmod n) + 1\) 道题去了。 不过她是怎么做到将第 \(n\) 道题的答案填到第 \(1\) 道去的？果然是玩【数据删除】玩的。 显然，此时 cxy 非常焦虑，但是她不记得自己每道题原来填了什么选项了 现给出每道题的答案 \(h_i\) ，请帮助 cxy 计算有多少种可能的初始答案，使得错误填涂后比原来正确的多了。 输入格式： 第一行给出 \(n,k~(1 \le n \le 2\times 10^5,\,1\le k \le 10^9)\) 。 第二行给出 \(n\) 个数 \(h_1,h_2,\cdo...

CF1370F2 The Hidden Pair (Hard Version) 题解 题目链接：The Hidden Pair (Hard Version) 题意： 这是一道交互题，且本题有多组数据。 已知一棵 \(n\) 个顶点的树（边集已知），其中有两个不同的顶点被暗中做了标记。 你现在需要通过若干次询问，猜出两个被标记顶点的编号。 一次询问的格式为 ? c x1 x2 ... xc，表示向交互库请求关于 \(x_1,x_2,\cdots,x_c\) 这 \(c(c \le n)\) 个点的信息。 对于一次询问，交互库的返回格式为 x d，表示在询问的集合中，到两个被标记点的距离之和最小的点是 \(x\)，这个最小值为 \(d\)。如果有多个最小值点，\(x\) 的值可能是其中任意一个。 如果已经知晓答案，请用 ! x y 的格式来输出你的答案，任意顺序均可。在这之后，你会收到一个字符串 Correct 或者 Incorrect，代表你的猜测是否正确。如果收到了 Incorrect，请立即终止程序，否则请继续处理下一组数据。 对于每组数据，请你在不超过 \(11\) 次询问...

[AGC028B] Removing Blocks 题解 题目链接：[AGC028B] Removing Blocks 题意： 有 \(N\) 块砖块排列成一行，从左到右编号为 \(1\) 到 \(N\) 。每一个砖块都有一个重量，砖块 \(i\) 的重量为 \(A_i\)。 Snuke 会对这些 \(N\) 个砖块执行如下操作： 选择一个还没有被移除的砖块，然后移除它。这个操作的代价是与被移除的砖块相邻的砖块（包括它自己）的重量之和。我们定义两块砖 \(x\) 和 \(y ~(x \leq y)\) 是相邻的，当且仅当对于所有 \(z ~(x \leq z \leq y)\) ，砖块 \(z\) 仍然没有被移除。 有 \(N!\) 种移除砖块的可能顺序。你需要对于所有可能的顺序计算出移除完所有 \(N\) 块砖块的代价，并计算这些代价的和。由于答案可能非常大，答案需要对 \(10^9+7\) 取模。 数据范围： \(1 \le n \le 10^5,~1 \le A_i \le 10^9\) 。 这题它本可以问你期望是什么的，但是它偏要问你期望乘以 \(n!\) ，后面忘了...