Q779’s Blog

洛谷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\) ...

CF1036C Classy Numbers 题解 题目链接：CF1036C Classy Numbers 题意：定义一个数字是“好数”，当且仅当它的十进制表示下有不超过\(3\)个数字\(1 \sim 9\) 举个例子：\(4,200000,10203\)是“好数”，然而\(4231,102306,7277420000\)不是 给定\([l,r]\)，问有多少个\(x\)使得\(l \le x \le r\)，且\(x\)是“好数” 一共有\(T(1 \le T \le 10^{4})\)组数据，对于每次的询问，输出一行一个整数表示答案 \(1 \le l_i \le r_i \le 10^{18}\) 一般数位dp可以用来解决 \(\sum _{i=l}^{r} f(i)\) 的问题， 其中 \(f(i)\) 为与 \(i\) 的数位有关的某个函数或判定式 这题稍微变形了一下，那我们就理所当然地记录一下出现数字的情况 设 \(f_{i,j}\) 表示满 \(i\) 位数，有 \(j\) 个非 \(0\) 位 采用记忆化搜索，详见代码 #include <iostre...

洛谷P1836 数页码 题解 题目链接：P1836 数页码 题意： 一本书的页码是从 \(1\sim n\) 编号的连续整数：\(1,2,3,\cdots,n\)。请你求出全部页码中所有单个数字的和，例如第 \(123\) 页，它的和就是 \(1+2+3=6\)。 \(1\le n\le 10^9\) 容易发现这个东西可以转化为 \(1 \sim n\) 中每个数字有多少个 考虑数位dp，详见link 然后把每个数字乘一乘就好了 代码： #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 #def...

SP3928 MDIGITS - Counting Digits 题解 题目链接：SP3928 MDIGITS - Counting Digits 题意： 给定两个整数 \(a\) 和 \(b\)，求 \(a\) 和 \(b\) 之间的所有数字中 \(0\) ~ \(9\) 出现次数。 例如，\(a\) = \(1024\)，\(b\) = \(1032\)，则 \(a\) 和 \(b\) 之间共有 \(9\) 个数如下： 1024 1025 1026 1027 1028 1029 1030 1031 1032 其中 0 出现 \(10\) 次，1 出现 \(10\) 次，2 出现 \(7\) 次，3 出现 \(3\) 次等等…… 数位dp的基础题 设 \(f_i\) 表示满 \(i\) 位数字（包括前导零），每种数字的出现次数 \[ f_1 = 1 \\f_i = f_{i-1} \times 10 + 10^{i-1} \] 其中 \(f_{i-1}\times 10\) 是 \(i-1\) 位及以下位的贡献 例如 \(\tt{7000\sim7999,~8000\si...

洛谷P4047 [JSOI2010]部落划分 题解 题目链接：P4047 [JSOI2010]部落划分 题意： 聪聪研究发现，荒岛野人总是过着群居的生活，但是，并不是整个荒岛上的所有野人都属于同一个部落，野人们总是拉帮结派形成属于自己的部落，不同的部落之间则经常发生争斗。只是，这一切都成为谜团了——聪聪根本就不知道部落究竟是如何分布的。 不过好消息是，聪聪得到了一份荒岛的地图。地图上标注了 \(n\) 个野人居住的地点（可以看作是平面上的坐标）。我们知道，同一个部落的野人总是生活在附近。我们把两个部落的距离，定义为部落中距离最近的那两个居住点的距离。聪聪还获得了一个有意义的信息——这些野人总共被分为了 \(k\) 个部落！这真是个好消息。聪聪希望从这些信息里挖掘出所有部落的详细信息。他正在尝试这样一种算法： 对于任意一种部落划分的方法，都能够求出两个部落之间的距离，聪聪希望求出一种部落划分的方法，使靠得最近的两个部落尽可能远离。 例如，下面的左图表示了一个好的划分，而右图则不是。请你编程帮助聪聪解决这个难题。 对于 \(100\%\) 的数据，保证 \(2 \leq k \l...

洛谷P5018 [NOIP2018 普及组] 对称二叉树 题解 题目链接：P5018 [NOIP2018 普及组] 对称二叉树 题意： 一棵有点权的有根树如果满足以下条件，则被轩轩称为对称二叉树： 二叉树； 将这棵树所有节点的左右子树交换，新树和原树对应位置的结构相同且点权相等。 下图中节点内的数字为权值，节点外的 \(id\) 表示节点编号。 现在给出一棵二叉树，希望你找出它的一棵子树，该子树为对称二叉树，且节点数 最多。请输出这棵子树的节点数。 注意：只有树根的树也是对称二叉树。本题中约定，以节点 \(T\) 为子树根的一棵“子 树”指的是：节点\(T\) 和它的全部后代节点构成的二叉树。 【数据规模与约定】 共 \(25\) 个测试点。 \(v_i ≤ 1000\)。 测试点 \(1 \sim 3, n ≤ 10\)，保证根结点的左子树的所有节点都没有右孩子，根结点的右 子树的所有节点都没有左孩子。 测试点 \(4 \sim 8, n ≤ 10\)。 测试点 \(9 \sim 12, n ≤ 10^5\)，保证输入是一棵“满二叉树” 。 测试点 \(13 \sim ...

洛谷P5536 【XR-3】核心城市 题解 题目链接：P5536 【XR-3】核心城市 题意： X 国有 \(n\) 座城市，\(n - 1\) 条长度为 \(1\) 的道路，每条道路连接两座城市，且任意两座城市都能通过若干条道路相互到达，显然，城市和道路形成了一棵树。 X 国国王决定将 \(k\) 座城市钦定为 X 国的核心城市，这 \(k\) 座城市需满足以下两个条件： 这 \(k\) 座城市可以通过道路，在不经过其他城市的情况下两两相互到达。 定义某个非核心城市与这 \(k\) 座核心城市的距离为，这座城市与 \(k\) 座核心城市的距离的最小值。那么所有非核心城市中，与核心城市的距离最大的城市，其与核心城市的距离最小。你需要求出这个最小值。 数据范围： \(1 \le k < n \le 10 ^ 5\)。 \(1 \le u,v \le n, u \ne v\)，保证城市与道路形成一棵树。 不要被树这个东西坑了，其实和树关系不大 我们感性地分析一下，这些核心城市一定是在比较中间的位置 然后这些核心城市到所有边缘结点的距离是相差不超过 \(1\) 的 那...

洛谷P5194 [USACO05DEC]Scales S 题解 题目链接：P5194 [USACO05DEC]Scales S 题意： 约翰有一架用来称牛的体重的天平。与之配套的是 \(N\) ( \(1 \leq N \leq 1000\) )个已知质量的砝码（所有砝码质量的数值都在32位带符号整数范围内）。 每次称牛时，他都把某头奶牛安置在天平的某一边，然后往天平另一边加砝码，直到天平平衡，于是此时砝码的总质量就是牛的质量（约翰不能把砝码放到奶牛的那边，因为奶牛不喜欢称体重，每当约翰把砝码放到她的蹄子底下，她就会尝试把砝码踢到约翰脸上）。 天平能承受的物体的质量不是无限的，当天平某一边物体的质量大于 \(C\) ( \(1 \leq C \leq 2^{30}\) )时，天平就会被损坏。砝码按照它们质量的大小被排成一行。并且，这一行中从第3个砝码开始，每个砝码的质量至少等于前面两个砝码（也就是质量比它小的砝码中质量最大的两个）的质量的和。 约翰想知道，用他所拥有的这些砝码以及这架天平，能称出的质量最大是多少。由于天平的最大承重能力为 \(C\) ，他不能把所有砝码都放到天平...