乒乓球筐（哈希）

題目鏈接

題解

1. 兩個哈希表
先統計第一個字符串中的字符個數，再統計第二個字符串中的字符個數，如果第一個字符串中的字符個數大于等于第二個字符串中的字符個數，返回true，否則返回false
2. 用一個哈希表
先統計第一個字符串中的字符個數，然后再減去第二個字符串中的字符個數，如果hash表中某個字符的個數小于0就說明該字符不在第一字符串中，而只在第二個字符串中，返回false，否則返回true

代碼

#include <iostream>
using namespace std;int main()
{string s,t;while(cin >> s >> t)// 未知組數的輸入{int hash[26] = {0};int n = t.size();int flag = 1;for(auto ch : s){hash[ch - 'A']++;}for(int i = 0;i < n;i++){hash[t[i] - 'A']--;if(hash[t[i] - 'A'] < 0) {flag = 0;cout << "No" << '\n';break;} }if(flag)cout << "Yes" << '\n';}return 0;
}

組隊競賽

題目鏈接

題解

1. 排序 + 貪心
2. 總和最大 -> 每個小組的分數最大 -> 那么第二個人的分數盡可能大
3. 那就讓第一個人最小，第三個人最大，第二個人次大

代碼

#include <iostream>
#include<algorithm>
#include<vector>
using namespace std;int main()
{int n; cin >> n;vector<int> ret(3*n);for(int i = 0;i < 3*n;i++) cin >> ret[i];sort(ret.begin(),ret.end());long long sum = 0;int count = n;for(int i = 3*n-2;i >= 0;i-=2){if(count == 0) break;sum += ret[i];count--;}cout << sum << '\n';return 0;
}

刪除相鄰數字的最大分數（線性dp）

題目鏈接

題解

1. 線性dp，可以轉換為打家劫舍問題
2. 讓hash表的下標為數組中的值，hash表中的數據對應所有相同的下標的數之和
3. 細節問題：可以讓dp數組的長度為1e4 + 10，可以不用判斷hash表中的最大的數為數組的長度，dp數組第0個值都初始化為0，因為原數組中沒有0的值，返回選或者不選中dp數組的最大值，對應N-1下表中兩個數組中的最大值
4. 為什么可以轉換為打家劫舍問題？
因為數組中出現了相鄰的數選或者不選，這個數選了下一個數就不能選

代碼

#include <iostream>
#include<vector>
using namespace std;const int N = 1e4 + 10;
const int M = 1e5 + 10;
int ret[M];int main()
{int hash[N] = { 0 };int n = 0;cin >> n;for (int i = 0; i < n; i++) cin >> ret[i];for (int i = 0; i < n; i++){hash[ret[i]] += ret[i];}vector<int> f(N);// 選auto g = f;// 不選for (int i = 1; i < N; i++){f[i] = g[i - 1] + hash[i];g[i] = max(g[i - 1], f[i - 1]);}cout << max(f[N - 1], g[N - 1]) << '\n';return 0;
}