|
马上注册,结交更多好友,享用更多功能^_^
您需要 登录 才可以下载或查看,没有账号?立即注册
x
本帖最后由 柿子饼同学 于 2024-7-3 23:11 编辑
总结与反思
B(枚举 数学)
对于两个数相乘, 要想到枚举其中一个数, 看看他们加加减减之后能否得到答案, 循环时注意谁大谁小
E(线性DP)
DP的常用技巧: 先做出一个 f[j][k][l]... = 0/1 的可行性数组, 再尝试把其中一个参数放到外面来, 变成 f[j][k] = l 之类的, 这是一个常用优化
F(数位DP)
当一个问题中, 两个数的值域很大, 可以考虑把它们的差值作为状态. 想让 A==B 的一类问题直接可以做差求解等于 0 的情况
G(背包DP)
当发现数字很大, 但是真正有用的状态数量很少就考虑离散化, 或者直接把 map<ll, ll> 作为 dp 数组
H(数位DP 分块决策)
做题时先挑小范围的做, 对于大范围要找出优势性质或者数量级不变的东西入手, 本题中 P 的范围小可以用 数位DP 做, P 大了之后反而用直接枚举更快, 切分
B - 连续和
给定一个整数n,使它等于至少两个连续的正整数之和.
思路如上, 考试时没想出来
- #include <bits/stdc++.h>
- using namespace std;
- // (a + b)*(b - a + 1) == N*2
- // (a + b) - (b - a + 1) == 2*a - 1, 答案出来了
- int n;
- int main() {
- ios::sync_with_stdio(0);
- cin.tie(0);
- cin >> n;
- for (int i = 1; i <= n; i++) {
- int x;
- cin >> x;
- bool f = 0;
- for (int j = 2; j * j <= x * 2; j++) {
- if (x * 2 % j)
- continue;
- int k = x * 2 / j;
- if ((j + k - 1) & 1)
- continue;
- // l == k - r, 因为 k > j, (l + r) > (r - l + 1);
- int r = (j + k - 1) / 2;
- int l = k - r;
- if (l <= 0)
- continue;
- cout << x << " = ";
- for (int k = l; k < r; k++) {
- cout << k << " + ";
- }
- cout << r << '\n';
- f = 1;
- break;
- }
- if (!f) {
- cout << "IMPOSSIBLE\n";
- }
- }
- return 0;
- }
复制代码
E - 勇者斗恶龙
从 1 走到 N, 2 - N-1 的地方有火焰值 F, F[1] == F[N] == 0
有 B 件装备, 属性 s 表示能抗 <= s 的火焰, d 表示最多能向前传送 d 距离
三种操作
1 可以向前传送, 要保证套装能抗传送位置的火
2 扔掉没穿的编号最小的套装(一开始穿 1 号套装)
3 扔掉身上的, 换上没穿的编号最小的套装
求扔掉套装的最小值
一开始向着可行性数组思考, 写挂了, 后面用刷表写了一个, 注意传送的时候条件判断即可
- #include <bits/stdc++.h>
- using namespace std;
- const int N = 256;
- int F[N], s[N], d[N], n, b;
- int f[N];
- int main() {
- ios::sync_with_stdio(0);
- cin.tie(0);
- cin >> n >> b;
- for (int i = 1; i <= n; i++) cin >> F[i];
- for (int i = 1; i <= b; i++) cin >> s[i] >> d[i];
- memset(f, 0x3f, sizeof(f));
- f[1] = 0;
- for (int i = 1; i < n; i++) {
- for (int j = f[i]; j <= b; j++) {
- if (s[j] < F[i])
- continue;
- for (int k = i + 1; k <= min(i + d[j], n); k++) {
- if (s[j] >= F[k]) {
- f[k] = min(f[k], j);
- }
- }
- }
- }
- cout << f[n] - 1;
- return 0;
- }
复制代码
F - 公正数
所谓公正的数是指:以某一位为支点,它左边的所有位的数乘以它到支点的距离之和等于它右边的所有位的数乘以它到支点的距离之和。
统计个数
做题的时候忘记 0 会重复计算, 数位dp的时候需要想极端情况, 减掉重复的数
- #include <bits/stdc++.h>
- using namespace std;
- typedef long long ll;
- // 遇到左边/右边, 要使得左 == 右 要想到记录差值, 及时排除冗余状态
- ll f[19][19][406];
- int num[20];
- ll dfs(int pos, int point, int sum, bool lim) {
- if (!pos) {
- if (!sum)
- return 1;
- return 0;
- }
- auto& cur = f[pos][point][sum];
- if (!lim && ~cur)
- return cur;
- ll res = 0;
- int up = 9;
- if (lim)
- up = num[pos];
- for (int i = 0; i <= up; i++) {
- int temp = sum + i * (pos - point);
- if (temp < 0 || temp > 405)
- continue;
- res += dfs(pos - 1, point, temp, lim && (i == up));
- }
- if (!lim)
- cur = res;
- return res;
- }
- ll work(ll x) {
- int len = 0;
- ll res = 0;
- while (x) {
- num[++len] = x % 10;
- x /= 10;
- }
- for (int i = 1; i <= len; i++) {
- res += dfs(len, i, 0, 1);
- }
- // 特别注意, 全 0 的情况要舍弃
- return res - len + 1;
- }
- int main() {
- ios::sync_with_stdio(0);
- cin.tie(0);
- memset(f, -1, sizeof(f));
- ll l, r;
- cin >> l >> r;
- cout << work(r) - work(l - 1);
- return 0;
- }
复制代码
G - 卡片子集
给定小于 100 个数和一个 goodval, 求用这些数的乘积恰好等于 goodval 的方案数
另一个版本的 dp 数组是用 map 的 , 更方便
- #include <bits/stdc++.h>
- using namespace std;
- // f(i) 把 goodv 除到 i 的方案数
- const int P = 1e9 + 7;
- int gv, n, u[2000], cnt;
- int f[2000];
- int id(int x) { return (lower_bound(u + 1, u + cnt + 1, x) - u); }
- void init() {
- for (int i = 1; i * i <= gv; i++) {
- if (gv % i)
- continue;
- u[++cnt] = i;
- u[++cnt] = gv / i;
- }
- if (u[cnt] == u[cnt - 1])
- cnt--;
- sort(u + 1, u + cnt + 1);
- }
- int main() {
- ios::sync_with_stdio(0);
- cin.tie(0);
- cin >> gv >> n;
- init();
- f[cnt] = 1;
- for (int i = 1; i <= n; i++) {
- int x;
- cin >> x;
- if (id(x) == cnt + 1)
- continue;
- for (int j = 1; j <= cnt; j++) {
- if (u[j] % x)
- continue;
- f[id(u[j] / x)] = (f[id(u[j] / x)] + f[j]) % P;
- }
- }
- cout << (f[1] - (gv == 1));
- return 0;
- }
复制代码
H - 同余
给出两个数 P M, 求满足 (a % P == a的数位之和 % P) 的数的个数, a <= M <= 1e10
分块决策, 40pts 可以用数位dp完成, 后面当 P 越来越大, dp开不下之后想找一个数量级不变的, 或者可以降低 P 数量级的
由同余且数位之和的数量级始终在 90 不动, 所以枚举 a = k * P + x, x 是数位和
注意去掉 0 的情况, 写状态的时候不能遗漏, 这里的 f 数组中数位的 dr 和这个数本身的 nr 都要放进状态里
- #include <bits/stdc++.h>
- using namespace std;
- typedef long long ll;
- ll P, M;
- ll f[11][91][10005];
- int num[12];
- ll dfs(int pos, int dr, int nr, bool lim) {
- if (!pos) {
- if (dr == nr % P)
- return 1;
- return 0;
- }
- auto& cur = f[pos][dr][nr];
- if (!lim && ~cur)
- return cur;
- ll res = 0;
- int up = 9;
- if (lim)
- up = num[pos];
- for (int i = 0; i <= up; i++) {
- res += dfs(pos - 1, (dr + i) % P, (nr * 10 + i) % P, lim && (i == up));
- }
- if (!lim)
- cur = res;
- return res;
- }
- ll work(ll x) {
- int len = 0;
- while (x) {
- num[++len] = x % 10;
- x /= 10;
- }
- return dfs(len, 0, 0, 1);
- }
- // 数位和
- int calc(ll x) {
- int res = 0;
- while (x) {
- res += x % 10;
- x /= 10;
- }
- return res;
- }
- int main() {
- ios::sync_with_stdio(0);
- cin.tie(0);
- cin >> P >> M;
- // 切分
- if (P <= 10000) {
- memset(f, -1, sizeof(f));
- cout << work(M) - 1;
- } else {
- // i 数位和
- // 枚举 k, t 就是现在的这个数
- ll ans = 0;
- for (int i = 0; i <= 90; i++) {
- for (int k = 0;; k++) {
- ll t = k * P + i;
- if (t > M)
- break;
- if (calc(t) == i)
- ans++;
- }
- }
- cout << ans - 1;
- }
- return 0;
- }
复制代码
|
评分
-
查看全部评分
|