定义一个数字是“好数”，当且仅当它的十进制表示下有不超过3个数字1∼9 举个例子：4,200000,102034,200000,10203是“好数”，然而4231,102306,72774200004231,102306,7277420000不是 给定[l,r]，问有多少个x使得l≤x≤r，且x是“好数” 一共有T(1≤T≤10^4)组数据，对于每次的询问，输出一行一个整数表示答案 数位dp #include <bits/stdc++.h> #include <iostream> #include <string.h> #include <math.h...

给你一个n和d，求1-n中有多少个数位和是d的倍数 数位dp #include <bits/stdc++.h> #include <iostream> #include <string.h> #include <math.h> using namespace std; typedef long long ll; const ll mod = 1e9 + 7; const int maxn = 10005; int digit[maxn], tot, d; ll dp[maxn][105]; ll dfs(int len, int pre, int...

小象非常喜欢区间中的数. 此时他有一対整数l和r(l<=r). 小象需要找到满足以下条件的x(l<=x<=r),使得数x的第一个数字与最后一个数字相等. 例如, 101, 477474,9101,477474,9是符合这个条件的,而47, 253, 102047,253,1020则不符合. 请帮助他找到符合这个条件的数的数目. 输入格式: 一行两个数l,r(1<=l<=r<=10^18),意义如上. 题解：数位dp模板 #include <bits/stdc++.h> #include <iostream> #include <...

#include <bits/stdc++.h> using namespace std; const int int = 1e9; const int maxn = 1e5 + 5; int a[maxn]; int Lmin[maxn], Rmin[maxn];//以当前位置为最小值,能扩展到哪里 int Lmax[maxn], Rmax[maxn];//以当前位置为最大值,能扩展到哪里 stack<int> s; int main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); int n; ci...

Problem DescriptionYou are given a string S consisting of only lowercase english letters and some queries. For each query (l,r,k), please output the starting position of the k-th occurence of the substring SlSl+1...Sr in S. InputThe first line contains an integer T(1≤T≤20), denoting the number of te...

#include <bits/stdc++.h> #include <iostream> #include <string.h> #include <math.h> using namespace std; const int maxn = 2e5 + 5; int head[maxn], tot, father[maxn]; int root, dp[maxn], mx; int n, k, u, v, w; struct Edge { int u, v, w, next; } edge[maxn]; void init() { memset(...

X 国有 n 座城市，n−1 条长度为 1 的道路，每条道路连接两座城市，且任意两座城市都能通过若干条道路相互到达，显然，城市和道路形成了一棵树。 X 国国王决定将 k 座城市钦定为 X 国的核心城市，这 k 座城市需满足以下两个条件： 这 k 座城市可以通过道路，在不经过其他城市的情况下两两相互到达。定义某个非核心城市与这 k 座核心城市的距离为，这座城市与 k 座核心城市的距离的最小值。那么所有非核心城市中，与核心城市的距离最大的城市，其与核心城市的距离最小。你需要求出这个最小值。 题解：先找出树直径的中心root，以它为根节点，然后dfs去二分深度找答案 #include <bit...

#include <bits/stdc++.h> using namespace std; const int maxn = 1e6 + 5; const int inf = 1e9; struct SA { int dp[maxn][20], sa[maxn], rak[maxn]; int tx[maxn], height[maxn], lg[maxn]; int n, m, p; char s[maxn]; struct node { int x, y, id; } a[maxn], b[maxn]; void rsort() { for (int i = 1; i <...

状态压缩裸题https://atcoder.jp/contests/dp/tasks/dp_o #include <bits/stdc++.h> #include <iostream> #include <string.h> #include <math.h> using namespace std; const int mod = 1e9 + 7; const int maxn = (1<<21) + 5; int dp[30][maxn]; int a[30][30], b[30]; vector<int> can[3...

有n个位置，每个位置最多可以放a[i]个物品，现在你有m个物品想要全部放到位子上，求共有多少种放法？ 设dp[i][j] 为前i个位置放了j个物品的方案数 然后我们可以想到枚举位置;然后在枚举前面一共放了多少个物品;在枚举当前位置放多少个物品代码：复杂度为O(n * m ^ 2) 很明显超时 for(int i = 1; i <= n; i++) { for (int j = 0; j <= m; j++) { for (int k = 0; k <= a[i]; k++) { dp[i][j] += dp[i - 1][j - k]; } } } 很明显枚举放了多少个物品是...

给你一个长度为n个序列，有两个人 Taro 和 Jiro，这两个人每次可以从序列的头部和尾部取数求x - y #include <math.h> using namespace std; typedef long double lld; typedef long long ll; const ll inf = 1e18; const int maxn = 3005; ll a[maxn], dp[maxn][maxn]; ll dfs(int l, int r) { if (l > r) return 0; if (dp[l][r] != inf) return dp[l][...

题意：给你N个硬币，每个硬币正面朝上的概率为p[i],反面朝上的概率为1 - p[i]求正面朝上硬币数量比反面朝上硬币的数量多的概率是多少 设dp[i][j] 为前i个硬币有j个硬币朝上的概率和 所以可得出转移方程为：dp[i][j + 1] += dp[i - 1][j] * p[i] //表示当前硬币为正面超市dp[i][j] += dp[i - 1][j] * (1 - p[i]) // 表示当前硬币问反面朝上 #include <bits/stdc++.h> #include <iostream> #include <string.h> #inclu...

对于一个正整数x，我们定义一次操作是将其变为它二进制下“1”的个数,比如我们知道13(10)=1101(2),而1101有三个"1",所以对13进行一次操作就会将其变为3。显而易见的是，对于一个正整数，我们在进行若干次操作后，一定会将其变为1。 给定n和k，其中n是在二进制下被给出，求出所有不大于n且将其变为1的最小操作次数为k的数的个数对10^9+7取模的结果。 因为strlen(str) <= 1000, 使用在预处理1-1000中变化到1时要多少步,中枚举1-1000,然后使用组合数学（） #include <bits/stdc++.h> #incl...

题目大意：给出n行m列01串，对于每一行所要花费的代价是行中第一个1和最后一个1之间的距离加一，现在你有魔法可以去除掉k个1，问去掉不多于k个1的情况下，你所能获得的最小代价是多少。 题解：每一天翘多少课所得到的价值都是互相独立的，那么就很容易想到将每一天都看成一个物品组，翘不同数量的课可以达到不同的最大价值，然后跑分组背包即可。 但由于翘课顺序不同导致的剩余价值也不同，所以直接贪心递推地删点是不可取的 我们考虑搞一个辅助DP，设w[i][j]为第i天翘了j节课所达到的最大价值。 由于我们翘课只有从两边翘才可达到最优，那我们对于一个确定的j，可以分别枚举左右两边翘课的数量。 分好组后，跑01背...