周赛补题（力扣、acwing）

AcWing第67场周赛

第一题：4609. 火柴棍数字 - AcWing题库

思路：这题的意思是要是用给定的火柴棍使组成的数字最大，所以是火柴棍摆放的数字的个数最多就可以了，至少用两个火柴棍才能摆放一个数字，其次是三根火柴棍可以摆放一个数字，所以可以摆放n/2个一个，如果n为奇数第一位可以变成7。

代码

#include <bits/stdc++.h>
 
using namespace std;
 
int main()
{
    int t; cin >> t;
    while(t --)
    {
        int n;
        cin >> n;
        string s;
        int a = n / 2, b = n & 1;
        if(b)
        {
            s += '7';
            a --;
        }
        for(int i = 0; i < a; i ++)
            s += '1';
        cout << s << endl;
    }
    return 0;
}

第二题：4610. 列表排序 - AcWing题库

思路：原以为是dfs，写了半天发现dfs不可以，模拟试了一下过了。可以枚举任意两列（这两列可以是同一列，然后是同一列就是不交换两列）将所枚举的两列进行交换，然后对每行进行枚举如果不合法（可以交换一次），每行最多可以交换一次，如果最后是合法的就可以达到目标。

关于每行是否合法：因为每行是一行全排列，所以第i行的每个数都满足a[i][j] == j

代码

#include <bits/stdc++.h>
 
using namespace std;
 
const int N = 25;
 
int a[N][N];
int n, m;
 
bool check()
{
    //对每行枚举（最多交换一次后）是否合法
    for(int i = 1; i <= n; i ++)
    {
        //用cnt来表示不合法的数字
        int cnt = 0;
        for(int j = 1; j <= m; j ++)
            if(a[i][j] != j)
                cnt ++;
        //交换一次最多可以使两个不合法的数组合法
        if(cnt > 2) return false;       
    }
    return true;
}
 
int main()
{
    cin >> n >> m;
    //为了比较好判断每一行是否是合法的下标要从1开始
    for(int i = 1; i <= n; i ++)
        for(int j = 1; j <= m; j ++)
            cin >> a[i][j];
    bool st = 0;
    //枚举两列进行交换
    for(int i = 1; i <= m; i ++)
    {
        if(st) break;
        for(int j = i; j <= m; j ++)
        {
            //交换第i列和第j列
            for(int k = 1; k <= n; k ++) swap(a[k][i], a[k][j]);
            if(check())
            {
                st = 1;
                break;
            }
            //使数组恢复
            for(int k = 1; k <= n; k ++) swap(a[k][i], a[k][j]);
        }
    }
    
    if(st) cout << "YES" << endl;
    else cout << "NO" << endl;
    return 0;
}

力扣第86场周赛

第一题：6171. 和相等的子数组 - 力扣（LeetCode）

思路：可以直接暴力枚举。

代码

class Solution {
public:
    bool findSubarrays(vector<int>& nums) {
        int n = nums.size();
        for(int i = 0; i < n; i ++)
            for(int j = i + 1; j < n; j ++)
                if(j + 1 < n)
                    if(nums[i] + nums[i + 1] == nums[j] + nums[j + 1])
                        return true;
        return false;
    }
};

第二题：6172. 严格回文的数字 - 力扣（LeetCode）

思路：这题直接模拟，将n转化为x进制（x为2~n-2），对每个进制判断是否为回文串。

代码

class Solution {
public:
    bool is(int x, int n)
    {
        vector<int> ans;
        while(n)
        {
            ans.push_back(n % x);
            n /= x;
        }
        //因为是要判断是否为回文串，这里可以不用翻转数组
        int m = ans.size();
        for(int i = 0; i < m / 2; i ++)
            if(ans[i] != ans[m - i - 1])
                return false;
        return true;
    }
    bool isStrictlyPalindromic(int n) {
        for(int i = 2; i < n - 1; i ++)
            if(!is(i, n))
                return false;
        return true;
    }
};

第三题：2397. 被列覆盖的最多行数 - 力扣（LeetCode）

思路：状态压缩。用二进制数（1的个数为col）来表示每一列覆盖的情况。对每个状态进行枚举。

代码

class Solution {
public:
    int maximumRows(vector<vector<int>>& mat, int cols) {
        int ans = 0;
        int n = mat.size(), m = mat[0].size();
        vector<int> res;
        // 将状态存在数组中
        for(int i = 0; i < (1 << m); i ++)
        {
            int cnt = 0;
            for(int j = 0; j < m; j ++)
                if(i >> j & 1)
                    cnt ++;
            if(cnt == cols) res.push_back(i);
        }
        set<int> s;
        for(auto i : res)
        {
            // 存储该状态没有被覆盖存在1的行数
            s.clear();
            // 在该状态下对每一列进行枚举
            for(int j = 0; j < m; j ++)
                // 如果该列没有被覆盖
                if((i >> j & 1) == 0)
                {
                    // 将该列有1的行数存起来
                    for(int k = 0; k < n; k ++)
                        if(mat[k][j])
                            s.insert(k);
                }
            // cnt为没有被覆盖的行数
            int cnt = s.size();
            ans = max(ans, n - cnt);
        }
        return ans;
    }
};

第四题：6143. 预算内的最多机器人数目 - 力扣（LeetCode）

思路：滑动窗口。这题刚开始没有看到连续两个字，排序后写发现样例都是错的，所以看清楚题目再去写题是很重要的。这题的意思是求一段连续的（满足题目的）子数组的最大长度。

