求，有基本可以确定是数论分块了，但还得乘以   以为例：                        注意到每个块的答案贡献是，设这个块的长度为，那么就是   那么就直接用数论分块去累加每个块的答案贡献即可   总代码：   #include<bits/stdc++.h> using namespace std; #define endl '\n' #define int long long #define IOS ios::sync_with_stdio(false);cin.tie(NU...

设表示区间所有数的因子个数之和，那么求区间的因子个数之和为   如何求   这是暴力循环的代码：   因为区间中有个数是的倍数，即有个数的因子包含   区间中有个数是的倍数，即有个数的因子包含   区间中有个数是的倍数，即有个数的因子包含   .....   int sum = 0; for(int i = 1; i <= n; i ++){     sum += (n / i); } cout&nb...

目标是求的和：   做法是将相同的连续一个区间看做一个块，例如区间中所有的的的值都相同，那么我直接   所以依次枚举区间的左边界，然后找到最大的右边界，然后累加，最后将设置为，继续找下一个块   下面是基本代码：   int ans = 0; for(int i = 1; i <= n; i ++){     int l = i, r = 😀    ...

给你一棵树(因为n个节点，n-1条边)，每个节点的权值就是它的度数，然后若干次查询：求任意两个节点的最短路径上的权值之和   使用倍增的算法求解，我们知道   使用相同的思想，在DFS中同时存储，从根节点到每个节点的权值之和，记为   那么是不是   但还是有问题，这里有一点需要警惕：   ，这个公式是边的数量   而是求节点权值的和，这个点也在最短路径上，但是，其中是把这个点的权值给减掉了，所以还得加上，那么正确的公式应当为：   总代码：   #include<bits/stdc++.h> using namespace std; #define ...

题目的意思是给定了一棵树，有若干个询问：，问的最短路径和的最短路径是否有交点     神奇的结论：如果两条最短路径相交，那么其中一条的最近公共祖先一定在另一条最短路径上   证明就是如图所示，如果存在交点，那么可以继续向上走，或者向下走；如果向下走，那么LCA就是向下走的哪个转折点，如果向上走，那么LCA就是最上面的那个点或者它在某个位置向下走的转折点   所以既然如果相交，不妨以在的最短路径上，那么一定有:                  &...

最近公共祖先:在有根树的结构中，对于任意两个节点和,它们的最近公共祖先是指满足下面两个条件的节点:     同时是和的公共祖先(即在到根节点的路径上，也在到根节点的路径上)、   是所有公共祖先中深度最大的节点("最近"的本质是距离u 和 v距离最近)   关键性质：     是到根节点的路径与到根节点的路径中第一个交点   这棵树里面到的的最短路径一定经过并且是这条最短路径中深度最小的节点   多个节点的最近公共祖先：   如果是的祖先，则；反之同理    的常见使用场景：     计算树上两点间的距离：，很好理解：表示根节点到的距离，表示根节点到的距离，两者重叠部分是根节点到的距离，并且重...

倍增题目   太卡时间了，没意思   定义st[i][j]表示从i位置 进行了次操作后的下标，为什么是下标呢？   我一开始定义的是i位置进行了次次操作后的值，但是发现如果是值的话，转移方程写不了   如果是下标，那么转移时，直接就是,初始化st[i][0] = x[i]   所以可以很快的写完代码： #include<bits/stdc++.h> using namespace std; #define endl '\n' #define ll long long #define IOS i...

倍增题目   和上一道题差不多，但还是有很些区别(这道题完全靠自己做出来了！)   题目的意思就是不断的跃迁，然后累加上每一次跃迁到达的位置的值，当然跃迁的次数m最大为1e18;   定义st[i][j]表示从i出发，跃迁了次后的结果   那么转移的方程：就不是简单的什么st[i][j] = st[st[i][j - 1][j - 1],所以，转移的方程是需要根据题目变化的   容易想到st[i][j] = st[i][j - 1] + 🤔：st[i][j - 1]表示从i跃迁了后的结果, 那么还需要加上再跃迁的值。   那肯定不是st[i][j] = st[i][j - 1] + st[i...

这是一道倍增题目，因为k最大可以取到1e18,所以需要优化转化为二进制来计算   定义st[i][j]表示从i这个位置经行次跃迁后到达的位置，那么st[i][j] = st[st[i][j - 1]][j - 1], 表示的是从st[i][j - 1](即先从i这个位置进行次跃迁)然后再进行次跃迁.那么就相当于经行了次跃迁   观察st[i][j]的转移方程式，其实只需要求出所有的st[i][0]，那么就可以推出所有的st[i][j]   st[i][0]表示从i位置进行即1次跃迁的结果，求st[i][0]的具体方法是：   首先需要将字符串s扩大一倍，因为这是环形： string ...

题目的意思是将这n张牌修改成一个顺子，求最小的操作次数   修改后的顺子一定是[left, left + 1, left + 2, ... , right]，其中right - left + 1 = n, 也就是长度为n   那么最优的方法就是依次枚举每一个a[i]为左边界left，然后看有多少个元素在[a[i], a[i] + n - 1]   所以首先得对a[]数组进行从小到大的排序并且去重   sort(a.begin(), a.end()); a.erase(unique(a.begin(), a.end()), a.end()); 然后依次枚举每一个a[...

纯思维题目   还是很好想的：假设我现在知道了前 i - 1 张的答案，然后我需要求前 i 张牌的答案(为什么是这样想？，因为题目就是这么说的：依次回答的每一个答案   那么当我新加入a[i]时，如果前 i  - 1张牌里面有 a[i] - 1 或者有 a[i] + 1牌时，那么我是不是就可以连成顺子来打？   可以将a[i]与a[i] - 1或者a[i] 与 a[i] + 1连接成顺子，这样前 i 张牌的答案就是前 i - 1张牌的答案，但是：   比如[4, 5, 4]，答案是[1, 1, ?]此时 "?"就不是1而是2，所以这里面还得考虑一个关键因素：数量   那么结论就是：(...

2是唯一一个偶数质数，其他的质数都是奇数   所以在中：   显然如果都是奇数质数，则为偶数，为奇数，则肯定不满足   所以中肯定其中一个为2   所以不妨令，然后枚举小于n的质数即可   总代码:   #include<bits/stdc++.h> using namespace std; #define endl '\n' #define int long long #define IOS ios::sync_with_stdio(false);cin.tie(NULL);cout.tie...

唯一分解定理:任何一个大于1的整数n都可以分解成若干个质数的连乘积   那么   则的因子总个数为   那么对于给定的n，求   方案一：全部分解为质数，那么值为   方案二：不分解，那么值为   方案三：分解部分：例如将n分解为:,那么值为   显然方案二总是比方案三更好，所以只需考虑方案一与方案二的优劣   当n只能分解为一个质数时，此时方案一的值为，而方案二为,此时方案一比方案二更优   当n可以分解为多个质数时，方案二比方案一更优   总代码：   #include<bits/stdc++.h> using namespace std; #define&...

cin >> n >> m; vector<int> dp(m + 1); for(int i = 1; i <= n; i ++) cin >> v[i] >> w[i]; for(int i = 1; i <= n; i ++){  ...