阅读量:4
C++日常刷题积累
今日刷题汇总 - day014
1、乒乓球筐
1.1、题目
1.2、思路
读完题知道，需要判定A、B两盒乒乓球中，A是否包含了B中所有类型的乒乓球，其中类型以大写字母表示。如果B盒中所有球的类型在A中都有，并且每种球的数量都不大于A，则输出“Yes”；否则输出“No”即可。其实这道题本质就是两个字符串，A串包括了B串中所有字符，那么想到可以利用hash表的思路解决，因为还得考虑字符的数量问题，满足B中g该球的数量不大于A中该球的数量。然后思路步骤就出来了：
(1)、利用哈希映射，统计A字符串中字符的频次；
(2)、再遍历利用哈希，减去B字符串出现的字符；
(3)、最后再次利用哈希查询数目是否满足题目要求，即查看哈希表中B中对应字符下标的数量是否小于0，小于说明，A中对应B的字符数量不足或者不存在B的字符。否则，输出“yes”.
1.3、程序实现
首先按照题目要求，完成多组输入，定义所需的int型hash表，方便统计数量，根据思路完成三个for循环遍历即可。值得注意的是这里可以使用标志位，区分输出结果。
#include <iostream> #include <string> using namespace std; int main() { string A, B; while (cin >> A >> B) { int hash[26] = { 0 }; for (int i = 0; i < A.size(); i++) { hash[A[i] - 'A']++; } int flag = 1; for (int i = 0; i < B.size(); i++) { hash[B[i] - 'A']--; } for (int i = 0; i < B.size(); i++) { if (hash[B[i] - 'A'] < 0) { flag = 0; break; } } cout << (flag ? "Yes" : "No") << endl; } return 0; } 由于后两个循环都是对B进行判断操作，所以可以结合写在一起。
#include <iostream> #include <string> using namespace std; int main() { string A, B; while (cin >> A >> B) { int hash[26] = { 0 }; for (int i = 0; i < A.size(); i++) { hash[A[i] - 'A']++; } int flag = 1; for (int i = 0; i < B.size(); i++) { if (--hash[B[i] - 'A'] < 0) { flag = 0; break; } } cout << (flag ? "Yes" : "No") << endl; } return 0; } 其次，也可以用范围for执行遍历的逻辑。
#include <iostream> #include <string> using namespace std; int main() { string A, B; while (cin >> A >> B) { int hash[26] = { 0 }; for (auto ch1 : A) { hash[ch1 - 'A']++; } int flag = 1; for (auto ch2 : B) { if (--hash[ch2 - 'A'] < 0) { flag = 0; break; } } cout << (flag ? "Yes" : "No") << endl; } return 0; } 
2、组队竞赛
2.1、题目
2.2、思路
读完题，知道让实现所有比赛组合的水平值最大，其中，每个队伍的水平值有该队伍第二高的选手水平值决定。那么，思路想到贪心法，尽可能让每个队伍都分到的第二高水平值的选手水平值高且接近，那么我们可以将每个选手的水平值进行sort排序，如5，2，8，5，1，5 排序后得到，1，2，5，5，5，8，此时组队要水平值和最大，就把最大值放一组的最后，次大值作为该组第二个位置，再次大值作为第二组最大值，再将下一个值作为第二组的第二个位置，这样组成才是最大水平的和，所以最后我们就只需要拿去每一组第二个位置的值即可。为了直观的观察，画个图理解推导过程：
那么接下来，就是程序实现。
2.3、程序实现
首先。按照题目要求写好输入部分，接着就是排序数组，目的是方遍索引每组次高位的下标位置，然后就定义index每组次高位的下标，然后定义retmaxsum 最大水平值，然后将每组的次高位累计加即可。主要是能想到第二位之间的下标关系就很好处理了。
#include <iostream> #include <algorithm> using namespace std; const int N = 1e5 + 10; long long arr[N*3]; int main() { int n; cin >> n; for(int i = 0;i < n*3;i++) cin >> arr[i]; sort(arr,arr+ 3*n); int index = 3*n - 2; long long retmaxsum = 0; while(n--) { retmaxsum += arr[index]; index -= 2; } cout << retmax << endl; return 0; } 
3、删除相邻数字的最大分数
3.1、题目
3.2、思路
读完题，知道让在一组数组中选择任意一个元素ai，获取它的数值作为分数，同时然后去掉数组中ai-1和ai+1的元素，最终知道所有元素都被去除或者获取，要求得到最后的分数最大。那么，根据示例和题目规则分析，为了方便理解画个图：
那么接下来，就是程序实现。
3.3、程序实现 – dp+hash
首先，按照题目需要写好输入，再根据思路分析，只要分为以下几个步骤即可：
(1)、预处理数组元素，转成hash表下标索引统计每个元素的分数值；
(2)、遍历统计好对应元素分数的哈希数组，执行状态转移方程；
(3)、输出f[i]和g[i]这两种情况的最大值即可
值得注意的是，这里转换成hash的数组执行逻辑，所以遍历时遍历hash数组N的范围
#include <iostream> using namespace std; const int N = 1e4 + 10; int hashcount[N] = { 0 }; int f[N]; int g[N]; int main() { int n; cin >> n; int a = 0; for(int i = 0;i < n;i++) { cin >> a; hashcount[a] += a;//统计a元素的分值和 } //遍历哈希表 f[0] = g[0] = 0; for(int i = 1;i < N;i++) { f[i] = hashcount[i] + g[i-1]; g[i] = max(f[i-1],g[i-1]); } //输出这两种情况的最大值即可 cout << max(f[N-1],g[N-1]) << endl; return 0; } 4、题目链接
🌟乒乓球筐
🌟组队竞赛
🌟删除相邻数字的最大分数
