题解：P10914 [蓝桥杯 2024 国 B] 跳石头

· · 题解

题目大意：

小明在玩一个跳石头的小游戏。游戏中有 n 块石头，按顺序排列为第 1 块到第 n 块。每块石头上写有一个正整数权值，第 i 块石头的权值为 c_i，让你求所有的方案中不同权值的个数最大是多少。

这一题的解法（我想到的）是 DP。因为它满足 DP 的特征：

  1. 小的子问题会影响大的子问题，但反过来没有影响。
  2. 一定有最小的子问题。
  3. 一定会储存中间的结果。
  4. 所有的子问题结构相似。

解题思路：

我们可以用 1 表示可以走到的地方，0 表示不可以走到的地方，再将这些数字串起来，就会发现：好像一个二进制的数字！

所以，我们可以用某个容器：bitset。

首先，我们要知道：bitset 是什么？（其实我也不会，上百度查了一下……）

bitset 是 C++ 标准库中的一个模板类（对我来说很陌生），用于表示固定大小的二进制位序列。它的每个位只能是 0 或 1，并且支持位运算（比如按位与、按位或、按位异或等）。

定义：

bitset<8> a("10010010");//定义一个长度为8的二进制数。

在这道题中，有什么用呢？

在这道题，我们可以对于两个集合，运用 bitset 支持的按位异或的操作来合并这两个集合（方法：如果这个位置 a 集合的数为 1，b 集合的数为 1；或者这个位置 a 集合的数为 0，b 集合的数为 1；或者这个位置 a 集合的数为 1，b 集合的数为 0；那么这个位置 c 集合的数为 1。否则为 0）。

具体使用方式：

bitset<8> a("10001000");
bitset<8> b("10101001");
bitset<8> c = a | b;

最终 c 的答案是：10101001。

回归本题：

因为有题目所说的从 x 可以移动到 x+c_i，所以我们要从后往前遍历（不然从前往后遍历的话 x-c_i 就很难得出这个点是从哪里来的）。

然后，对于一个点 x，我们可以从这个点到达 2x 或者 x+c_i（当然，要确保不能越界），所以就可以得到以下公式：

if(i + c[i] <= n){
    dp[i] |= dp[i + c[i]];
}
if(i * 2 <= n){
    dp[i] |= dp[i * 2];
}

最后，就是初始化了。对于一个点 x，如果从这里开始走的话，那么这个集合里就只有这一种权值，所以 dp[i] = 1。

AC 代码：

AC 记录（cin），AC 记录（快读快输）。

#include<bits/stdc++.h>
#define int long long
using namespace std;

int n;
int c[100005]; //权值数组
bitset<100005> dp[100005];//定义一个bitset，这里像是一个二维数组。
int ans;

template<typename T>inline void readT(T &x){
    bool f = 1;
    x = 0;
    char ch = getchar();
    while(ch < '0' || ch > '9'){if(ch == '-')f = !f;ch = getchar();}
    while(ch >= '0' && ch <= '9'){x = (x << 1) + (x << 3) + (ch ^ 48);ch = getchar();}
    x = (f ? x : -x);
    return ;
}

template<typename T>
inline void writeT(T x){
    if(x < 0)putchar('-'),x = -x;
    if(x > 9)writeT(x / 10);
    putchar(x % 10 + '0');
    return ;
}
//上面是快读快输，可以不用。
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
//  cin >> n;
//  如果不想用快读，就用cin
    readT(n);
    for(int i = 1 ; i <= n ; i++){
//      cin >> c[i];
        readT(c[i]);
    }
//  输入
    for(int i = n ; i >= 1 ; i--){//从后往前遍历。
        dp[i][c[i]] = 1;
        //初始化，可以在输入时一起。
        if(i + c[i] <= n){
            dp[i] |= dp[i + c[i]];
        }
        if(i * 2 <= n){
            dp[i] |= dp[i * 2];
        }
        //注意这里要求方案数，所以是直接累加，不是在中间取max。
        ans = max(ans,(int)(dp[i].count()));
        //注意bitset访问要用.count()，这里还强制转换了一下类型。
    }
    writeT(ans);
    puts("");//输出，最后加一个换行。
    return 0;
}

本蒟蒻的唯一一篇写得这么详细的题解，求管理员大大给过！