【题解】AcWing - 第60场周赛

总地址：周赛60 - AcWing

前言

题目AC不是终点，做完后看看大佬们的解法，受益很大。unique去重就很好用。

第一题

题目： 4494. 吃饭 - AcWing题库

题意：

n 个小朋友去食堂吃饭，食堂一共准备了 m 份饭和 k 瓶饮料。

请问，能否让每个小朋友都分到至少一份饭和一瓶饮料？

输入格式

第一行包含三个整数 n,m,k。

输出格式

如果可以让每个小朋友都分到至少一份饭和一瓶饮料，则输出 Yes，否则输出 No。

数据范围

所有测试点满足 1≤n,m,k≤100。

输入样例1：

5 8 6

输出样例1：

Yes

思路：

• 简单判断一下两个条件是否符合就可以。

代码：

#include<iostream>
#include<algorithm>

using namespace std;

int main()
{
    int n,m,k;
    cin>>n>>m>>k;
    
    if(m>=n&&k>=n)cout<<"Yes"<<endl;
    else cout<<"No"<<endl;
    return 0;
}

第二题

题目： 4495. 数组操作 - AcWing题库

题意：

给定一个长度为 nn 的正整数数组 a₁, a₂, …, a_n。

请你对该数组进行 k 次操作，每次操作具体如下：

• 如果数组中存在非零元素，则找到其中的最小非零元素 x，将其输出，并让数组中的所有非零元素都减去 x。
• 如果数组中不存在非零元素，则输出 0 即可。

输入格式

第一行包含两个整数 n,k。

第二行包含 n 个整数 a₁, a₂, …, a_n。

输出格式

共 k 行，其中第 i 行输出第 i 次操作需要输出的值。

数据范围

前四个测试点满足 1 ≤ n ≤ 10。
所有测试点满足 1 ≤ n, k ≤ 10₅，1 ≤ a_i ≤ 10₉。

输入样例1：

3 5
1 2 3

输出样例1：

1
1
1
0
0

思路：

• 因为要找到最小的非零数，我们可以先排序，然后从小到大依次输出。
• 这里有三个需要注意的细节：
  1. 找到第一个非零数。
  2. 每次输出时只需要输出当前值和前一个数的差值即可。因为我们每次将所有非零数减去所输出的值，那么减去的总值其实就是上一个输出的数。
  3. 数组需要去重。

比赛时代码

#include<iostream>
#include<algorithm>
#include<map>

using namespace std;

const int N=100010;

int n,k;
int a[N];
map<int,int>p;

int main()
{
    cin>>n>>k;
    int j=1;//丑陋的map去重方式
    for(int i=1;i<=n;++i)
    {
        int x;
        cin>>x;
        if(p[x]==0)
        {
            a[j++]=x;
            p[x]++;
        }
    }
    
    n=j;
    sort(a+1,a+n+1);
    
    int i=1;
    for(;i<=n;++i)if(a[i])break;
    
    while(k--)
    {
        if(i<=n)
        {
            cout<<a[i]-a[i-1]<<endl;
            i++;
        }
        else cout<<0<<endl;
    }
    
    return 0;
}

unique优雅代码

#include<iostream>
#include<algorithm>
#include<map>

using namespace std;

const int N=100010;

int n,k;
int a[N];

int main()
{
    cin>>n>>k;
    for(int i=1;i<=n;++i)cin>>a[i];
    

    sort(a+1,a+n+1);
    //使用unique对数组进行去重
    n=unique(a+1,a+n+1)-a-1;//使用unique后求数组长度：n=unique(a,a+n)-a; 此处从a[1]开始，所以要额外减1
    
    for(int i=1;i<=k;++i)i<=n?cout<<a[i]-a[i-1]<<endl:cout<<0<<endl;
    
    return 0;

}

第三题

题目： 4496. 吃水果 - AcWing题库

题意:

n 个小朋友站成一排，等着吃水果。

一共有 m 种水果，每种水果的数量都足够多。

现在，要给每个小朋友都发一个水果，要求：在所有小朋友都拿到水果后，恰好有 k 个小朋友拿到的水果和其左边相邻小朋友拿到的水果不同（最左边的小朋友当然不算数，即最左边的小朋友不包含在 k 个小朋友内）。

请你计算，一共有多少种不同的分发水果的方案。

输入格式

一行，三个整数 n,m,k。

输出格式

一个整数，表示合理的分发水果的方案总数量对 998244353 取模后的结果。

数据范围

前 5 个测试点满足 1≤n,m≤5。
所有测试点满足 1 ≤ n,m ≤ 2000，0 ≤ k ≤ n−1。

输入样例1：

3 3 0

输出样例1：

3

思路：

• 其实有两种做法，数学做法和dp。这里只讲一下用dp的做法。
• 用 f[i][j] 表示在前i个小朋友中凑出j个不同的方案数。
• 前i个小朋友凑出j种不同的方案数，就等于前j-1个小朋友凑出j种不同的方案数，加上前i-1个小朋友凑出j-1种不同再乘第i位小朋友的选择数，而第i位小朋友的选择方案共有m-1种，因为他只需要和第i-1位小朋友不同就可以了。
• 综上可得状态转移方程：f[i][j]=(f[i-1][j],f[i-1][j-1]*(m-1));

代码：

#include<iostream>
#include<algorithm>

using namespace std;

const int N=2050,M=998244353;
#define ll long long

ll n,m,k;
ll f[N][N];//f[i][j]在前i个小朋友中凑出j个不同的方案数

int main()
{
    cin>>n>>m>>k;
    
    for(int i=1;i<=n;++i)f[i][0]=m;
    
    for(ll i=2;i<=n;++i)
        for(int j=1;j<=k;++j)
            f[i][j]=(f[i-1][j]%M+f[i-1][j-1]*(m-1)%M)%M;
            
    cout<<f[n][k];
    return 0;
}