AcWing周赛 69 场 && LeetCode单周赛 311 场 && LeetCode 双周赛87场

一、AcWing周赛第69场

1、4615.相遇问题

（1）原题链接：4615. 相遇问题 – AcWing题库

（2）解题思路：

        1、题目的意思可以转化为求解（y – x）/ (a + b) 的值为多少；因为x，y之间的距离每秒的减少量就是a+b。

        2、先判断是否存在余数，若存在则输出 -1； 反之，则输出（y – x）/ (a + b) 的值；

（3）参考代码：

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

typedef long long ll;

int main()
{
    int t;
    cin >> t;
    
    while(t -- ) {
        ll x, y, a, b;
        cin >> x >> y >> a >> b;
        
        ll res = 0;
        
        ll dis = y - x;
        ll total = a + b;
        
        if(dis % total) cout << -1 << endl;
        else cout << (dis / total) << endl;
    }
    return 0;
}

2、4616.击中战舰

（1）原题链接：4616. 击中战舰 – AcWing题库

（2）解题思路：

        1、每遍历连续 b 个格子就保存一个下标到 res 中，最终 res 中会有 a 个战舰；

        2、我们要击中至少一个，假设前res.size()-a发都没中，那第res.size()-a+1发肯定就会打中一发，所以答案就是res.size()-a+1。

（3）参考代码：

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 2e5 + 10;

int n, a, b, k;
string s;

int main()
{
    cin >> n >> a >> b >> k >> s;
    
    int cnt = 0;
    vector<int> res;
    
    for(int i = 0; i < n; i ++) {
        if(s[i] == '0') {
            cnt ++;
            if(cnt == b) {
                res.push_back(i + 1);
                cnt = 0;
            }
        }
        else cnt = 0;
    }
    
    cout << res.size() - a + 1 << endl;
    for(int i = 0; i < res.size() - a + 1; i ++) cout << res[i] << ' ';
    
    return 0;
}

二、LeetCode 单周赛 311

1、2413.最小偶倍数

（1）原题链接：力扣https://leetcode.cn/problems/smallest-even-multiple/

（2）解题思路：

        如果n为奇数，那么 2n 就是最小公倍数，反之，最小公倍数就是 n。

（3）代码：

class Solution {
public:
    int smallestEvenMultiple(int n) {
        return n & 1 ? 2*n : n;
    }
};

2、2414.最长的字母序连续子字符串的长度

（1）原题链接：力扣https://leetcode.cn/problems/length-of-the-longest-alphabetical-continuous-substring/

（2）解题思路：

        直接暴力遍历即可。遇到字符串序列不满足要求，就从该字符开始重新开始遍历。

（3）代码：

class Solution {
public:
    int longestContinuousSubstring(string s) {
        int res = 1;
        int n = s.size();
        int tmp = 1;

        for(int i = 1; i < n; i ++ ) {
            if(s[i] - s[i - 1] == 1) tmp ++;
            else tmp = 1;

            res = max(res, tmp);
        }

        return res;
    }
};

三、LeetCode双周赛 87

1、2409.统计共同度过的日子数

（1）原题链接：力扣https://leetcode.cn/problems/count-days-spent-together/submissions/

（2）解题思路：

        1、先将字符串日期转换为一年中的某一天;

        2、再求两个区间的交集。

（3）代码：

class Solution {
public:
    int countDaysTogether(string arriveAlice, string leaveAlice, string arriveBob, string leaveBob) {
        int day1 = calc(arriveAlice);
        int day2 = calc(leaveAlice);
        int day3 = calc(arriveBob);
        int day4 = calc(leaveBob);

        return max(min(day2, day4) - max(day1, day3) + 1, 0);
    }

    int days[12] = {31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
    
    int calc(string s) {
        int m = (s[0] - '0') * 10 + s[1] - '0';
        int ans = (s[3] - '0') * 10 + s[4] - '0';
        for (int i = 1; i < m; i++) { 
            ans += days[i - 1];
        }

        return ans;
    }
};

2、2410.运动员和训练师的最大匹配数

（1）原题链接：力扣https://leetcode.cn/problems/maximum-matching-of-players-with-trainers/

（2）解题思路：

        1、先对运动员和训练师进行排序。

        2、然后用双指针分别对两个序列进行一一匹配并记录最大值。

（3）代码：

class Solution {
public:
    int matchPlayersAndTrainers(vector<int>& players, vector<int>& trainers) {
        sort(players.begin(), players.end());
        sort(trainers.begin(), trainers.end());
        
        int i = 0;
        int j = 0;
        int ans = 0;
        while (i < players.size() && j < trainers.size()) {
            if (players[i] <= trainers[j]) { 
                i ++;
                ans ++;
            }
            j ++;  
        }
        return ans;
    }
};