AcWing周赛60

鸽了好久，最近几天多校，今天才抽出时间来补这场总结，还有一场cfdiv2没补总结呢，如果今晚不打edu的话就有两场div2还有一场abc堆积了...

比赛链接 第60场周赛 - AcWing
过题数：3/3
排名:30/1139
这场手速还算快（从排名来看），但是我觉得还是不够快hhh

又一次在1min内过题hhh，锻炼锻炼速度。

A-吃饭（签到）

超级简单的签到

inline void Case_Test()
{
    cin>>n>>m>>k;
    if (n>Min(m,k)) cout<<"No";
    else cout<<"Yes";
}

B-数组操作（堆）

题意

给定一个长度为 $n$ 的正整数数组 $a_1,a_2,...,a_n$。

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

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

思路

也是用一个累计的思想，虽然是所有元素都减去$x$，但是我可以让这个$x$累加，等到轮到该元素的时候再计算，而不是每次减去的时候都减一遍。

并且用到了堆优化，每次选出top也就是当前元素的最小值，如果减去为$0$的话就说明就不是非零元素，继续下一个。

代码

inline void Case_Test()
{
    cin>>n>>m;
    priority_queue<int,vector<int>,greater<int>> q;
    for (int i=1;i<=n;i++)
    {
        cin>>x;
        q.push(x);
    }
    int res = 0;
    while (m--)
    {
        bool ok = false;
        while (!q.empty())
        {
            x = q.top();q.pop();
            //debug(x);debug(res);
            if (x>res)
            {
                cout<<x-res<<endl;
                res += x-res;
                ok = true;
                break;
            }
        }
        if (!ok) cout<<0<<endl;
    }
}

C-吃水果（动态规划,线性DP）

题意

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

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

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

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

思路

线性DP。令dp[i][j]表示从左开始第i个小朋友，有j个不同的小朋友拿到的水果和左边相邻的那个不一样。

根据题意，分为两种情况：

• 与左边相同。那么没得选择，方案数也就是dp[i-1][j]，继承。
• 与左边不同。那么就有$(m-1)$种选择，方案数也就是dp[i-1][j-1]*(m-1)从上一个k-1继承过来。

初始状态当然是第一个特殊的时候，也就是dp[1][0] = m，注意取模。

代码

inline void Case_Test()
{
    cin>>n>>m>>k;
    dp[1][0] = m;
    for (int i=2;i<=n;i++)
        for (int j=0;j<=k;j++)
            dp[i][j] = (dp[i-1][j] + dp[i-1][j-1]*(m-1))%mod;
    cout<<dp[n][k];
}