ABC358(A-G)
评价是 F 比 G 难，不仅构造题，而且细节还多。。。
A - Welcome to AtCoder Land¶
题目大意
给你两个字符串，如果第一个字符串是 AtCoder，且第二个字符串是 Land，则输出 Yes，否则输出 No
参考代码
#include <iostream>
using namespace std;
int main()
{
string s, t;
cin >> s >> t;
if(s == "AtCoder" && t == "Land")
cout << "Yes" << endl;
else
cout << "No" << endl;
return 0;
}
B - Ticket Counter¶
题目大意
办一次业务需要 \(A\) 时间，有 \(N\) 个人需要办业务，这 \(N\) 个人按照时间先后顺序来办业务，第 \(i\) 个人到达的时间是 \(T_i\)。如果没有人排队，则可以直接办业务，否则需要排队。问：最后一个人办完业务的时间是多少？
参考代码
#include <iostream>
using namespace std;
int main()
{
int n, a, x;
cin >> n >> a;
int now = -1;
while(n--)
{
cin >> x;
now = max(now, x);
now += a;
cout << now << '\n';
}
return 0;
}
C - Popcorn¶
题目大意
有 \(N(1 \le N \le 10)\) 个出售爆米花的商人，一共有 \(M(1 \le M \le 10))\) 种口味的爆米花，用长度为 \(M\) 的字符串 \(S_i\) 来描述第 \(i\) 个商人卖哪些爆米花，具体来说，如果 \(S_i\) 的第 \(j\) 个字符是 o，表示商人 \(i\) 有卖第 \(j\) 种口味的爆米花，如果 \(S_i\) 的第 \(j\) 个字符是 x 表示商人 \(i\) 不卖第 \(j\) 种口味的爆米花。
每一个商人至少卖一种爆米花，每一种口味的爆米花至少在一个商人处有卖。问：如何访问最少的商人，并购买到所有口味的爆米花？
解题思路
注意到 \(N \le 10\)，暴力枚举每个商人即可，时间复杂度 \(O(2^n)\)
参考代码
#include <iostream>
#include <vector>
using namespace std;
int main()
{
int n, m;
cin >> n >> m;
vector<int> stand(n);
string s;
for(int i = 0; i < n; i++)
{
cin >> s;
for(int j = 0; j < m; j++)
if(s[j] == 'o')
stand[i] |= 1 << j;
}
int len = 1 << n;
int target = (1 << m) - 1;
int ans = n;
for(int choose = 0; choose < len; choose++)
{
int st = 0, cnt = 0;
for(int i = 0; i < n; i++)
if(choose >> i & 1)
{
st |= stand[i];
cnt++;
}
if(st == target)
ans = min(ans, cnt);
}
cout << ans << endl;
return 0;
}
D - Souvenirs¶
题目大意
有一个商店正在出售 \(N(1 \le N \le 2 \times 10^5)\) 个礼物，第 \(i\) 个礼物的价格是 \(A_i\)。你打算给 \(M(1 \le M \le N)\) 个人购买礼物，并且你打算第 \(i\) 个人送出价格至少为 \(B_i\) 的礼物。
问：如何以最少的花费给每个人都送出礼物？如果无法给每个人都送出价格至少为 \(B_i\) 的礼物，输出 -1。
解题思路
对 \(A_i\) 和 \(B_i\) 排序，然后双指针即可。
参考代码
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main()
{
int n, m;
cin >> n >> m;
vector<int> a(n), b(m);
for (int i = 0; i < n; i++)
cin >> a[i];
for (int i = 0; i < m; i++)
cin >> b[i];
sort(a.begin(), a.end());
sort(b.begin(), b.end());
long long ans = 0;
for (int i = 0, j = 0; j < m; j++)
{
while (i < n && a[i] < b[j])
i++;
if (i == n)
{
cout << -1 << endl;
return 0;
}
ans += a[i++];
}
cout << ans << endl;
return 0;
}
E - Alphabet Tiles¶
题目大意
给你一个整数 \(K(1 \le K \le 1000)\) 以及 \(26\) 个整数 \(C_1, C_2, \cdots, C_{26}\)，求出满足下列条件的字符串 \(S\) 的个数：
- \(1 \le |S| \le K\)
- \(S\) 中只包含大写字母，且
A的出现次数小于等于 \(C_1\)，B的出现次数小于等于 \(C_2\)，\(\cdots\)，Z的出现次数小于等于 \(C_{26}\)
答案对 \(998244353\) 取模。
解题思路
定义 \(dp[i][j]\) 表示长度为使用前 \(i\) 种字符，凑出长度为 \(j\) 的字符串的方案数。
反过来也可以，也就是让第一维表示长度，第二维表示使用多少种字符。
转移时，枚举第 \(i\) 种字符贡献了多少个，假设贡献了 \(x\) 个，这相当于在 \(j\) 个位置中，选出 \(x\) 个位置字符 \(i\)，剩下的部分相当于使用 \(i-1\) 种字符，凑出长度为 \(j-x\) 的方案数。即： $$ dp[i][j] = \sum_{x = 0}^{\min(j, c[i])}C_j^x * dp[i-1][j-x] $$ 其中 \(C_j^x\) 表示组合数，可以在 \(O(k^2)\) 的时间内预处理出来，转移的时候需要枚举 \(x\)，至多枚举 \(0\) 到 \(k\)，因此总的时间复杂度为 \(O(26k^2)\)，考虑到枚举的时候有一些常数，这个数据量是能过的。
答案就是 \(\sum\limits_{i=1}^k dp[26][i]\)
参考代码
#include <iostream>
#include <vector>
using namespace std;
typedef long long LL;
const int mod = 998244353;
int main()
{
int k, c[27];
cin >> k;
for(int i = 1; i <= 26; i++)
cin >> c[i];
vector<vector<LL>> com(k+1, vector<LL>(k+1));
com[0][0] = 1;
for(int i = 1; i <= k; i++)
{
com[i][0] = 1;
for(int j = 1; j <= i; j++)
com[i][j] = (com[i-1][j] + com[i-1][j-1]) % mod;
}
vector<vector<LL>> dp(27, vector<LL>(k+1));
dp[0][0] = 1;
for(int i = 1; i <= 26; i++)
{
dp[i][0] = 1;
for(int j = 1; j <= k; j++)
for(int x = 0; x <= min(j, c[i]); x++)
dp[i][j] = (dp[i][j] + dp[i-1][j-x] * com[j][x] % mod) % mod;
}
LL ans = 0;
for(int i = 1; i <= k; i++)
ans = (ans + dp[26][i]) % mod;
cout << ans << endl;
return 0;
}
G - AtCoder Tour¶
题目大意
有一个 \(H \times W(1 \le H, W \le 50)\) 的二维矩阵，矩阵的每个位置 \((i, j)\) 都有一个正整数 \(A_{i, j}\)。你的初始位置是 \((S_i, S_j)\)。你可以执行 \(K(1 \le K \le 10^9)\) 次操作，每一次操作时，可以选择移动到上下左右相邻的位置，或者留在原地。每一次操作后，假设你所在的位置是 \((i, j)\)，你将获得 \(A_{i, j}\) 的得分。
问：\(K\) 次操作后，最多能获得多少分？
解题思路
注意到 \(K\) 很大，如果 \(K\) 非常非常大，那么最优的策略就是移动到矩阵的最大值，然后剩下的次数在原地停留。
进一步我们会发现，答案一定是遵循着一种策略：即移动到某个数字比较大的位置，然后在原地停留。于是我们可以枚举最终停留的位置，假设我们枚举出的最终位置是 \((r, c)\)
接下，考虑如何移动到 \((r, c)\)，这意味着我们需要花费几步从 \((S_i, S_j)\) 移动到 \((r, c)\)，事实上，并不是按照曼哈顿距离（即消耗次数最少的）路径就是最优解，考虑下面这个样例：
100 100 100
100 1 100
100 1 100
100 1 100
100 1 101
假设 \(K\) 的次数较少，起始的位置是左下角的 100，最优的方式应该沿着所有 100 的路线走到 101，而不是往右走经过 1。
考虑这个例子：
100 100 100
100 1 100
100 1 100
100 1 100
100 1 10000000
这种情况下，显然最优的方式就应该是往右走，因为这样会更节省操作的次数，把剩余的次数获得最大值的分数。
因此，我们需要考虑从 \((S_i, S_j)\) 移动到 \((r, c)\) 的所有路径中的最大值，同时，靠需要考虑这条路径走了多少步。
定义 \(dis[t][i][j]\) 表示从起点走了 \(t\) 步走到 \((r, c)\) 的所有路径中，路径之和的最大值。
\(dis\) 的第一维只需要开到 \(n\times m\) 就够了，因为在二维矩阵中，这种绕远路的方式最多走 \(n \times m\) 步，于是预处理出 \(dis\) 的时间复杂度为 \(O(n^2m^2)\)。
接下来，只需要枚举所有的 \(t\) 以及 \((i, j)\)，然后剩下的次数全部停留在 \((i, j)\)，输出所有答案的最大值即可。
参考代码
#include <iostream>
#include <vector>
using namespace std;
typedef long long LL;
int main()
{
int n, m, k;
cin >> n >> m >> k;
int t = min(n * m, k);
int sr, sc;
cin >> sr >> sc;
sr--;
sc--;
vector<vector<int>> a(n, vector<int>(m));
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++)
cin >> a[i][j];
vector<vector<vector<LL>>> dis(t + 1, vector<vector<LL>>(n, vector<LL>(m, -1)));
dis[0][sr][sc] = 0;
static const int dr[] = {-1, 1, 0, 0};
static const int dc[] = {0, 0, -1, 1};
auto inlim = [n, m](int r, int c)
{ return r >= 0 && r < n && c >= 0 && c < m; };
for (int i = 1; i <= t; i++)
for (int r = 0; r < n; r++)
for (int c = 0; c < m; c++)
for (int j = 0; j < 4; j++)
{
int lr = r + dr[j], lc = c + dc[j];
if (!inlim(lr, lc) || dis[i - 1][lr][lc] == -1)
continue;
dis[i][r][c] = max(dis[i][r][c], dis[i - 1][lr][lc] + a[r][c]);
}
LL ans = 0;
for (int i = 0; i <= t; i++)
for (int r = 0; r < n; r++)
for (int c = 0; c < m; c++)
{
if (dis[i][r][c] == -1)
continue;
ans = max(ans, dis[i][r][c] + (LL)a[r][c] * (k - i));
}
cout << ans << endl;
return 0;
}
创建日期: 2024-06-20