C++笔试强训day14

目录

1.乒乓球框

2.组队竞赛

3.删除相邻数字的最⼤分数

1.乒乓球框

链接

哈希表直接秒了：

#include <iostream>
#include <string>
using namespace std;
int main() {
    string s1, s2;
    while (cin >> s1 >> s2) { // 未知组数的输⼊
        int hash[26] = { 0 };
        for (auto ch : s1) hash[ch - 'A']++;
        bool ret = true;
        for (auto ch : s2) {
            if (--hash[ch - 'A'] < 0) {
                ret = false;
                break;
            }
        }
        cout << (ret ? "Yes" : "No") << endl;
    }
    return 0;
}

唯一要注意的就是该题是多组输入。

2.组队竞赛

链接

据题意描述就是每次都取中间的值为水平值，所以我们可以每次都取第二大的值为水平值。

（注意，需要先排序，因为这样才能得到第二大的值）

所以直接遍历求和：

#include <iostream>
#include <algorithm>
using namespace std;
typedef long long LL;
const int N = 1e5 + 10;
int n;
LL arr[N * 3];
int main()
{
	cin >> n;
	for (int i = 0; i < 3 * n; i++) cin >> arr[i];
	sort(arr, arr + 3 * n);
	int pos = 3 * n - 2, count = 1;
	LL ret = 0;
	while (count++ <= n)
	{
		ret += arr[pos];
		pos -= 2;
	}
	cout << ret << endl;
	return 0;
}

3.删除相邻数字的最⼤分数

链接

单看看不出有什么好用的解法，但是如果将同数的和求出来，就可以得到一个：取第i个值，则不能取i - 1和 i + 1的值的一个线性dp问题。

#include <iostream>
using namespace std;

const int N = 1e4 + 10;
int sum[N];
int f[N];
int g[N];

int main() {
    int n;
    cin >> n;

    int x;
    for(int i = 0; i < n; ++i)
    {
        cin >> x;
        sum[x] += x;
    }

    for(int i = 0; i < N; ++i)
    {
        f[i] = sum[i] + g[i - 1];
        g[i] = max(f[i - 1], g[i - 1]);
    }
    cout << max(f[N - 1], g[N - 1]) << endl;

    return 0;
}