第23次CCF-CSP认证（含C++源码）

4006 数组推导

题目链接

输入输出及样例：

AC代码及解析

首先对于这道题目我们可以利用贪心的思想 对于最大值sum_max 我们B对应A的选择都尽可能取最大值
而对于最小值sum_min在选择的时候我们都尽可能取最小但不影响B

• 什么是选择？
  //例如在样例1中 我们的A在第四个位置上就会有选择
  //我们可以填0-5的任意一个数字 都不会影响B 所以我们如果求的是max我们就填5 那么min就填0
• 那么什么时候会出现选择呢 ？
  //不难发现 当B中的值出现重复的时候我们就可以进行选择了 直到下一个最大值出现

#include <bits/stdc++.h>
using namespace std;
const int N=110;
int n,sum_max,sum_min;
int B[N];

int main()
{
    cin>>n;
    for(int i=0;i<n;i++)
   {
    cin>>B[i];
   }//读入完成
     sum_max+=B[0];
     sum_min+=B[0];
   for(int i=1;i<n;i++)
   {
       if(B[i-1]==B[i])
       {
           sum_max+=B[i];//当B出现重复数值的时候
       }else{
           sum_max+=B[i];
           sum_min+=B[i];
       }
   }
   cout<<sum_max<<endl<<sum_min;//输出结束
    return 0;
}

4007 非零段划分

题目链接

AC代码及解析

solution 1(暴力 70%)

主要思路 是通过枚举所有可能的阈值p，统计每个阈值p下 数组被划分成的非零段数量，最终找到最大的非零段数量

#include <iostream>
using namespace std;
int num[500000];  // 存储输入的整数数组

int main()
{
    int n, p, phrase = 0; // 整数个数，当前处理的阈值p，最大非零段数
    int i, min = 10000, max = 0; // min和max分别记录数组中的最小值和最大值

    // 读取输入并确定数组中的最小值和最大值
    cin >> n;
    for(i = 0; i < n; i++)
    {
        cin >> num[i];
        if(num[i] < min)
            min = num[i];
        if(num[i] > max)
            max = num[i];
    }

    // 特殊情况处理：如果所有元素都相同，直接输出0
    if(min == max)
    {
        cout << 0;
        return 0;
    }

    int temp;     // 当前阈值下的非零段数
    bool flag;    // 标记是否处于一个新的非零段
    // 枚举所有可能的阈值p（从min到max-1）
    for(p = min; p < max; p++)
    {
        temp = 0;
        flag = true;  // 初始状态为允许开始新的非零段
        // 遍历数组，统计当前阈值p下的非零段数量
        for(i = 0; i < n; i++)
        {
            if(num[i] < p)  // 当前元素小于阈值，视为0
            {
                flag = true;  // 允许开始新的非零段
            }
            else  // 当前元素大于等于阈值，视为非零
            {
                if(flag)  // 如果允许开始新的非零段
                {
                    temp += 1;  // 非零段数量加1
                    flag = false;  // 标记当前处于一个非零段中，不允许开始新段
                }
            }
        }
        // 更新最大非零段数
        if (temp > phrase)
            phrase = temp;
    }

    cout << phrase;  // 输出最大非零段数
    return 0;
}

solution2 （AC 参考yxc思路）

• 考虑p足够大的情况，这时所有的岛都被海水淹没了，只有0个岛屿
  然后海平面逐渐下降，岛屿数量开始变化
• 每当一个凸峰出现，岛屿数就会多一个；
• 每当一个凹谷出现，原本相邻的两个岛屿就被这个凹谷连在一起了，岛屿数减少一个
  可以使用数组cnt[]，cnt[i] 表示海平面 下降 到i时，岛屿数量的变化

这样，数组元素cnt[i]中存储的就是该元素被替换为0时，划分数变化的差分值
最大值则只需要从其前缀和（程序中实际为 后缀和）中找出最大值
代码参考

#include <iostream>
#include <algorithm>
using namespace std;

const int N = 500004, M = 10004;
int n, a[N], cnt[M];  // a[]存储数组，cnt[]存储每个高度的差分变化

