给出n个数字，我们来逐步删除，如果一个子串是回文数，就可以直接删除，问删除完最少的次数。设dp[i][j]为删除区间[i,j]所需最小次数题解：记忆化搜索  #include <bits/stdc++.h> using namespace std; const int maxn = 505; const int inf = 1e9; int dp[maxn][maxn], a[maxn]; int dfs(int i, int j) { if (i >= j) return 1; if (dp[i][j]) return dp[i][j]; int ans = inf; if...

设f[i][j]为第i层的第j个数，可得 f[i][j] = f[i - 1][j - 1] ^ f[i - 1][j] #include <bits/stdc++.h> using namespace std; typedef long long ll; const int maxn = 5005; ll dp[maxn][maxn], f[maxn][maxn]; int main() { int n, m, l, r; scanf("%d", &n); for (int i = 1; i <= n; i++) { scanf("%l...

kefa进入了一家餐厅，这家餐厅中有n个菜（0<n<=18）,kefa对第i个菜的满意度为ai（0<=ai<=10^9），并且对于这n个菜有k个规则，如果kefa在吃完第xi个菜之后吃了第yi个菜（保证xi、yi不相等），那么会额外获得ci（0<=ci<=10^9）的满意度。kefa要吃m道任意的菜（0<m<=n），但是他希望自己吃菜的顺序得到的满意度最大，请你帮帮kefa吧！ 输入第一行是三个数：n,m,k 第二行是n个数，第i个数表示kefa对第i道菜的满意度为ai 第三行到第k+2行每行有3个数：xi，yi，ci，表示如果kefa在吃完第x...

题意：给你两个字符串s 和 t ， 然后在s中找k个不重叠的子串， 并且能够在t中按顺序 能找出这k个子串， 求这k个子串的最大长度和 dp[i][j][t][0] ，i是在s中的位置， j是在t中的位置，i，j跟求最大公共子串一样， t是当前子串的个数， 1说明还能继续匹配子串个数不用加，  0说明匹配结束要加个子串继续匹配 转移方程为：如果s[i] == t[j] dp[i][j][t][1] = max(dp[i - 1][j - 1][t - 1][0], dp[i - 1][j - 1][t][1]) + 1dp[i][j][t][0] = max(dp[i - 1][j][t][0...

有n个人，要写m行代码，第i个人每写一行会出现ai个bug，每个人可以写任意行，但总bug数不能超过b个，求总方案数 dp[j][k] 表示有j行代码k个bug的方法数,所有转移方程为：类似一维完全背包dp[j + 1][k + a[i]] += dp[j][k]  #include <bits/stdc++.h> using namespace std; const int maxn = 1005; int dp[maxn][maxn]; int a[maxn]; int main() { int n, m, b, mod; cin >> n >> m &...

#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<ll,ll> pll; const pll mod = make_pair(1e9 + 7, 1e9 + 9); const pll base = make_pair(10007, 10009); const int maxn = 1e6 + 5; const int maxm = 1e6; char str[maxn]; pll fac[maxn]; map<pll, int> mp; struc...

给出n个已知字符串，m次询问，每次询问给出一个字符串，问上面n个字符串中是否有一个字符串满足恰好有一个字母不同于询问的字符串。（字符串的字符集为{'a','b','c'}）n,m<=3e5,输入总长度不超过6e5。 注意：这里如果使用hash自动溢出会被卡掉，所以使用双hash #include <bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<ll,ll> pll; const int maxn = 1e6 + 5; const int maxm = 1e6; char...

给定一棵包含N个节点的带权树，节点编号1~N。小Hi每次会给定树上两个节点的编号u和v，请你计算从u到v的路径上，哪条边的权值最小。  请你输出最小的权值。 输入第一行包含两个整数N和Q，代表节点数和询问次数。 以下N行每行包含一个整数Pi, Wi，代表1~N的父节点的编号，以及(i, P[i])这条边的权值。其中根的父节点编号为0，这一行的Wi也为0。 以下Q行每行包含两个整数u和v，代表一个询问。  1 <= N, Q <= 100000 1 <= u, v <= N 0 <= Wi <= 1000000000 题解：求树上的两点间的最小值，我们可以想求...

#include <bits/stdc++.h> using namespace std; typedef long long ll; const ll mod = 1e9 + 7; const int maxn = 1e6 + 5; const int maxm = 1e6; ll L[maxn], R[maxn], fac[maxn]; char s1[maxn], s2[maxn]; int n, m; void initHash() { for (int i = 1; i <= m; i++) { L[i] = L[i - 1] * mod + s2[i]; } fo...

链接：https://ac.nowcoder.com/acm/problem/15710来源：牛客网 题目描述给一个1-base数组{a}，有N次操作，每次操作会使一个位置无效。一个区间的权值定义为这个区间里选出一些数的异或和的最大值。求在每次操作前，所有不包含无效位置的区间的权值的最大值。 输入描述:第一行读入一个正整数(1 <= n <= 105) 第二行读入n个正整数，第i个表示a[i](0<= a[i] <= 109) 第三行读入n个正整数，第i个表示x[i]即第i次操作的位置，保证x[i]互不相同。 输出描述:输出n行答案示例1输入复制10169 816 70...

#include <bits/stdc++.h> using namespace std; //线性基模板 struct Lbase{ typedef long long ll; ll p[64], q[64], tot; bool zero; Lbase() { memset(p, 0, sizeof(p)); tot = 0; zero = false; } //插入线性基（false插入失败） （true插入成功） bool insert(ll x) { for (int i = 62; i >= 0; i--) { if ((x >> i) & 1...

#include <bits/stdc++.h> using namespace std; typedef long long ll; struct Field { ll mod = 1000000007; //扩域 first实部 second虚部 typedef pair<ll, ll> pll; ll qpow_num(ll a, ll b) { ll ans = 1; while (b) { if (b & 1) { ans = (ans * a) % mod; } b >>= 1; a = (a * a) % mod; } return a...

已知0<=x<=y<p,p=1e9+7且有(x+y)=bmodp(x×y)=cmodp求解任意一对x,y，不存在输出−1 −1。 由两式变化可得(y−x)2=(b2−4c+p)%p mod p，那么可以应用二次剩余定理解得y−x的值，我们可以知道(x+y)=b或者(x+y)=b+p，那么直接求解即可。 #include <bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<ll,ll> pll; ll qpow_num(ll a, ll b, ll mod) { ...

给出一段区间a-b，统计这个区间内0-9出现的次数。 数位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 = 22; int digit[maxn], tot, d; ll dp[maxn][22][22]; ll dfs(int len, int top, in...