强化训练：day4

前言

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

1. 简写单词

1.1 题目描述

1.2 解题思路

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

1.3 代码实现

#include 
using namespace std;
#include
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;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

2. dd爱框框

2.1 题目描述

2.2 解题思路

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

2.3 代码实现

#include
using namespace std;
#include 
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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

3. 除2！

3.1 题目描述

3.2 解题思路

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

3.3 代码实现

#include 
using namespace std;
#include 
#include 
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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

总结

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