周赛补题（AcWing、力扣）

AcWing第66场周赛

第一题：4606. 奇偶判断 - AcWing题库

思路：对输入的字符串的最后一个字母进行判断即可。

代码

#include <bits/stdc++.h>
 
using namespace std;
 
int main()
{
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    string s;
    cin >> s;
    reverse(s.begin(), s.end());
    if(s[0] - '0' & 1) cout << 1 << endl;
    else cout << 0 << endl;
    return 0;
}

第二题：4607. 字母补全 - AcWing题库

思路：没看清楚题目，wa了一次。滑动窗口。当窗口大小（每个字母的次数最多为1，遇到？可以直接扩大窗口）大于26说明可以找到符合条件的字符串，将窗口的中的？转化为字母是窗口中的所有的大写的字母都恰出现一次，其余的？可以任意替换为一个大写的字母。

代码

#include <bits/stdc++.h>
 
using namespace std;
 
string s;
int cnt[26], t[26];
 
int main()
{
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> s;
    bool st = 0;
    int b, e;
    for(int i = 0, j = 0; i < s.size(); i ++)
    {
        if(s[i] != '?')
        {
            cnt[s[i] - 'A'] ++;
            while(j < i && cnt[s[i] - 'A'] > 1) cnt[s[j ++] - 'A'] --;
        }
        if(i - j + 1 == 26)
        {
            st = 1;
            b = j, e = i;
            break;
        }
    }
    if(!st) cout << -1 << endl;
    else
    {
        for(int i = b; i <= e; i ++)
            if(s[i] != '?')
                t[s[i] - 'A'] = 1;
        for(int i = b, k = 0; i <= e; i ++)
            if(s[i] == '?')
            {
                while(k < 26 && t[k]) k ++;
                s[i] = (char)(k + 'A');
                k ++;
            }
        for(int i = 0; i < s.size(); i ++)
            if(s[i] == '?')
                s[i] = 'A';
        cout << s << endl;
    }
    return 0;
}

第三题：4608. 整数分组 - AcWing题库

思路：将所有的数用哈希表存储，统计出现一次的数的个数cnt，当一个数出现的次数大于等于3时表示可以分出一个超级数出来res。

为了使A和B中的超级数相同有两种情况：

        1、cnt为偶数，将前cnt/2个只出现一次的数给A，后cnt/2个只出现一次的数给B，其余的数给A或B都可以

        2、cnt为偶数，res>0，将前(cnt+1)/2个只出现一次的数给A，后cnt/2个只出现一次的数给B，可以从出现次数大于等于3的数x中分出一个超级数给B（有一个x给B，其余的x都要给A)，其余的数给A或B都可以。

这两种情况就直接模拟就可以了。

代码

#include <bits/stdc++.h>
 
using namespace std;
 
const int N = 110;
int a[N];
int n;
unordered_map<int, int> mp;
 
int main()
{
    cin >> n;
    for(int i = 0; i < n; i ++)
    {
        cin >> a[i];
        mp[a[i]] ++;
    }
    int cnt = 0, res = 0;
    for(auto [x, y] : mp)
    {
        if(y == 1) cnt ++;
        else if(y > 2) res ++;
    }
    res = min(res, 1);
    if(cnt % 2 == 0) res = 0;
    if(cnt % 2 == 0 || res)
    {
        cout << "YES" << endl;
        string s;
        int ans = 0;
        for(int i = 0; i < n; i ++)
        {
            if(mp[a[i]] == 1)
            {
                ans ++;
                if(ans <= (cnt + 1) / 2) s += 'A';
                else s += 'B';
            }
            else if(mp[a[i]] > 2 && res)
            {
                s += 'B';
                res --;
            }
            else s += 'A';
        }
        cout << s << endl;
    }
    else cout << "NO" << endl;
    return 0;
}

力扣第308场周赛

第一题：2389. 和有限的最长子序列 - 力扣（LeetCode）

思路：求一个小于等于m子序列的最大长度，这个序列一定是都前n个最小的数组成的序列（这个应该很容易想到（OS ：关于证明全搞完了，y总平时将证明的时候也没有好好听，而且好要证明充分性和必要性，有点麻烦））。所以可以先将数组排序求前缀和，对于每个询问找出对于小于等于该数的最大的前缀和的最大长度。

代码

class Solution {
public:
    vector<int> answerQueries(vector<int>& nums, vector<int>& q) {
        sort(nums.begin(), nums.end());
        int n = nums.size();
        vector<int> s(n, 0);
        map<int, int> mp;
        for(int i = 0; i < n; i ++)
        {
            if(!i) s[i] = nums[i];
            else s[i] = s[i - 1] + nums[i];
            mp[s[i]] = i + 1;
        }
        vector<int> ans;
        for(auto i : q)
        {
            auto it = mp.upper_bound(i);
            if(it == mp.begin()) ans.push_back(0);
            else
            {
                it --;
                ans.push_back(it->second);
            }
        }
        return ans;
    }
};

