AtCoder Beginner Contest 358 A~E(F,G更新中...)

A.Welcome to AtCoder Land

题意

给出两个字符串$S,T$，请你判断是否满足：

• 字符串$S$为AtCoder

• 字符串$T$为Land

分析

输入后判断即可

代码

#include<bits/stdc++.h>
using namespace std;
void solve() {string s, t;cin >> s >> t;if (s == "AtCoder" && t == "Land") {cout << "Yes" << endl;} else {cout << "No" << endl;}
}
int main() {solve();return 0;
}

B.Ticket Counter(思维)

题意

有$N$个人会进入会场买票，每个人买票均需要花费$A$分钟，其中第$i$个人会在$T_i$时间到达，如果到达后前面的人还没买完票，就需要等待前面的人完成后继续，否则，可以直接开始买票。

问：每个人买票结束的时间是多少。

分析

由于保证了到达时间是有序的，那么可以依次遍历每个人，第$i$个人的开始买票时间为第$i-1$个人的结束时间和第$i$个人的到达时间中的较大值，那么结束时间即为开始时间加上花费的时间。

输出每个人买完票的时间即可。

代码

#include<bits/stdc++.h>
using namespace std;
int t[105];
void solve() {int n, a;cin >> n >> a;int now = 0;for (int i = 1; i <= n; i++) {cin >> t[i];now = max(now, t[i]);now += a;cout << now << endl;}
}
int main() {solve();return 0;
}

C. Popcorn(二进制枚举)

题意

有$N$种爆米花，爆米花总共有$M$种味道，使用一个包含$M$个字符的字符串$S_i$表示第$i$种爆米花拥有的味道，即使用$S_{i,j}{=}^{\prime }{o}^{\prime }$表示第$i$种爆米花拥有$j$味道，用$S_{i,j}{=}^{\prime }{x}^{\prime }$表示第$i$种保密吗没有$j$味道。

问：最少买几种爆米花，才能包含所有味道。

分析

观察数据可以发现，$N,M\le 10$，那么数据量是非常小的，可以直接使用二进制枚举去枚举所有选择方案，记录包含所有味道中，选择爆米花种类最小的一个即为最后的答案。

代码

#include<bits/stdc++.h>
using namespace std;
string s[105];
int vis[15];
void solve() {int n, m;cin >> n >> m;for (int i = 0; i < n; i++) {cin >> s[i];}int ans = n;for (int i = (1 << n) - 1; i >= 0; i--) {memset(vis, 0, sizeof (vis));int cnt = 0, sum = 0;for (int j = 0; j < n; j++) {if (i & (1 << j)) {cnt++;for (int k = 0; k < m; k++) {if (s[j][k] == 'o') {vis[k]++;if (vis[k] == 1) sum++;}}}}if (sum == m) {ans = min(ans, cnt);}}cout << ans << endl;
}
int main() {solve();return 0;
}

D.Souvenirs(贪心)

题意

有$N$个糖果盒，第$i$个盒子价格为$A_i$，且包含$A_i$颗糖果。

你需要买其中$M$盒糖果，并把这些盒子送给你的朋友，送给第$j$个朋友的盒子需要至少包含$B_j$颗糖果。

如果能买到满足要求的$M$盒糖果，输出最小的花费，如果不能，输出-1。

分析

首先一定要优先考虑给糖果需求大的选取盒子，那么该怎么选择最优呢，必然会去选择所有满足要求的盒子中$(B[j]\le A[i])$，价格最低的一个，对于这些盒子，可以使用优先队列维护所有价值大于等于$B[j]$的糖果盒子，每次从优先队列取出最小的元素加到答案中，如果取不出来，则说明无解。

代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
priority_queue<int, vector<int>, greater<int> >Q;
const int N = 2e5 + 5e2;
int n, m, a[N], b[N];
void solve() {cin >> n >> m;for (int i = 1; i <= n; i++) cin >> a[i];for (int j = 1; j <= m; j++) cin >> b[j];sort(a + 1, a + n + 1);sort(b + 1, b + m + 1);ll ans = 0;for (int i = m, j = n; i >= 1; i--) {while (j >= 1 && a[j] >= b[i]) {Q.push(a[j--]);}if (Q.empty()) {cout << -1 << endl;return;}ans += Q.top();Q.pop();}cout << ans << endl;
}
int main() {solve();return 0;
}

E.Alphabet Tiles(DP)

题意

给出26个字母中每个字母的数量，即使用$a_i$表示第$i$个字母的个数。

定义函数$f(i)$表示使用给出的字母组成长度为$i$的字符串的个数。

给出一个正整数$k$，请你求出：

• $\sum _{i=1}^{k}f(i)$

hint：结果较大，需对$998244353$取模

分析

定义$dp[i][j]$表示选择前$i$个字母，组成$j$长度的字符串的方案数。

状态转移：可以在前面所有字母已经放置了$j$个字母的方案中，再放置$l$个当前字母，此时的方案数可以视为总共$j+l$个空位，要给前面的$j$个字母放入这些空位中，此时摆放的方案数为$C_{j+l}^j$，产生的总方案数即为$dp[i-1][j]\times C_{j+l}^j$

完成状态转移后，答案即为$\sum _{i=1}^{k}dp[26][i]$

代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e3 + 5e2, mod = 998244353;
ll C[N][N], k, a[N], dp[N][N];
void init() {C[0][0] = 1;for (int i = 1; i <= 1000; i++) {C[i][0] = C[i][i] = 1;for (int j = 1; j <= i; j++) {C[i][j] = (C[i - 1][j] + C[i - 1][j - 1]) % mod;}}
}
void solve() {cin >> k;for (int i = 1; i <= 26; i++) cin >> a[i];dp[0][0] = 1;for (int i = 1; i <= 26; i++) {for (int j = 0; j <= k; j++) {for (int l = 0; l <= a[i]; l++) {if (j + l > k) break;dp[i][j + l] = (dp[i][j + l] + dp[i - 1][j] * C[j + l][j] % mod) % mod;}}}ll ans = 0;for (int i = 1; i <= k; i++) {ans = (ans + dp[26][i]) % mod;}cout << ans << endl;
}
int main() {init();solve();return 0;
}

F,G更新中…

赛后交流

在比赛结束后，会在交流群中给出比赛题解，同学们可以在赛后查看题解进行补题。

群号： 704572101，赛后大家可以一起交流做题思路，分享做题技巧，欢迎大家的加入。