int main()
{
    scanf("%d", &n);
    for(int i = 1; i <= n; i++)
        scanf("%d", &a[i]);

    a[0] = a[n + 1] = 0; // 设置边界为0，方便处理
    n = unique(a, a + 2 + n) - a; // 去重并更新数组长度，确保相邻元素不重复
    
    // 统计每个关键点（凸峰和凹谷）的差分变化
    for(int i = 1; i < n; i++)
    {
        if(a[i - 1] < a[i] && a[i] > a[i + 1]) // 凸峰：当海平面下降到a[i]时，新增一个岛屿
            cnt[a[i]]++;
        else if(a[i - 1] > a[i] && a[i] < a[i + 1]) // 凹谷：当海平面下降到a[i]时，合并两个岛屿
            cnt[a[i]]--;
    }

    int res = 0, sum = 0;
    // 从高到低遍历所有可能的高度，计算后缀和并记录最大值
    for(int i = M; i; i--)
    {
        sum += cnt[i];  // 累加差分变化，得到当前高度的岛屿数
        res = max(res, sum);  // 更新最大岛屿数
    }
    printf("%d\n", res);  // 输出结果
    return 0;
}

4009 收集卡牌

题目链接

输入输出及样例解释

AC代码及解析

基本思路：

• 1 明确状态和选择

状态就是会改变的量 在本题中 分别是 收集到的不同卡牌的数量 手里硬币的个数 以及 剩余还有几种卡牌没拿到

选择就是我们每回合进行抽牌
如果抽到已有的卡牌，获得 1 个硬币，卡牌集合不变。
如果抽到新卡牌，卡牌集合更新，硬币数量不变。

• 2 明确dp数组的含义

f[state][coins] 表示在当前已收集卡牌状态为state、拥有coins个硬币时，收集完所有卡牌所需的期望回合数。

• 3.根据选择 写出状态转移方程

抽到已有卡牌 f[state][coin]+= p[i] * (dp(state, coins + 1, r) + 1)
抽到新卡 f[state][coin]+= p[i] * (dp(state | (1 << i), coins , r-1) + 1)

注：由于我们是使用 16位二进制数来表示卡牌的状态的 所以这里在更新卡牌状态的时候会涉及位运算的操作 其实我们在二分查找的时候就有涉及 只不过等价于（left+right)/2
这里state | (1 << i)的意思就是说明把第i位上的数字置为1 在本题中就是表示抽到了第i个新的卡片

#include <bits/stdc++>h>
using namespace std;

const int N = 16, M = 1 << N;
int n, m;
double p[N];
// f[000...0000][N * 5 + 1]
// k <= 5，意味着最多有 N * 5 张卡片（当然不可能有这么多）
// 第一个参数state 二进制表示牌是否被抽到，抽到是1，反之为0
// 第二个参数coin 表示硬币状态
double f[M][N * 5 + 1];

double dp(int state, int coins, int r) {
    // v = f[state][coins] 记录下来
    auto& v = f[state][coins];
    // 之前已经算过了，直接返回
    if (v >= 0) return v;
    // 直接买下所有，所需次数为0
    if (coins >= r * m) return v = 0;
    // 以上两种都不是，也就是还要往下算，先初始化次数为0
    v = 0;
    // 遍历各种卡牌种类
    for (int i = 0; i < n; i ++) {
        // 如果state里面该种卡牌已经被抽到过
        if (state >> i & 1) {
            // 卡牌状态不变，硬币加一个，没抽到的卡的数量不变，回合数+1
            v += p[i] * (dp(state, coins + 1, r) + 1);
        }
        // 没有抽到过
        else {
            // 卡牌状态更新，硬币数量不变，没抽到的卡的数量-1，回合数+1
            v += p[i] * (dp(state | (1 << i), coins, r - 1) + 1);
        }
    }
    return v;
}

int main() {
    cin >> n >> m;
    for (int i = 0; i < n; i ++) {
         cin >> p[i];
    }
    // 初始化为-1，不是-1说明可以直接返回
    memset(f, -1, sizeof f);
    // 初始有0张卡，0个硬币，还剩n张卡片没有拿
    printf("%.10lf\n", dp(0, 0, n));
    return 0;
}