@[TOC]
比赛链接： 第 60 场周赛二十分钟下班，有进步。
B.AcWing 4495. 数组操作
题目
给定一个长度为 n 的正整数数组 a1,a2,…,an。
请你对该数组进行 k 次操作，每次操作具体如下：
- 如果数组中存在非零元素，则找到其中的最小非零元素 x，将其输出，并让数组中的所有非零元素都减去 x。
- 如果数组中不存在非零元素，则输出 0 即可。
思路: 模拟
因为每次操作都是先找到数组中的最小元素，并且让数组中每个元素都减去x，那么可以先将数组从小到大排序，此时数组呈非单调递减，全部都减去一个数后，也不影响数组的顺序，还是非单调递减。那么我们就可以枚举每个元素，从前到后依次操作，最多进行k次。如果当前元素已经等于0的话那么就不能在操作了，找下一个大于0的数，如果直到最后还找不到k个的话，那么就都输出0即可
代码
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> PII;
typedef priority_queue<int, vector<int>, less<int>> Q;
#define x first
#define y second
int dx[4] = {1, -1, 0, 0};
int dy[4] = {0, 0, 1, -1};
const int N = 1e6 + 10;
ll a[N];
signed main()
{
// freopen("in.in", "r", stdin);
// freopen("out.out", "w", stdout);
int n, k;
cin >> n >> k;
// 记录当前总共减去了多少
ll ans = 0;
for (int i = 1; i <= n; i++)
cin >> a[i];
sort(a + 1, a + n + 1);
for (int i = 1; i <= n; i++)
{
// 如果当前已经被减完的话，就跳过当前这个数，因为每个数都要找大于0的
a[i] = max(0ll, a[i] - ans);
// 如果当前元素大于0，并且还需要操作的话就继续操作
if (a[i] > 0 && k > 0)
{
// 操作次数减1
k--;
cout << a[i] << endl;
}
// 减去元素加上
ans += a[i];
}
while (k--)
{
puts("0");
}
return 0;
}C.AcWing 4496. 吃水果
题目
n 个小朋友站成一排，等着吃水果。一共有 m 种水果，每种水果的数量都足够多。
现在，要给每个小朋友都发一个水果，要求：在所有小朋友都拿到水果后，恰好有 k 个小朋友拿到的水果和其左边相邻小朋友拿到的水果不同（最左边的小朋友当然不算数，即最左边的小朋友不包含在 k 个小朋友内）。
请你计算，一共有多少种不同的分发水果的方案。
思路: 状态机模型
根据
闫氏dp法分析，总共有三个参数状态表示：
f[i][j][k]表是前i个小朋友，其中有j个小朋友被选中的总方案数，k==0时，表示第i个小朋友没被选中，k==1表示第i个小朋友被选中状态计算：
- 当第
i个小朋友没被选上时：f[i][j][0] = f[i-1][j][1] + f[i-1][j][0],如果当前小朋友没被选上，那么他一定要和前一个小朋友拿的水果一样，所以就等于前一个的方案数- 当第
i个小朋友被选上时：f[i][j][1] = (f[i-1][j-1][0] + f[i-1][j-1][1]) * (m-1),因为选中的要和前一个不一样，所以方案数要乘上m-1。
代码1
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> PII;
typedef priority_queue<int, vector<int>, less<int>> Q;
#define x first
#define y second
int dx[4] = {1, -1, 0, 0};
int dy[4] = {0, 0, 1, -1};
const int N = 2010, mod = 998244353;
ll f[N][N][2];
ll n, m, k;
signed main()
{
// freopen("in.in", "r", stdin);
// freopen("out.out", "w", stdout);
cin >> n >> m >> k;
// 初始化，第一位置不能选，所以有m种水果可以选
f[1][0][0]=m;
for (int i = 2; i <= n; i++)
{
f[i][0][0] = f[i - 1][0][0] % mod;
for (int j = k; j >= 1; j--)
{
f[i][j][0] = f[i - 1][j][1] % mod + f[i - 1][j][0] % mod;
f[i][j][1] = f[i - 1][j - 1][1] * (m - 1) % mod + f[i - 1][j - 1][0] * (m-1) % mod;
}
}
ll ans = (f[n][k][1] + f[n][k][0]) % mod;
cout << ans;
return 0;
}我们还可以优化，可以不用表示状态那一维。
01背包
状态表示：
f[i][j]表是前i个小朋友，其中有j个小朋友被选中的总方案数状态计算：
- 当第
i个小朋友没被选上时：f[i][j] += f[i-1][j],如果当前小朋友没被选上，那么他一定要和前一个小朋友拿的水果一样，所以就等于前一个的方案数- 当第
i个小朋友被选上时：f[i][j] += f[i-1][j-1] * (m-1),因为选中的要和前一个不一样，所以方案数要乘上m-1。
代码2
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> PII;
typedef priority_queue<int, vector<int>, less<int>> Q;
#define x first
#define y second
int dx[4] = {1, -1, 0, 0};
int dy[4] = {0, 0, 1, -1};
const int N = 2010, mod = 998244353;
ll f[N][N];
ll n, m, k;
signed main()
{
// freopen("in.in", "r", stdin);
// freopen("out.out", "w", stdout);
cin >> n >> m >> k;
f[1][0] = m;
for (int i = 2; i <= n; i++)
{
f[i][0] = f[i - 1][0] % mod;
for (int j = k; j >= 1; j--)
{
f[i][j] = (f[i - 1][j] + f[i - 1][j - 1] * (m - 1)) % mod;
}
}
ll ans = f[n][k];
cout << ans;
return 0;
}
