周赛补题（AcWing，力扣）

AcWing第60场周赛

第一题：4494. 吃饭 - AcWing题库

思路：判断小朋友的个数是否同时不大于饭的数量和饮料的数量

代码

#include 

using namespace std;

int main()
{
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int n, m, p;
    cin >> n >> m >> p;
    if(n <= m && n <= p)    cout << "Yes" << endl;
    else cout << "No" << endl;
    return 0;
}

第二题：4495. 数组操作 - AcWing题库

思路：对数组的元素从小到大遍历（遍历k次，数组元素遍历完就输出0），有一个数t来记录每次找到的最小非0元素，每次输出在数组中大于t的最小数减去t并将t的值更新为这个值，这个相当于每次找到t并将数组中的所有数减去t。因为我想到从小到大遍历就想到了优先队列，所以我当时是用优先队列来写的，其实数组也是可以写的，要先排个序

代码（优先队列）

#include 

using namespace std;

int n, k;

int main()
{
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> n >> k;
    priority_queue, greater> q;
    while(n --) 
    {
        int x;
        cin >> x;
        q.push(x);
    }
    
    
    int sum = 0;
    bool st = 0;
    int t = 0;
    while(k --)
    {
        sum = q.top();
        while(q.size() && q.top() == sum)   q.pop();
        if(st)  cout << 0 << endl;
        else    cout << sum - t << endl;
        t = sum;
        if(!q.size())   st = 1;
    }
    return 0;
}

代码（用数组排序）

#include 

using namespace std;

const int N = 1e5 + 10;
int a[N];
int n, m;

int main()
{
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> n >> m;
    for(int i = 1; i <= n; i ++)    cin >> a[i];
    sort(a + 1, a + 1 + n);
    int t = 0, i = 1;
    while(m --)
    {
        if(i > n)   cout << 0 << endl;
        else
        {
            while(i <= n && a[i] == t)  i ++;
            if(i > n)   cout << 0 << endl;
            else
            {
                cout << a[i] - t << endl;
                t = a[i];
            }
        }
    }
    return 0;
}

第三题：4496. 吃水果 - AcWing题库

思路：题目等价于将n块地分为k + 1份，给每块第都涂上一个颜色，使每两块地相邻的颜色都不一样的染色方案数。这个分为两步，第一步是求将n块地分为k+1份的方案数；第二步是有k+1块地，求是每两块相邻地的颜色不同的方案数。

第一步：将n块地分为k + 1份，可以在中间加上k块挡板，o表示地，|表示挡板

o o o | o o o | o o o o | o o o o o

这个的方案数为组合数C(n - 1, k);

第二步：将k+1块地相邻的两块地的染色不能相同的方案数，可以从左到右进行选择

o o o ... o o

第一块的选择为m

第二块的选择为m - 1  因为左边已经选择了一种颜色，而且这块的颜色不能与左边的相同

第三块的选择为m - 1

....

第k + 1块的选择为m - 1

这个的方案数为m*(m-1)^k

所以总方案数为C(n - 1, k)*m*(m-1)^k，对答案取模（每次计算一次就取一次模，防止爆int或者long long）

求组合数的这个当时忘了怎么写的，所以是直接从基础课中copy过来的.

f[i][j]的含义是从前i个数中选择j个数，f[i][j] = f[i - 1][j - 1] + f[i - 1][j].

可以将f[i][j]变成上面的那个式子，是因为从前i个数选择j个，第i个数分为两种情况选或者不选。

选第i个数，那么从前i个数中选择j个数就变成了从前i-1个数中选择j-1个数      既f[i - 1][j - 1]

不选第i个数，那么从前i个数中选择j个数就变成了从前i-1个数中选择j个数      既f[i - 1][j]

代码

#include 

using namespace std;

const int N = 2010, mod = 998244353;

int n, m, k;
int a[N][N];



int main()
{
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> n >> m >> k;
    for(int i = 0; i < N; i ++)
    {
        for(int j = 0; j <= i; j ++)
        {
            if(!j) a[i][j] = 1;
            else a[i][j] = (long long)(a[i - 1][j] + a[i - 1][j - 1]) % mod;
        }
    }
    int sum = m;
    for(int i = 0; i < k; i ++)
        sum = (long long)sum * (m - 1) % mod;
    sum = (long long)sum * a[n - 1][k] % mod;
    cout << sum << endl;
    
    return 0;
}

力扣第302场周赛

第一题：2341. 数组能形成多少数对 - 力扣（LeetCode）

思路：模拟。

代码

class Solution {
public:
    vector numberOfPairs(vector& nums) {
        map mp;
        for(auto i : nums)  mp[i] ++;
        int a = 0, cnt = 0;
        for(auto [x, y] : mp)
        {
            if(y & 1)   cnt ++, a += y / 2;
            else a += y / 2;
        }
        return {a, cnt};
    }
};

第二题：2342. 数位和相等数对的最大和 - 力扣（LeetCode）

思路：用一个数组来存储数位和的相等的数，最后枚举最大的两个数的和。

代码

class Solution {
public:
    vector a[100];
    int maximumSum(vector& nums) {
        sort(nums.begin(), nums.end());
        for(auto i : nums)
        {
            int t = i, sum = 0;
            while(t)
            {
                sum += t % 10;
                t /= 10;
            }
            a[sum].push_back(i);
        }
        int ans = -1;
        for(int i = 1; i < 100; i ++)
        {
            int n = a[i].size();
            if(n < 2)   continue;
            int s = 0;
            int l = a[i].back(); a[i].pop_back();
            ans = max(ans, l + a[i].back());
        }
        return ans;
    }
};

第三题：2343. 裁剪数字后查询第 K 小的数字 - 力扣（LeetCode）

思路：每个字符串都用一个数组来存储该字符串的所有后缀字符串，根据对应的数组的查询来得到下标。

代码

class Solution {
public:
    string a[110][110];
    vector smallestTrimmedNumbers(vector& nums, vector>& q) {
        int n = nums.size(), m = nums[0].size();
        for(int i = 0; i < n; i ++)
        {
            string t = nums[i];
            for(int j = 1; j <= m; j ++)
            {
                a[i][j] = t.substr(m - j);
            }
        }
        vector ans;
        for(auto i : q)
        {
            int l = i[0], r = i[1];
            vector res;
            r = min(r, m);
            for(int j = 0; j < n; j ++)
            {
                res.push_back(a[j][r]);
            }
            sort(res.begin(), res.end());
            string temp = res[l - 1];
            int jj = 0;
            while(l - 1 >= 0 && temp == res[l - 1]) l --, jj ++;
            int v = 0;
            for(int j = 0; j < n; j ++)
            {
                if(a[j][r] == temp)
                {
                    v ++;
                    if(v == jj)
                    {
                        ans.push_back(j);
                        break;
                    }
                }
            }
        }
        return ans;
    }
};