第二题：2390. 从字符串中移除星号 - 力扣（LeetCode）

思路：用栈来模拟。因为这个字符串会将*的最左边的非*的字符删除，所以可以用栈（先进先出）来模拟。遇到了一个*，如果当前栈不是空的话，栈顶元素一定是在*最左边的一个非*字符。

代码

class Solution {
public:
    string removeStars(string s) {
        stack<char> str;
        for(int i = 0; i < s.size(); i ++)
        {
            if(s[i] == '*' && str.size()) str.pop();
            else    str.push(s[i]);
        }
        string ans;
        while(str.size())
        {
            ans += str.top();
            str.pop();
        }
        reverse(ans.begin(), ans.end());
        return ans;
    }
};

第三题：2391. 收集垃圾的最少总时间 - 力扣（LeetCode）

思路：模拟。因为每辆车都是从0开始出发，所以只需要找到每个垃圾的最后一个下标加上它们的前缀和就是每辆汽车的时间，每个垃圾收拾的次数都是一分钟，所以收拾垃圾的时间就是每个垃圾的次数和，最后将汽车的总时间和收拾垃圾的总时间加在一起就是总时间。

代码

class Solution {
public:
    int garbageCollection(vector<string>& g, vector<int>& travel) {
        int ans = 0;
        int n = g.size();
        int a = 0, b = 0, c = 0;
        map<char, int> mp;
        for(int i = 0; i < n; i ++)
        {
            auto t = g[i];
            for(auto j : t)
            {
                mp[j] ++;
                if(j == 'M') a = i;
                else if(j == 'P') b = i;
                else c = i;
            }
        }
        for(int i = 1; i < n - 1; i ++) travel[i] += travel[i - 1];
        if(a != 0) a = travel[a - 1];
        if(b != 0) b = travel[b - 1];
        if(c != 0) c = travel[c - 1];
        // cout << a << " " << b << " " << c << endl;
        ans += a + b + c;
        for(auto [x, y] : mp) ans += y;
        return ans;
    }
};

第四题：2392. 给定条件下构造矩阵 - 力扣（LeetCode）

思路：拓扑排序。因为有一个二维数组规定了关于行和列的先后顺序，可以用拓扑排序来求每行和每列的数字的前后顺序，通过这个先后的的顺序可以确定一个数的位置。拓扑的无法出现所有的就表示无法构造一个矩阵。

代码

const int N = 410, M = 10010;
class Solution {
public:
    int h1[N], e1[M], ne1[M], idx1;
    int h2[N], e2[M], ne2[M], idx2;
    int d1[N], d2[N];
    void add1(int a, int b)
    {
        e1[idx1] = b, ne1[idx1] = h1[a], h1[a] = idx1 ++;
    }
    
    void add2(int a, int b)
    {
        e2[idx2] = b, ne2[idx2] = h2[a], h2[a] = idx2 ++;
    }
    vector<vector<int>> buildMatrix(int k, vector>& r, vector>& c) {
        memset(h1, -1, sizeof h1);
        memset(h2, -1, sizeof h2);
        for(auto i : r)
        {
            int a = i[0], b = i[1];
            add1(a, b);
            d1[b] ++;
        }
        for(auto i : c)
        {
            int a = i[0], b = i[1];
            add2(a, b);
            d2[b] ++;
        }
        vector<int> res1, res2;
        queue<int> q1, q2;
        for(int i = 1; i <= k; i ++)
        {
            if(!d1[i]) q1.push(i);
            if(!d2[i]) q2.push(i);
        }
        while(q1.size())
        {
            auto p = q1.front(); q1.pop();
            res1.push_back(p);
            for(int i = h1[p]; i != -1; i = ne1[i])
            {
                int j = e1[i];
                d1[j] --;
                if(!d1[j]) q1.push(j);
            }
        }
        while(q2.size())
        {
            auto p = q2.front(); q2.pop();
            res2.push_back(p);
            for(int i = h2[p]; i != -1; i = ne2[i])
            {
                int j  = e2[i];
                d2[j] --;
                if(!d2[j]) q2.push(j);
            }
        }
        if(res1.size() != k || res2.size() != k) return {};
        vector<vector<int>> ans(k, vector(k, 0));
        map<int, int> mp1, mp2;
        for(int i = 0; i < k; i ++)
        {
            mp1[res1[i]] = i;
            mp2[res2[i]] = i;
        }
        for(int i = 1; i <= k; i ++)
        {
            int x = mp1[i], y = mp2[i];
            ans[x][y] = i;
        }
        return ans;
    }
};