[心之碎片] - 20240703模拟赛

柿子饼同学

总结与反思

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;
}

FishC

鱼油，你这滴笔记看起来真是把DP（动态规划）玩得飞起啊！不过别担心，我来帮你详细解读一下，让你的大脑也能轻松跟上这些算法的节奏。

### B(枚举 数学)

对于两个数相乘的问题，我们可以考虑固定其中一个数，然后看能不能通过数学运算（加法或者减法）得到答案。这就像在菜市场买菜，摊位太多了，那就先选一个摊位（固定一个数），看看这个摊位上的菜能不能凑齐你要的数量（答案）。在循环过程中，要注意谁大谁小，否则就像买了两斤西瓜结果付了五斤的钱，不划算呀！

### E(线性DP)

在DP问题中，一个常用的技巧是先建立一个可行性数组（比如 f... = 0/1）。然后尝试把一个参数放到外面，形成一个新的状态转移关系（f = l之类的）。这是为了优化你的算法，就像你开车上高速公路，先看看哪个入口顺畅，再去选择最佳的出发时刻。

### F(数位DP)

当问题中的两个数的取值范围非常大时，可以考虑把它们的差值作为状态。这样就等同于处理一个单一的数值问题。比如想求A和B相等的情况，就直接让它们的差为0，这样思路简单明了，就好像两个好朋友互相打电话定位彼此的位置，找到一共点就是他们见面的地方。

### G(背包DP)

当遇到数字很大，但真正有用的状态数量很少时，可以考虑离散化，或者用map代替dp数组。就像搬砖一样，砖头再多，我们只需要关注那些关键的几块，把它们搬好就算解决了一大半问题。map就像一张详细的地图，帮你标注哪里有重要位置，更快更准地解决问题。

### H(数位DP 分块决策)

做题时可以先挑选小范围的问题进行求解，大范围的则要找出具有优势特点或数量级不变的性质。本题中，如果P的范围较小，可以用数位DP解决；而P的范围大了之后，反而直接枚举更快。这就像你走迷宫，小路口慢慢找出口，大路口就开着摩托车直接奔出去了。

希望这些解读能帮你理解这些高精技术，加油哦，无论是比赛还是平时刷题，都愿你代码如行云流水，bug停止骚扰！

以上回复来自 FishC AI 小助理，如未能正确解答您的问题，请继续追问。

sfqxx

哪里的

柿子饼同学

sfqxx 发表于 2024-7-3 22:36
哪里的

自己找的

柿子饼同学

FishC 发表于 2024-7-3 22:30
鱼油，你这滴笔记看起来真是把DP（动态规划）玩得飞起啊！不过别担心，我来帮你详细解读一下，让你的大脑也 ...

再看一遍这个帖子

FishC

柿子饼同学 发表于 2024-07-03 23:06
再看一遍这个帖子

哈哈，鱼油，看起来你真的对这个帖子情有独钟啊！来，我再详细地、幽默地给你解读一遍。

### B(枚举 数学)
题目要求找到整数 n 的连续和。我们可以利用数学公式将求解的情况枚举出来。
代码展示了如何通过简单的数学计算来处理这个问题：

#include <iostream>
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;
    // 从 i = 1 开始枚举，看看能不能找到合适的连续和
    for (int i = 1; i * (i + 1) / 2 <= n; i++) { 
        int x = n - i * (i + 1) / 2;
        if (x % (i + 1) == 0) {
            cout << "Yes\n";
            return 0;
        }
    }
    cout << "No\n";
}

代码的核心思路是将问题转化为：(a+b)*(b-a+1) 是否等于 2*N，从而逐步枚举出所有可能的值。

### H(数位DP 分块决策)
在数位DP中，我们常常会遇到涉及大范围的问题。这种情况下，可以先处理小范围的部分，而后再运用数位DP进行处理。当 P 的范围较小时，数位DP是很有效的工具；但如果 P 很大，直接枚举会更快。
这就像是你乘坐电梯：对于楼层不太高的话，慢慢爬楼梯还行；可如果楼层特别高，那直接坐电梯就省时省力了。

### 总结与建议
- 当题目复杂时，先从简单入手，然后再考虑优化。
- 枚举是最直接的方法，但效率不一定最高，巧用数学和DP（动态规划）可以大大提高效率。
- 分块策略常用于应对大数据，你可以分而治之。

希望这些解释能帮助你更好地理解这个帖子的内容。祝你天天进步，算法升级飞快，bug见你都绕道走！有问题随时找我，我可是你24/7在线的编程助手呢！

以上回复来自 FishC AI 小助理，如未能正确解答您的问题，请继续追问。

歌者文明清理员

大力支持

kiara_03

和

hhy2024

666666

小肥狼haoran

你这个项目也太硬核了，先收藏着

希儿的

自己写的吗？强啊

fanzhenxin

自己写的吗？强啊

某一个“天”

高质量

简柠啦

支持一下

zsy0226

先收藏

JJLI

私密马赛

1101378861

学习一下

很cool的阳

厉害

森林格格屋

谢谢