[数据结构与算法]力扣299场周赛+AcWing57场周赛

AcWing57场周赛

第一题：4485. 比大小 - AcWing题库

思路：直接求和然后比较

代码

#include <bits/stdc++.h>

using namespace std;

int n;

int main()
{
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int a = 0, b = 0;
    cin >> n;
    for(int i = 0; i < n; i ++)
    {
        int x;
        cin >> x;
        a += x;
    }
    for(int i = 0; i < n; i ++)
    {
        int x;
        cin >> x;
        b += x;
    }
    if(a >= b)  cout << "Yes" << endl;
    else    cout << "No" << endl;
    return 0;
}

第二题：4486. 数字操作 - AcWing题库?

思路：分解质因数。? ? ? ? ?x = a1^p1 * a2^p2 * ... * an^pn? (a1 a2 ... an之间互质)? 存在一个数n使得y=x*n=a1^(m^2) * a2^(m^2) * ... * an^(m^2)? m^2>=pi? i = 1, 2, ... , n? ? ? 对y进行m次开方可以得到符合题目的最小值n=a1 * a2 * .. * an，如果m^2==p1==p2==p3==...==pn? ? 则只需进行m次操作，否则要进行m+1次操作

代码

#include <bits/stdc++.h>

using namespace std;

const int N = 1e6 + 10;
typedef pair<int, int> PII;
PII prime[N];
int n, cnt = 0;

void get_prime(int x)
{
    for(int i = 2; i * i <= x; i ++)
    {
        if(x % i == 0)
        {
            int res = 0;
            while(x % i == 0)
            {
                res ++;
                x /= i;
            }
            prime[cnt ++] = {i, res};
        }
    }
    if(x > 1)   prime[cnt ++] = {x, 1};
}

int main()
{
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> n;
    get_prime(n);
    int s = 1, sum = 0;
    int ans = 0;
    bool st = 0;
    for(int i = 0; i < cnt; i ++)
    {
        s *= prime[i].first;
        if(prime[i].second != ans && ans)   st = 1;
        ans = max(ans, prime[i].second);
    }
    while(ans > 1)
    {
        if(ans & 1) ans ++, st = 1;
        ans /= 2;
        sum ++;
    }
    //cout << st << endl;
    if(st && sum)   sum ++;
    cout << s << " " << sum << endl;
    return 0;
}

力扣299场周赛

第一题：2319. 判断矩阵是否是一个 X 矩阵 - 力扣（LeetCode）

思路：模拟

代码

class Solution {
public:
    bool checkXMatrix(vector<vector<int>>& grid) {
        int n = grid.size();
        for(int i = 0; i < n; i ++)
        {
            for(int j = 0; j < n; j ++)
            {
                if(i == j || i + j == n - 1)
                {
                    //cout << grid[i][j] << " ";
                    if(grid[i][j] == 0) return false;
                }
                else
                {
                    if(grid[i][j] != 0)  return false;
                }
            }
        }
        return true;
    }
};

第二题：2320. 统计放置房子的方式数 - 力扣（LeetCode）

思路：用一个二维数组f[n][2]记录一边的状态，以为两边是一样的所以只用记录一边就可以，最后将两边的情况相乘就可以了。f[i][0] 表示第i个位置没有放置房间，f[i][1]表示第i个房间放置了房间。

f[i][0] = f[i - 1][0] + f[i - 1][1]? f[i][1] = f[i - 1][0]

代码

class Solution {
public:
    int countHousePlacements(int n) {
        vector<vector<int>> f(n + 1, vector<int>(2));
        f[0][0] = 1;
        int mod = 1e9 + 7;
        for(int i = 1; i <= n; i ++)
        {
            f[i][0] = (f[i - 1][1] + f[i - 1][0]) % mod;
            f[i][1] = f[i - 1][0];
        }
        int ans = (f[n][0] + f[n][1]) % mod;
        ans = (long long)ans * ans % mod;
        return ans;
    }
};

第三题：2321. 拼接数组的最大分数 - 力扣（LeetCode）?

思路：题目意思是通过交换两个数组的一段连续的数得到新的两个数组，返回新的两个数组的和的最大值。分别求交换a和b的一段得到的a数组和最大值和b数组和最大值。这个只需要用函数来求解就可以了。sum为a数组的和，c数组存放b[i] - a[i]，交换后a的数的和的最大值为sum + c[l] + c[l + 1] + .. + c[r]，所以现在只需要求最大的c[l] + c[l + 1] + .. + c[r]，相当于求最大连续子数组和。这个可以用递推：f = max(f, 0) + c[i].

代码

class Solution {
public:
    int work(vector<int>& a, vector<int>& b)
    {
        int sum = 0;
        for(auto i : a) sum += i;
        int ans = 0, res = 0;
        for(int i = 0; i < a.size(); i ++)
        {
            res = max(res, 0) + b[i] - a[i];
            ans = max(ans, res);
        }
        return sum + ans;
    }
    int maximumsSplicedArray(vector<int>& nums1, vector<int>& nums2) {
        return max(work(nums1, nums2), work(nums2, nums1));
    }
};

?