Q779’s Blog

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\) ，他不能把所有砝码都放到天平...

洛谷P3065 [USACO12DEC]First! G 题解 题目链接：P3065 [USACO12DEC]First! G 题意： Bessie一直在研究字符串。她发现，通过改变字母表的顺序，她可以按改变后的字母表来排列字符串（字典序大小排列）。 例如，Bessie发现，对于字符串串“omm”，“moo”，“mom”和“ommnom”，她可以使用标准字母表使“mom”排在第一个（即字典序最小），她也可以使用字母表“abcdefghijklonmpqrstuvwxyz”使得“omm”排在第一个。然而，Bessie想不出任何方法（改变字母表顺序）使得“moo”或“ommnom”排在第一个。 接下来让我们通过重新排列字母表的顺序来计算输入中有哪些字符串可以排在第一个（即字典序最小），从而帮助Bessie。 要计算字符串X和字符串Y按照重新排列过的字母表顺序来排列的顺序，先找到它们第一个不同的字母X[i]与Y[i]，按重排后的字母表顺序比较，若X[i]比Y[i]先，则X的字典序比Y小，即X排在Y前；若没有不同的字母，则比较X与Y长度，若X比Y短，则X的字典序比Y小，即X排在Y前。 ...

洛谷P2939 [USACO09FEB]Revamping Trails G 题解 题目链接：P2939 [USACO09FEB]Revamping Trails G 题意： 约翰一共有 \(N\) 个牧场.由 \(M\) 条布满尘埃的小径连接。小径可以双向通行。每天早上约翰从牧场 \(1\) 出发到牧场 \(N\) 去给奶牛检查身体。 通过每条小径都需要消耗一定的时间。约翰打算升级其中 \(K\) 条小径，使之成为高速公路。在高速公路上的通行几乎是瞬间完成的，所以高速公路的通行时间为 \(0\)。 请帮助约翰决定对哪些小径进行升级，使他每天从 \(1\) 号牧场到第 \(N\) 号牧场所花的时间最短。 \(1 \le n \le 10^4,~1\le m \le 5 \times 10^4 ,~ 1\le k \le 20\) 考虑建分层图跑最短路 首先建 \(k+1\) 个同样的图 第 \(i\) 层的结点 \(u_i\) 向 第 \(i+1\) 层的 \(v_i\) 连边 表示已经用了 \(i\) 次修改，现在是第 \(i+1\) 次修改，修改的是 \((u,v)\) ...

洛谷P4683 [IOI2008] Type Printer 题解 题目链接：P4683 [IOI2008] Type Printer 题意： 你需要利用一台可移动的打印机打印出\(N\)个单词。这种可移动式打印机是一种老式打印机，它需要你将一些小的金属块（每个包含一个字母）放到打印机上以组成单词。然后将这些小金属块压在一张纸上以打印出这个词。这种打印机允许你进行下列操作： 在打印机当前词的末端（尾部）添加一个字母； 在打印机当前词的尾部删去一个字母（将打印机当前词的最后一个字母删去）。仅当打印机当前至少有一个字母时才允许进行该操作； 将打印机上的当前词打印出来。 初始时打印机为空，或者说它不含任何带字母的金属块。打印结束时，允许有部分字母留在打印机内。同时也允许你按照任意的次序打印单词。 由于每一个操作都需要一定时间，所以需要你尽可能减少所需操作的总数目（将操作的总数最小化）。 你需要编写一个程序，给定所要打印的\(N\)个单词，找出以任意次序打印所有单词所需操作的最小数目，并输出一种这样的操作序列。 对于所有数据，\(1\leq N\leq25000\)。 显然可以用...

洛谷P3426 [POI2005]SZA-Template 题解 题目链接：P3426 [POI2005]SZA-Template 题意：你打算在纸上印一串字母。 为了完成这项工作，你决定刻一个印章。印章每使用一次，就会将印章上的所有字母印到纸上。 同一个位置的相同字符可以印多次。例如：用 aba 这个印章可以完成印制 ababa 的工作（中间的 a 被印了两次）。但是，因为印上去的东西不能被抹掉，在同一位置上印不同字符是不允许的。例如：用 aba 这个印章不可以完成印制 abcba 的工作。 因为刻印章是一个不太容易的工作，你希望印章的字符串长度尽可能小。 输入一个长度不超过 \(5 \times 10^5\) 的非空字符串（只包含小写字母），代表要在纸上印的字符。 因为印章可以随便印，也就是无所谓什么顺序和数量 所以我们可以考虑什么样的情况可以继续 观察样例 ababbababbabababbabababbababbaba ababbaba ababbaba ababbaba ababbaba ...

洛谷P2466 [SDOI2008] Sue 的小球 题解  题目链接：P2466 [SDOI2008] Sue 的小球 题意： Sue 和 Sandy 最近迷上了一个电脑游戏，这个游戏的故事发在美丽神秘并且充满刺激的大海上，Sue 有一支轻便小巧的小船。然而，Sue 的目标并不是当一个海盗，而是要收集空中漂浮的彩蛋，Sue 有一个秘密武器，只要她将小船划到一个彩蛋的正下方，然后使用秘密武器便可以在瞬间收集到这个彩蛋。然而，彩蛋有一个魅力值，这个魅力值会随着彩蛋在空中降落的时间而降低，Sue 要想得到更多的分数，必须尽量在魅力值高的时候收集这个彩蛋，而如果一个彩蛋掉入海中，它的魅力值将会变成一个负数，但这并不影响 Sue 的兴趣，因为每一个彩蛋都是不同的，Sue 希望收集到所有的彩蛋。 然而 Sandy 就没有 Sue 那么浪漫了，Sandy 希望得到尽可能多的分数，为了解决这个问题，他先将这个游戏抽象成了如下模型： 将大海近似的看做 \(x\) 轴，以 Sue 所在的初始位置作为坐标原点建立一个竖直的平面直角坐标系。 一开始空中有 \(N\) 个彩蛋，对于第 \(i\) 个彩...