本文主要是介绍AtCoder Beginner Contest 358 A~E(F,G更新中...),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
A.Welcome to AtCoder Land
题意
给出两个字符串 S , T S, T S,T,请你判断是否满足:
-
字符串 S S S为
AtCoder
-
字符串 T T 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 N N个人会进入会场买票,每个人买票均需要花费 A A A分钟,其中第 i i i个人会在 T i T_i Ti时间到达,如果到达后前面的人还没买完票,就需要等待前面的人完成后继续,否则,可以直接开始买票。
问:经过多少时间后,所有人都买到了票。
分析
由于保证了到达时间是有序的,那么可以依次遍历每个人,第 i i i个人的开始买票时间为第 i − 1 i - 1 i−1个人的结束时间和第 i i i个人的到达时间中的较大值,那么结束时间即为开始时间加上花费的时间。
输出第 n n n个人的结束时间即为答案。
代码
#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 N N种爆米花,爆米花总共有 M M M种味道,使用一个包含 M M M个字符的字符串 S i S_i Si表示第 i i i种爆米花拥有的味道,即使用 S i , j = ′ o ′ S_{i, j} = 'o' Si,j=′o′表示第 i i i种爆米花拥有 j j j味道,用 S i , j = ′ x ′ S_{i, j} = 'x' Si,j=′x′表示第 i i i种保密吗没有 j j j味道。
问:最少买几种爆米花,才能包含所有味道。
分析
观察数据可以发现, N , M ≤ 10 N, M \le 10 N,M≤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 N N个糖果盒,第 i i i个盒子价格为 A i A_i Ai,且包含 A i A_i Ai颗糖果。
你需要买其中 M M M盒糖果,并把这些盒子送给你的朋友,送给第 j j j个朋友的盒子需要至少包含 B j B_j Bj颗糖果。
如果能买到满足要求的 M M M盒糖果,输出最小的花费,如果不能,输出-1
。
分析
首先一定要优先考虑给糖果需求大的选取盒子,那么该怎么选择最优呢,必然会去选择所有满足要求的盒子中 ( B [ j ] ≤ A [ i ] ) (B[j] \le A[i]) (B[j]≤A[i]),价格最低的一个,对于这些盒子,可以使用优先队列维护所有价值大于等于 B [ j ] B[j] 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 a_i ai表示第 i i i个字母的个数。
定义函数 f ( i ) f(i) f(i)表示使用给出的字母组成长度为 i i i的字符串的个数。
给出一个正整数 k k k,请你求出:
- ∑ i = 1 k f ( i ) \sum\limits_{i = 1}^{k}f(i) i=1∑kf(i)
hint:结果较大,需对 998244353 998244353 998244353取模
分析
定义 d p [ i ] [ j ] dp[i][j] dp[i][j]表示选择前 i i i个字母,组成 j j j长度的字符串的方案数。
状态转移:可以在前面所有字母已经放置了 j j j个字母的方案中,再放置 l l l个当前字母,此时的方案数可以视为总共 j + l j + l j+l个空位,要给前面的 j j j个字母放入这些空位中,此时摆放的方案数为 C j + l j C_{j + l}^{j} Cj+lj,产生的总方案数即为 d p [ i − 1 ] [ j ] × C j + l j dp[i - 1][j] \times C_{j + l}^{j} dp[i−1][j]×Cj+lj
完成状态转移后,答案即为 ∑ i = 1 k d p [ 26 ] [ i ] \sum\limits_{i = 1}^{k}dp[26][i] i=1∑kdp[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,赛后大家可以一起交流做题思路,分享做题技巧,欢迎大家的加入。
这篇关于AtCoder Beginner Contest 358 A~E(F,G更新中...)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!