前言

  今天的题目是：BC149 简写单词、dd爱框框、除2！，分别涉及模拟、滑动窗口、堆（优先级队列）的内容。

1. 简写单词

1.1 题目描述

1.2 解题思路

  一道简单的模拟题，遍历一遍字符串，然后找到空格，再将空格的下一个字符添加到最后结果中即可。

1.3 代码实现

#include <iostream>
using namespace std;
#include<string>
int main() 
{string s;getline(cin, s);string ret;int cur = 0;while(cur < s.size()){if(s[cur] >= 'a' && s[cur] <= 'z') ret += s[cur] - 32;else ret += s[cur];while(cur < s.size() && s[cur] != ' ') cur++;cur++;}cout << ret;return 0;
}

2. dd爱框框

2.1 题目描述

2.2 解题思路

  使用滑动窗口来解决，也就是使用两个指针来维护我们的所需要的区间，当我们维护的区间满足条件时，就记录一下此时的左边界和右边界，然后继续向后遍历。

2.3 代码实现

#include<iostream>
using namespace std;
#include <vector>
typedef long long ll;
int main()
{int n = 0, x = 0; cin >> n >> x;vector<ll> nums(n + 1);for(int i = 1; i <= n; i++){cin >> nums[i];}int left = 0, right = 0,sum = 0, len = 0x3f3f3f3f, l = 0, r = 0;while(right <= n){// 进窗口sum += nums[right];//判断是否符合条件while(sum >= x){// 当区间长度比上一次小时，更新我们的结果if(right - left < len) len = right - left, l = left, r = right;// 出窗口sum -= nums[left++];}right++;}cout << l << " " << r;return 0;
}

3. 除2！

3.1 题目描述

3.2 解题思路

  使用堆一下子就解决了，堆的作用就是每次选出最大的数，然后让我们进行判断。先将所有偶数入堆，然后选出最大的偶数，进行除2，如果除2后的结果还是偶数，继续入堆，直到操作次数变为0。

3.3 代码实现

#include <iostream>
using namespace std;
#include <queue>
#include <vector>
int main()
{long long n, k;cin >> n >> k;vector<int> nums(n);priority_queue<pair<int,int>> q;for(int i = 0; i < n; i++){cin >> nums[i];if(nums[i] % 2 == 0) q.push({nums[i], i});}while(q.size() != 0 && k--){auto [num, i] = q.top();q.pop();nums[i] /= 2;if(nums[i] % 2 == 0) q.push({nums[i],i});}long long ret = 0;for(int i = 0; i < n; i++){ret += nums[i];}cout << ret;return 0;
}

总结

  模拟题没什么好说的，对于滑动窗口，本质就是用双指针来维护一个符合条件的区间，然后不断进窗口和出窗口，一直找到所有符合条件的结果，一般就是用于一段子区间求和，上面的例题就是典型的滑动窗口问题，多画图多看多走读代码就能理解了。而最后一个题就是堆的简单使用，不理解的话可以看看有关堆的相关知识，在这我就贴一个链接，有兴趣的可以看看堆的知识。（二叉树与堆）
  那么第四天的内容就到此结束了，如果大家发现有什么错误的地方，可以私信或者评论区指出喔。我会继续坚持训练的，希望能与大家共同进步！！！那么本期就到此结束，让我们下期再见！！觉得不错可以点个赞以示鼓励！