​​​​​​​​48days强训——day14

​ 📔个人主页📚：Shawn_Griffin-CSDN博客 ☀️专属专栏✨：OJ刷题 🏅往期回顾🏆：​48days强训——day13 🌟其他专栏🌟：OJ刷题

第一题：乒乓球筐

链接：乒乓球筐__牛客网

nowcoder有两盒（A、B）乒乓球，有红双喜的、有亚力亚的……现在他需要判别A盒是否包含了B盒中所有的种类，并且每种球的数量不少于B盒中的数量，该怎么办呢？ 输入描述: 输入有多组数据。 每组数据包含两个字符串A、B，代表A盒与B盒中的乒乓球，每个乒乓球用一个大写字母表示，即相同类型的乒乓球为相同的大写字母。 字符串长度不大于10000。 输出描述: 每一组输入对应一行输出：如果B盒中所有球的类型在A中都有，并且每种球的数量都不大于A，则输出“Yes”；否则输出“No”。 示例1 输入 ABCDFYE CDE ABCDGEAS CDECDE 输出 Yes No

题解：利用哈希表存储A中的字符串，再用哈希表减去B中的字符串进行判断即可。

代码：

#include <iostream>
using namespace std;

int main() 
{
    string s1,s2;
    while(cin >> s1 >> s2)
    {   
        bool flag = true;
        int hash[26]={0};
        for(auto x : s1)
        {
            hash[x-'A']++;
        }
        for(auto x:s2)
        {
            if(--hash[x-'A'] < 0)
            {
                flag = false;
                break;
            }
        }
        cout << (flag ? "Yes" : "No") << endl;
    }
    return 0;
}

第二题： 组队竞赛

链接：组队竞赛_牛客笔试题_牛客网

牛牛举办了一次编程比赛,参加比赛的有3*n个选手,每个选手都有一个水平值a_i.现在要将这些选手进行组队,一共组成n个队伍,即每个队伍3人.牛牛发现队伍的水平值等于该队伍队员中第二高水平值。 例如: 一个队伍三个队员的水平值分别是3,3,3.那么队伍的水平值是3 一个队伍三个队员的水平值分别是3,2,3.那么队伍的水平值是3 一个队伍三个队员的水平值分别是1,5,2.那么队伍的水平值是2 为了让比赛更有看点,牛牛想安排队伍使所有队伍的水平值总和最大。 如样例所示: 如果牛牛把6个队员划分到两个队伍 如果方案为: team1:{1,2,5}, team2:{5,5,8}, 这时候水平值总和为7. 而如果方案为: team1:{2,5,8}, team2:{1,5,5}, 这时候水平值总和为10. 没有比总和为10更大的方案,所以输出10. 输入描述: 输入的第一行为一个正整数n(1 ≤ n ≤ 10^5) 第二行包括3*n个整数a_i(1 ≤ a_i ≤ 10^9),表示每个参赛选手的水平值. 输出描述: 输出一个整数表示所有队伍的水平值总和最大值. 示例1 输入 2 5 2 8 5 1 5 输出 10

题解： 本题要从 3 倍队伍数量的选手中组队，使队伍水平值总和最大。先读取选手水平值并排序，接着从排序后的数组末尾开始，每隔两个选一个选手，将其水平值累加，累加次数为队伍数量，最后输出总和。

代码：

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

int main() 
{
    long long n,ret = 0;
    cin >> n;
    vector<long long> nums(n*3);
    for(int i = 0;i < n*3;i++) cin >>nums[i];

    sort(nums.begin(),nums.end());
    int pos = n*3-2,count = 0;
    while(count < n)
    {
        ret+=nums[pos];
        pos-=2;
        count++;
    }
    cout << ret << endl;
    return 0;
}

第三题：删除相邻数字的最大分数

链接：删除相邻数字的最大分数_牛客题霸_牛客网

描述 给定一个长度为 n 的仅包含正整数的数组，另外有一些操作，每次操作你可以选择数组中的任意一个元素 ai ai​ ，同时数组中所有等于 ai−1 ai​−1 和 ai+1 ai​+1 的元素会被全部移除，同时你可以得到 ai ai​ 分，直到所有的元素都被选择或者删除。 请你计算最多能得到多少分。 数据范围： 数组长度满足 1≤n≤105 1≤n≤105 ，数组中的元素大小都满足 1≤ai≤104 1≤ai​≤104 输入描述： 第一行输入一个正整数 n 表示数组的长度 第二行输入 n 个数字表示数组的各个元素值。 输出描述： 输出能得到的最大分数。 示例1 输入： 2 1 2 输出： 2 说明： 直接选择元素 2 ，然后 1 被同时移除。 示例2 输入： 3 1 2 3 输出： 4 说明：先选择 3 ，同时 2 被移除，再选择 1 ，即得到 4 分。 示例3 输入： 9 1 2 1 3 2 2 2 2 3 输出： 10 说明： 第一步选择一个 2 ，然后所有 1 和 3 都被移除了，此时数组中剩下的是 [2,2,2,2] ，依次选择他们即可得到 10 分

题解：先统计各数字分数总和，再通过动态规划，对比选与不选某数字时的得分情况，递推求出最大得分

代码：

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

const int N = 1e4 + 10;
int sum[N]; 
int n;
int f[N], g[N];
int main() 
{
    cin >> n;
    int x;
    for(int i = 0; i < n; i++)
    {
        cin >> x;
        sum[x] += x;
    }
    for(int i = 1; i < N; i++)
    {
        f[i] = g[i - 1] + sum[i];
        g[i] = max(f[i - 1], g[i - 1]);
    }
    cout << max(f[N - 1], g[N - 1]) << endl;
    return 0;
}