Q779’s Blog

洛谷P4799 [CEOI2015 Day2] 世界冰球锦标赛 题解 题目链接：P4799 [CEOI2015 Day2] 世界冰球锦标赛 题意： 译自 CEOI2015 Day2 T1「Ice Hockey World Championship」 今年的世界冰球锦标赛在捷克举行。Bobek 已经抵达布拉格，他不是任何团队的粉丝，也没有时间观念。他只是单纯的想去看几场比赛。如果他有足够的钱，他会去看所有的比赛。不幸的是，他的财产十分有限，他决定把所有财产都用来买门票。 给出 Bobek 的预算和每场比赛的票价，试求：如果总票价不超过预算，他有多少种观赛方案。如果存在以其中一种方案观看某场比赛而另一种方案不观看，则认为这两种方案不同。 数据组号 \(1-2\) \(3-4\) \(5-7\) \(8-10\) \(N \leq\) \(10\) \(20\) \(40\) \(40\) \(M \leq\) \(10^6\) \(10^{18}\) \(10^6\) \(10^{18}\) 首先这个 \(20\) 就很有趣 显然暴搜是吧 那么 \(4...

洛谷P3435 [POI2006] OKR-Periods of Words 题解 题目链接：P3435 [POI2006] OKR-Periods of Words 题意： 对于一个仅含小写字母的字符串 \(a\)，\(p\) 为 \(a\) 的前缀且 \(p\ne a\)，那么我们称 \(p\) 为 \(a\) 的 proper 前缀。 规定字符串 \(Q\)（可以是空串）表示 \(a\) 的周期，当且仅当 \(Q\) 是 \(a\) 的 proper 前缀且 \(a\) 是 \(Q+Q\) 的前缀。 例如 ab 是 abab 的一个周期，因为 ab 是 abab 的 proper 前缀，且 abab 是 ab+ab 的前缀。 求给定字符串所有前缀的最大周期长度之和。 \(1\le |a| \le 10^6\) 考虑如何最大化周期 \(Q\) 对于某个前缀，例如 \(s = \tt{aabaaaab}\) 不难发现它的最长周期就是 \(\tt{aabaa}\) 仔细观察 \(\tt{\color{red}{aab}\color{blue}{aa}\color{red}{a...

洛谷P4287 [SHOI2011]双倍回文 题解 题目链接：P4287 [SHOI2011]双倍回文 题意： 记字符串 \(w\) 的倒置为 \(w^R\) 。例如 \((\tt{abcd})^R=\tt{dcba}\) ， \((\tt{abba})^R=\tt{abba}\) 。 对字符串 \(x\) ，如果 \(x\) 满足 \(x^R=x\) ，则称之为回文；例如 \(\tt{abba}\) 是一个回文，而 \(\tt{abed}\) 不是。 如果 \(x\) 能够写成的 \(ww^Rww^R\) 形式，则称它是一个“双倍回文”。换句话说，若要 \(x\) 是双倍回文，它的长度必须是 \(4\) 的倍数，而且 \(x\) ， \(x\) 的前半部分， \(x\) 的后半部分都要是回文。例如 \(\tt{abbaabba}\) 是一个双倍回文，而 \(\tt{abaaba}\) 不是，因为它的长度不是 \(4\) 的倍数。 \(x\) 的子串是指在\(x\)中连续的一段字符所组成的字符串。例如 \(\tt{be}\) 是 \(\tt{abed}\) 的子串，而 \(\t...

洛谷P2375 [NOI2014] 动物园 题解 题目链接：P2375 [NOI2014] 动物园 题意： 近日，园长发现动物园中好吃懒做的动物越来越多了。例如企鹅，只会卖萌向游客要吃的。为了整治动物园的不良风气，让动物们凭自己的真才实学向游客要吃的，园长决定开设算法班，让动物们学习算法。 某天，园长给动物们讲解KMP算法。 园长：“对于一个字符串\(S\)，它的长度为\(L\)。我们可以在\(O(L)\)的时间内，求出一个名为next的数组。有谁预习了next数组的含义吗？” 熊猫：“对于字符串\(S\)的前\(i\)个字符构成的子串，既是它的后缀又是它的前缀的字符串中（它本身除外），最长的长度记作\(next[i]\)。” 园长：“非常好！那你能举个例子吗？” 熊猫：“例\(S\)为abcababc，则\(next[5]=2\)。因为\(S\)的前\(5\)个字符为abcab，ab既是它的后缀又是它的前缀，并且找不到一个更长的字符串满足这个性质。同理，还可得出\(next[1] = next[2] = next[3] = 0\)，\(next[4] = next[6] = ...

洛谷P4568 [JLOI2011] 飞行路线 题解 题目链接：P4568 [JLOI2011] 飞行路线 题意： Alice 和 Bob 现在要乘飞机旅行，他们选择了一家相对便宜的航空公司。该航空公司一共在 \(n\) 个城市设有业务，设这些城市分别标记为 \(0\) 到 \(n-1\)，一共有 \(m\) 种航线，每种航线连接两个城市，并且航线有一定的价格。 Alice 和 Bob 现在要从一个城市沿着航线到达另一个城市，途中可以进行转机。航空公司对他们这次旅行也推出优惠，他们可以免费在最多 \(k\) 种航线上搭乘飞机。那么 Alice 和 Bob 这次出行最少花费多少？ 对于 \(100\%\) 的数据，\(2 \le n \le 10^4\)，\(1 \le m \le 5\times 10^4\)，\(0 \le k \le 10\)，\(0\le s,t,a,b\le n\)，\(a\ne b\)，\(0\le c\le 10^3\)。 分层图板子题 不写具体做法了，就总结几个易错点 无向图的e数组开 \[ M\times (K+1) \times 4 \] ...

洛谷P4551 最长异或路径 题解 题目链接：P4551 最长异或路径 题意：给定一棵 \(n\) 个点的带权树，结点下标从 \(1\) 开始到 \(n\)。寻找树中找两个结点，求最长的异或路径。 异或路径指的是指两个结点之间唯一路径上的所有边权的异或。 \(1\le n \le 100000,~0 < u,v \le n,~0 \le w < 2^{31}\)。 首先可以想到一个常用trick：前缀和处理边权异或和 然后对于每个异或和，我们都要找到一个和它异或值尽可能大的前缀和 直接枚举是不行的，考虑建01trie 01trie其实很简单，就是把每个数字的二进制形式看成字符串去建trie 贪心地选择高位，具体看代码就可以了，很简单 时间复杂度 \(O(n \log \max\{w_i\})\) ，其实就是 \(O(30 \times n)\) 代码： #include <iostream> #include <string> #include <vector> #include <algorithm> #include <cstdi...

洛谷P3698 [CQOI2017]小Q的棋盘 题解 题目链接：P3698 [CQOI2017]小Q的棋盘 题意： 小 Q 正在设计一种棋类游戏。 在小 Q 设计的游戏中，棋子可以放在棋盘上的格点中。某些格点之间有连线，棋子只能在有连线的格点之间移动。整个棋盘上共有 \(V\) 个格点，编号为\(0,1,2,\dots , V−1\)，它们是连通的，也就是说棋子从任意格点出发，总能到达所有的格点。小 Q 在设计棋盘时，还保证棋子从一个格点移动到另外任一格点的路径是唯一的。 小 Q 现在想知道，当棋子从格点 \(0\) 出发，移动 \(N\) 步最多能经过多少格点。格点可以重复经过多次，但不重复计数。 对于 \(100\%\) 的测试点，\(N,V \le 100,~0 \le a_i,b_i< V\) 。 显然树上背包 值得注意的是，我们并不知道走的路线有没有回到 \(u\) 因此要多加一维 设 \(f_{u,j,0/1}\) 表示 \(u\) 所在子树，走了 \(j\) 步，\(0/1\) 表示是/否回到 \(u\) 不难发现 \[ f_{u,j,0}=\max_{v...

洛谷P1005 [NOIP2007 提高组] 矩阵取数游戏 题解 题目链接：P1005 [NOIP2007 提高组] 矩阵取数游戏 题意： 帅帅经常跟同学玩一个矩阵取数游戏：对于一个给定的 \(n \times m\) 的矩阵，矩阵中的每个元素 \(a_{i,j}\) 均为非负整数。游戏规则如下： 每次取数时须从每行各取走一个元素，共 \(n\) 个。经过 \(m\) 次后取完矩阵内所有元素； 每次取走的各个元素只能是该元素所在行的行首或行尾； 每次取数都有一个得分值，为每行取数的得分之和，每行取数的得分 = 被取走的元素值 \(\times 2^i\)，其中 \(i\) 表示第 \(i\) 次取数（从 \(1\) 开始编号）； 游戏结束总得分为 \(m\) 次取数得分之和。 帅帅想请你帮忙写一个程序，对于任意矩阵，可以求出取数后的最大得分。 对于 \(60\%\) 的数据，满足 \(1\le n,m\le 30\)，答案不超过 \(10^{16}\)。 对于 \(100\%\) 的数据，满足 \(1\le n,m\le 80\)，\(0\le a_{i,j}\le1000...

洛谷P2585 [ZJOI2006]三色二叉树 题解 题目链接：P2585 [ZJOI2006]三色二叉树 题意： 一棵二叉树可以按照如下规则表示成一个由 \(0\)、\(1\)、\(2\) 组成的字符序列，我们称之为“二叉树序列 \(S\)”： \[S= \begin{cases} 0& \text表示该树没有子节点\\ 1S_1& 表示该树有一个节点，S_1 为其子树的二叉树序列\\ 2S_1S_2& 表示该树由两个子节点，S_1 和 S_2 分别表示其两个子树的二叉树序列 \end{cases}\] 例如，下图所表示的二叉树可以用二叉树序列 \(S=\texttt{21200110}\) 来表示。 你的任务是要对一棵二叉树的节点进行染色。每个节点可以被染成红色、绿色或蓝色。并且，一个节点与其子节点的颜色必须不同，如果该节点有两个子节点，那么这两个子节点的颜色也必须不同。给定一颗二叉树的二叉树序列，请求出这棵树中最多和最少有多少个点能够被染成绿色。 对于全部的测试点，保证 \(1 \leq |s| \leq 5 \times 10^5\)，\(s\...

洛谷P5520 [yLOI2019] 青原樱 题解 题目链接：P5520 [yLOI2019] 青原樱 题意： \(n\) 个空放 \(m\) 个物品，两两物品不能直接相邻，至少空一格 纯数学题。 看看几个空不能放，啊 \(m-1\) 那能放的就有 \(n-m+1\) 个空 \[ A_{n-m+1}^{m} \] 没了，水吧。直接算这个就好了。 为什么对呢，因为你在这 \(n-m+1\) 个空里面可以随便放 时间复杂度 \(O(n)\) 代码： #include <iostream> #include <string> #include <vector> #include <algorithm> #include <cstdio> #include <cstdlib> #include <cstring> #include <cmath> #include <iomanip> using namespace std; #define int long long #define INF 0x3f3f3f3f3f3f3f3f ...

洛谷P2822 [NOIP2016 提高组] 组合数问题 题解 题目链接：P2822 [NOIP2016 提高组] 组合数问题 题意： 组合数 \(\binom{n}{m}\) 表示的是从 \(n\) 个物品中选出 \(m\) 个物品的方案数。举个例子，从 \((1,2,3)\) 三个物品中选择两个物品可以有 \((1,2),(1,3),(2,3)\) 这三种选择方法。根据组合数的定义，我们可以给出计算组合数 \(\binom{n}{m}\) 的一般公式： \[ \binom{n}{m}=\frac{n!}{m!(n-m)!} \] 其中 \(n!=1\times2\times\cdots\times n\)；特别地，定义 \(0!=1\)。 小葱想知道如果给定 \(n,m\) 和 \(k\)，对于所有的 \(0\leq i\leq n,0\leq j\leq \min \left ( i, m \right )\) 有多少对 \((i,j)\) 满足 \(k|\binom{i}{j}\)。 对于全部的测试点，保证 \(0 \leq n, m \leq 2 \times 10...

洛谷P4127 [AHOI2009]同类分布 题解 题目链接：P4127 [AHOI2009]同类分布 题意： 给出两个数 \(a,b\) ，求出 \([a,b]\) 中各位数字之和能整除原数的数的个数。 对于所有的数据， \(1 ≤ a ≤ b ≤ 10^{18}\)。 明天就期末考了非但不复习还在刷题 qwqqwqwq 因为我们不能确切知道每个数的数位和 但是我们知道它们一定在 \([1,9 \times l]\) 的范围内（ \(l\) 为最长的位数） 我们枚举所有的数位和并计算每个数位和对应的答案 把这些答案加起来就是 \([0,x]\) 的答案 \([a,b]\) 的答案可以拆分为两个询问 \([0,b]\) 和 \([0,a-1]\) 而这里 \(a,b \le 10^{18}\) ，直接压入状态显然不可接受 于是我们可以考虑记录模当前枚举的数位和意义下的数 方便起见，我们称当前枚举的数位和为 \(m\) 设 \(f_{i,j,k}\) 表示只考虑前 \(i\) 位数（包括前导零），前 \(i\) 位的数位和为 \(j\) ，当前数模 \(m\) 为 \(k\) ...