题目链接：codeforces 1581C 题解 定义 dp[i] 为前 列最小的花费。枚举时先枚举上下边，在对列 DP。因为第 列可能是边界，也可能在后面的过程中变成中间的部分，所以每次单独计算，而不算在 dp[i] 里面。 参考代码 1234567891011121314151617181920212223242526272829303132333435363738394041#include <iostream>#include <cstring>using namespace std;const int N = 550;int maze[N][N];int tot0[N][N], tot1[N][N];int dp[N];int count0(int i, int j, int k) { return tot0[j][k] - tot0[i-1][k];}int count1(int i, int j, int k) { return tot1[j][k] - tot1[i-1][k];}int main() { int t; ...
题目链接：codeforces 1603A 题解 从头开始删数字，对于每个数字 ，如果它不能被 ~ 的数整除，说明它可以被删除。 参考代码 1234567891011121314151617181920212223#include <iostream>using namespace std;const int N = 1e5 + 10;int a[N];int n;int main() { int t; cin >> t; while (t--) { cin >> n; for (int i = 1; i <= n; i++) cin >> a[i]; int flag, ff = 0; for (int i = 1; i <= n; i++) { flag = 0; for (int j = 2; j <= i+1; j++) { if (a[i]%j) {flag = 1; break;} ...
题目链接：codeforces 1228C 题解 是所有 的质因子在 中出现次数的乘积，题目要求 ~ 的乘积，故对于每个质因子，统计其出现次数，再求乘积即可。 参考代码 123456789101112131415161718192021222324252627282930313233343536373839404142#include <iostream>using namespace std;typedef long long ll;const int mod = 1e9 + 7;const int N = 1e5 + 10;int prime[N];int tot;ll qpow(ll a, ll b, ll MOD = mod) { ll res = 1; a %= MOD; while (b > 0) { if (b & 1) { res = res * a % MOD; } a = a * a % MOD; b >>= 1; } ...
题目链接：codeforces 1486D 题解 二分中位数，每次将大于等于 mid 的数标记为 ，否则标记为 。 我们要找到一个长度为 k 的区间，枚举右端点，每次只要找到一个左端点，使区间 的和大于 （因为中位数是向下取整，故不能取到等号），用前缀和维护即可。 因为是在区间 寻找左端点，且区间是连续的，故维护最小的前缀和，只要这个区间和大于 满足条件即可。 参考代码 1234567891011121314151617181920212223242526272829303132333435363738#include <iostream>using namespace std;const int N = 2e5 + 10;int n, k;int a[N];int b[N]; // 标记数组int pre[N]; // 记录前i个前缀和int mn[N]; // 记录前i个最小的前缀和void init() {for (int i = 1; i <= n; i++) b[i] = pre[i] = 0, mn[i] = 0x3f3f3f3f;}bool c ...
题目链接：codeforces 837D) 题解 要求结果的 最多，不难想到这个数的因子 和 的个数尽可能多。故将每个数分解，然后就是一个比较简单的背包问题。 参考代码 12345678910111213141516171819202122232425262728293031323334353637383940414243#include <iostream>#include <cstring>using namespace std;typedef long long ll;const int N = 220;int cnt2[N], cnt5[N];int dp[N][5010]; // 前i个数，有j个5（也可以计2的个数，不过空间大点）能得到的最多的2的个数void get2(ll num, int pos) { while (num % 2 == 0) { cnt2[pos]++; num /= 2; }}void get5(ll num, int pos) { while (num % 5 == ...
题目链接：codeforeces 1119D 题解 数据这么大一定是找规律…… 求区间里数的个数，与顺序无关，不妨先排个序。不难发现当 时，就会又重叠的部分。于是想到差分，并对差分数组排序，用前缀和维护前面有重叠的部分。二分查找有重叠和未重叠的分界，即第一个大于等于 len 的下标。 参考代码 1234567891011121314151617181920212223242526272829303132#include <iostream>#include <algorithm>#include <cstring>using namespace std;typedef long long ll;const int N = 1e5 + 10;ll a[N], d[N], pre[N];int main() { int n, q; cin >> n; for (int i = 1; i <= n; i++) { cin >> a[i]; } sort(a+1, a+1+n); ...
题目链接：codeforces 1188C 题解 美丽值与顺序无关，故对数组排序，子序列的美丽值就是所有相邻数的差值的最小值。 设美丽值为 的子序列个数为 cnt[x]，那么美丽值为 的子序列个数为 cnt[1]，它对答案的贡献为 cnt[1]*1，相似的，美丽值为 的子序列对答案的贡献为 cnt[2]*2，差值的最大值为 ，故最后的答案为： 不难发现答案就是 cnt 的后缀和 suf的和，suf[i] 表示美丽值不小于 的方案数。于是，我们可以枚举美丽值 。令 dp[i][j] 为最后一位为 ，长度为 ，差值不小于 的子序列。定义状态转移方程： 因为 是递增的，所以用前缀和求这个 ，最后算出的 dp[n][k] 就是美丽值不小于 的方案数。时间复杂度为 。 可优化 dp 范围。长度为 的子序列最大差值为 ，而美丽值最大值是 ，故现在只要求 的范围即可，时间复杂度为 。 参考代码 123456789101112131415161718192021222324252627282930#include <iostream>#include <al ...
题目链接：codeforces 1199C 题解 将 离散化，前缀和维护区间个数。枚举区间起点，二分查找终点，取最大值。 参考代码 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354#include <iostream>#include <map>#include <algorithm>#include <cstring>#include <cmath>using namespace std;typedef long long ll;const int N = 4e5 + 10;const int inf = 0x3f3f3f3f;int n, I;ll a[N], b[N], pre[N];ll count(ll l ,ll r) { return pre[r] - pre[l-1];}bool check(ll l, ll r) { int k = r - l ...
题目链接：codeforces 1519D 题解 区间 dp /记忆化深搜，定义dp[i][j]为翻转区间 的前后差值。状态转移方程为dp[l][r] = dfs(l+1, r-1) + a[r] * b[l] + a[l] * b[r] - a[l] * b[l] - a[r] * b[r]。 参考代码 123456789101112131415161718192021222324252627282930#include <iostream>#include <cstring>using namespace std;typedef long long ll;const int N = 5e3 + 10;ll a[N], b[N], dp[N][N];ll dfs(int l, int r) { if (l >= r) return 0; if (dp[l][r] != -1) return dp[l][r]; dp[l][r] = dfs(l+1, r-1) + a[l] * b[r] + a[r] * b[l] - a[l] * ...
题目链接：codeforces 1041D 题解 显然，为了尽可能覆盖多的区间，起点一定是某段区间的左端点，故枚举左端点，二分查找终点，下降的高度用前缀和记录即可。 参考代码 12345678910111213141516171819202122232425262728293031323334353637383940#include <bits/stdc++.h>using namespace std;typedef long long ll;const int N = 2e5 + 10;int n, h;struct Node{ int x1, x2;}node[N];int pre[N]; // 记录上一个区间的右端点到当前区间左端点距离bool check(int start, int end) { return pre[end] - pre[start] < h; // 如果还可以下降，终点还可以往右}int main() { cin >> n >> h; for (int i = 1; i <= n ...