用multiset来存储窗口的最大充电时间，注意这里用set是错的，因为可能有相同的最大值，multiset可以存储相同的数，sum为子数组的前缀和。

代码（被hack了，multiset删除数据的erase(val)，会将所有值为val的都删除）

class Solution {
public:
    typedef long long LL;
    int maximumRobots(vector<int>& C, vector<int>& R, long long b) {
        int n = C.size();
        vector<LL> sum(n + 1, 0);
        // 求前缀和
        for(int i = 1; i <= n; i ++)    sum[i] = sum[i - 1] + R[i - 1];
        int ans = 0;
        LL t = 0;
        multiset<int> s;
        for(int i = 0, j = 0; i < n; i ++)
        {
            // 这里有一个小技巧，将充电时间的负数存储起来，那么最大值就是第一个元素的负数
            s.insert(-C[i]);
            // cout << (LL)sum[i + 1] - sum[j] - (*s.begin()) << endl;
            while(j <= i && (LL)(sum[i + 1] - sum[j]) * (i - j + 1) - (*s.begin()) > b)
            {
                s.erase(-C[j ++]);
            }
            ans = max(ans, i - j + 1);
        }
        
        
        return ans;
    }
};

代码（将multiset改为map）

class Solution {
public:
    typedef long long LL;
    int maximumRobots(vector<int>& C, vector<int>& R, long long b) {
        int n = C.size();
        vector<LL> sum(n + 1, 0);
        // 求前缀和
        for(int i = 1; i <= n; i ++)    sum[i] = sum[i - 1] + R[i - 1];
        int ans = 0;
        // LL t = 0;
        map<int, int> mp;
        // multiset<int> s;
        for(int i = 0, j = 0; i < n; i ++)
        {
            // 这里有一个小技巧，将充电时间的负数存储起来，那么最大值就是第一个元素的负数
            mp[-C[i]] ++;
            // cout << (LL)sum[i + 1] - sum[j] - (*s.begin()) << endl;
            while(j <= i && (LL)(sum[i + 1] - sum[j]) * (i - j + 1) - (mp.begin()->first) > b)
            {
                mp[-C[j]] --;
                if(mp[-C[j]] == 0) mp.erase(-C[j]);
                j ++;
            }
            // cout << endl;
            ans = max(ans, i - j + 1);
        }
        
        
        return ans;
    }
};

力扣第309场周赛

这次的周赛是真的难，这个第二题真的是把人搞麻了。

第一题：2399. 检查相同字母间的距离 - 力扣（LeetCode）

思路：用数组来存储两个字母的距离。用哈希表来存储每个字母第一次出现的下标，当字母第二次出现的时候就用当前下标减去第一次出现的下标再减去1。对出现的每个字母枚举每个字母的距离是否和给定的距离是一样的。

代码

class Solution {
public:
    bool checkDistances(string s, vector<int>& distance) {
        unordered_map<char, int> mp;
        int cnt[26] = {0};
        for(int i = 0; i < s.size(); i ++)
        {
            if(mp.count(s[i])) cnt[s[i] - 'a'] = i - mp[s[i]] - 1;
            else mp[s[i]] = i;
        }
        for(int i = 0; i < 26; i ++)
            if(mp.count(i + 'a') && cnt[i] != distance[i])
                return false;
        return true;
    }
};

第二题：2400. 恰好移动 k 步到达某一位置的方法数目 - 力扣（LeetCode）

思路：为了使起点到终点所以需要朝一个方向净走t = abs(startPos - endPos)，剩余步数为k - t，

剩余步数一定要是偶数并且大于等于0才能走到终点，然后分布朝左右两个方向各走(k - t)/2步，所以k步中有(k - t)/2朝一个方向走，其余的步数是朝另一个方向走，所以相当于是从k的步数中选择(k -t)/2朝一个方向走，既组合数C(k, (k - t)/2).

代码

const int mod  = 1e9 + 7;
class Solution {
public:
    int f[1010][1010];
    int numberOfWays(int startPos, int endPos, int k) {
        int t = abs(startPos - endPos);
        t = k - t;
        if(t < 0 || t & 1)  return 0;
        t /= 2;
        // 求组合数
        for(int i = 0; i < 1010; i ++)
            for(int j = 0; j <= i; j ++)
            {
                if(!j) f[i][j] = 1;
                else f[i][j] = (f[i - 1][j] + f[i - 1][j - 1]) % mod;
            }
        return f[k][t];
    }
};

第三题：2401. 最长优雅子数组 - 力扣（LeetCode）

思路：滑动窗口。题目的意思是求一个满足条件（数组内部的任意两个数按位与都是0）的子数组的最大长度。数组内部的任意两个数按位与都是0可以相当于子数组中每位的个数1的总个数都是喜小于等于1的。

代码

class Solution {
public:
    int cnt[32];
    bool check()
    {
        for(int i = 0; i < 32; i ++)
            if(cnt[i] > 1)
                return false;
        return true;
    }
    
    void add(int x)
    {
        for(int i = 0; i < 32; i ++)
            cnt[i] += (x >> i & 1);
    }
    
    void sub(int x)
    {
        for(int i = 0; i < 32; i ++)
            cnt[i] -= (x >> i & 1);
    }
    
    int longestNiceSubarray(vector<int>& nums) {
        int ans = 0, n = nums.size();  
        for(int i = 0, j = 0; i < n; i ++)
        {
            add(nums[i]);
            while(j <= i && !check()) sub(nums[j ++]);
            ans = max(ans, i - j + 1);
        }
        return ans;
    }
};