题目描述 给定两个整数 和 ，对于所有满足 的 ，把 的所有约数全部写下来。对于每个写下来的数，只保留最高位的那个数码。求每个数码出现的次数。 分析 由于约数和倍数一一对应，我们考虑枚举 ，然后 的倍数就有 个，那么 的数码出现次数就加上倍数个数。所以我们考虑某个数的倍数。由于每个数码独立，我们将每个数码单独考虑，假设考虑数码 。那我们就枚举 在个位，十位，百位等等的情况。假设 在第 位。那么范围就是 ，现在我们要看这个范围内每个数的倍数之和，也就是 。然后这个是一个除法分块的问题。关于除法分块，我这里简要说一说。首先随着 增大， 是单调不增的，而且相同的 构成一段连续...

这周学了一些数学题，下周继续学数学题QAQ

题意 给出长度为 的字符串，求长度为 的本质不同的子序列个数。 分析 设 表示前 个字母，长度为 的本质不同子序列个数。考虑 来源。 首先 可以来源于 ，也就是 不参与构成子序列 然后考虑第 参与子序列，第一反应肯定是 。不过这会有重复。假设上一个相同字母的位置为 ，则 参与了两个相同子序列，所以要减掉这部分。 代码如下 #include <bits/stdc++.h> #include<ext/pb_ds/hash_policy.hpp> #include<ext/pb_ds/assoc_container.hpp> #define...

T1 String 题意 给定一个字符串 ,求 中不同字符的个数。（) 分析 扫一遍 ，开个桶记录一下哪些字母用过，如果没用过，标记它用过，并将答案 代码如下 #include <bits/stdc++.h> #define LL long long #define N 1000005 using namespace std; int v[N], ans; LL z = 1; char s[N]; int main(){ int i, j, n, m; scanf("%s", s + 1); n = strlen(s + 1); for(i = ...

题意 给定一棵树，有 个节点（ 为偶数）。将 个节点分成 组，每组有 个节点 ，每组的值为 到 的树上路径和，总答案为每一组的和。求答案最小值。 分析 这是一道贪心题。首先一个点和另一个点的距离不会超过两条边，这个画画图即可看出。于是我们可以知道，最优情况下，一个点的配对点一定是它的父亲或兄弟节点。考虑以 为根的子树和它的儿子节点。如果节点 已经用过了，那显然不用再用它了。没用过就入队。那么我们得到的队列全是没用过的儿子节点。最优情况肯定是将儿子节点两两相连。但是会出现奇数个节点的情况，这时候只用将它和 相连就可以了。事实上，我们甚至不用一个队列。如果儿子节点没用过，就直接把...

题意 给定字符串 ，有 个询问，每个询问给出一个字符串 , 问 是否是 的子序列。 分析 先记录每个字母在 中出现的位置。对于字符串 的每个 ，我们肯定尽可能在 中往前取。假设上一次取的是 。那么这一次就要在所有 出现的位置中找到第一个比 大的。这个可以二分解决。 代码如下 #include <bits/stdc++.h> #include<ext/pb_ds/hash_policy.hpp> #include<ext/pb_ds/assoc_container.hpp> #define N 1000005 using namespace _...

题意 给定一棵树和根节点，每条边有边权。删去一些边，使得根节点和叶子节点不连通，求删的边的边权和最小值。 分析 树形dp。令 表示 不与子树中的叶子节点相连的最小值。考虑 的每一个儿子 和边权 显然断 中叶子节点的最优值为 然后 即可。 代码如下 #include <bits/stdc++.h> #include<ext/pb_ds/hash_policy.hpp> #include<ext/pb_ds/assoc_container.hpp> #define N 100005 using namespace __gnu_pbds; using ...

题意 给定一棵树，有 个点，根节点为 ，每个节点有一个值 。有 个询问，每个询问包含 ，问当前值为 ，从 走到 ，每次遇到比当前值大的值，即将当前值替换为该值，最终总共要替换多少次。（ 在 到根节点的路径上） 分析 这题还是很有必要记录一下的！首先我们每次可以在 后面接一个点 ， 点的值为 ，相当于每次从 走向 。然后暴力是 ，显然不可取。但是如果我们能快速知道每个值往上走第一个比它大的值，就可以倍增来解决了。问题是，怎么获取每个值往上走的第一个比它大的值呢？注意到，比 大的第一个值，一定是 或这比 大的第 个值（ 为正整数，这里假设 的值为无穷大）。于是，我们可以用倍增...

题意 给定 和数组 。求 中的最大值和最小值 。 分析 这题要用到单调队列。什么是单调队列？顾名思义，就是里面元素是单调的队列。假如我们有这么一个队列，里面的元素都是合法且单调的。那么最大值和最小值不是呼之欲出了吗？那么现在如何维护队列单调呢？以求最大值为例。假如当前维护了一个队列。现在新插入一个元素，这个元素如果比上一个元素大，那么上一个元素一定不会作为答案出现在之后的滑动窗口中，因为这个元素不仅在上一个元素的后面，而且还比它大。于是，上一个元素可以滚蛋了！然后再比较它和上上个元素，一直比较下去。比较完，我们得到了就是一个单调减的队列，里面的元素都无法再删去了！那么最大值就是队首的值。做...

题意 有 个数选两个长度为 的不相交区间，使得他们的和尽量大，求最大和。 分析 我们可以固定一个区间，然后来找另一个区间。记 为 的前缀和在这道题中，我们枚举 ，然后固定右边的区间 ，右边的贡献为 那么，现在就是在 中找长度为 的连续区间的和的最小值。那么我们设 表示 中长度为 的连续区间的和的最小值，考虑第 个点作为右端点，转移方程就是： 到这里这题就解决了。我们枚举右边区间的左端点 ，然后 即可。这个代码跑了108ms，牛客最快哦 代码如下 #include <bits/stdc++.h> #define N 200005 using namespace ...