AtCoder Beginner Contest 357 A~E(F更新中...)

本文主要是介绍AtCoder Beginner Contest 357 A~E(F更新中...)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

A.Sanitize Hands(模拟)

题意

有$n$个外星人排队对手消毒，其中第$i$个外星人有$H_i$只手需要消毒，已知消毒液共能使用$M$次，每次可以对一只手消毒，问：总共有多少个外星人的全部手都完成消毒了。

分析

本题并不是一个贪心的题目，而是直接对输入的数据从左往右进行操作，依次判断剩余的消毒液是否足够完成消毒，如果可以，就减去需要使用的量，否则，结束循环。

代码

#include <bits/stdc++.h>using namespace std;
typedef long long ll;
const int N = 3e5 + 5e2;
int a[N];void solve() {int n, m;cin >> n >> m;for (int i = 1; i <= n; i++) {cin >> a[i];}int ans = 0;for (int i = 1; i <= n; i++) {if (m >= a[i]) {m -= a[i];ans++;} else break;}cout << ans << endl;
}int main() {solve();return 0;
}

B.Uppercase and Lowercase

题意

给出一个既包含大写字母，也包含小写字母的字符串（保证字符串长度为奇数），如果该字符串中大写字母较多，则将所有字母改为大写字母，否则，将所有字母改为小写字母。

分析

先统计大小写字母的数量，然后按题目要求操作即可。

代码

#include <bits/stdc++.h>using namespace std;
typedef long long ll;
const int N = 3e5 + 5e2;
int a[N];void solve() {int u = 0, l = 0;string s;cin >> s;for (auto i : s) {if (i >= 'a') {l++;} else {u++;}}for (auto &i : s) {if (u > l && i >= 'a') {i -= 32;} else if (u < l && i <= 'Z') {i += 32;}}cout << s << endl;
}int main() {solve();return 0;
}

C.Sierpinski carpet(打印图形)

题意

对于一个非负整数$k$，我们定义$k$等级的地毯需要满足以下要求：

• $0$等级的地毯是一个$1\times 1$的网格，且这个网格为黑色。

• 对于$k>0$的情况，$k$等级的地毯是一个$3^k\times 3^k$的网格，可以将这个网格分为$9$个$3^{k-1}\times 3^{k-1}$部分。

  • 中心的部分全部都是空白的

  • 其余的8个部分均与$k-1$等级的地毯一致

给出一个正整数$n$，请你输出$n$等级的地毯

分析

先完成一个$0$等级的地毯，然后按要求依次制作出$1,2,\dots ,n$等级的地毯，即依次将$i-1$等级的地毯作为左上角，然后在剩余的$7$个部分复制一遍$i-1$等级的地毯。

经过$n$次操作后，即得到了$n$等级的地毯。

代码

#include <bits/stdc++.h>using namespace std;
typedef long long ll;
const int N = 3e5 + 5e2;
char c[1005][1005];void color(int x, int y, int len) {for (int i = x; i < x + len; i++) {for (int j = y; j < y + len; j++) {c[i][j] = c[i - x][j - y];}}
}void solve() {memset(c, '.', sizeof(c));c[0][0] = '#';int n;cin >> n;int len = 1;for (int i = 1; i <= n; i++) {for (int j = 0; j < 3; j++) {for (int k = 0; k < 3; k++) {if (k == j && j <= 1) continue;color(j * len, k * len, len);}}len *= 3;}for (int i = 0; i < len; i++) {for (int j = 0; j < len; j++) {cout << c[i][j];}cout << endl;}
}int main() {solve();return 0;
}

D.88888888(数学)

题意

给出一个数字$N$,定义$V_N$为将$N$个数字$N$拼在一起获得的数字，请你求出$V_N$ $mod$ $998244353$的结果。

分析

定义$K$为$N$的十进制数字数位，定义模数$998244353$为$P$。

那么有：

• $V_N=N+N\cdot 10^K+N\cdot 10^{2K}+\dots +10^{(N-1)K}$

• $V_N=N(1+10^K+10^{2K}+\dots +10^{(N-1)K})$

• $V_N=\frac{N(10^{NK}-1)}{10^K-1}$

得到这个式子后，即可计算得到最后的答案，而算式中间会出现两个long long范围相乘的算式，可以使用__int128类型进行运算。

hint: 除法需要转化为乘法逆元

代码

#include <bits/stdc++.h>using namespace std;
typedef long long ll;
const int N = 3e5 + 5e2;
const ll mod = 998244353;__int128 qpow(__int128 a, __int128 b) {__int128 res = 1;while (b) {if (b & 1) res = res * a % mod;a = a * a % mod;b >>= 1;}return res;
}int getLen(__int128 x) {int cnt = 0;while (x) {cnt++;x /= 10;}return cnt;
}void solve() {ll num;cin >> num;__int128 n = num;__int128 ans = n * (qpow(10, getLen(n) * n) - 1) % mod * qpow(qpow(10, getLen(n)) - 1, mod - 2) % mod;ll res = ans;cout << res << endl;
}int main() {solve();return 0;
}

E.Reachability in Functional Graph(拓扑排序)

题意

给出一个包含$N$个点的有向图，点$i$仅包含一条走向$a_i$出边（存在$i=a_i$，即该点不存在出边）。

定义$f(i)$为从点$i$出发可以到达的节点个数(包含节点自身)，请你求出：

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

分析

由于每个点仅包含一条出边，那么如果图上成环，必然是这些点首尾相连形成的，且环中不可能存在出边能走向不在环中的点。

那么只要是能到达环的点，均能到达环中的任意点，令$p$为能到达环中的点的数量，$q$为环中包含的点的数量，那么环中的点产生的贡献即为$p\times q$。

对于$p$，可以使用并查集将所有存在边的点连接到同一个集合中，每个集合中的节点数量即为当前的$p$。

对于不在环上的点，产生的贡献即为能到达该点的节点个数，可以使用拓扑排序进行状态继承，每次当节点入度为0时记录该节点的贡献。

对于$q$，在拓扑排序中有节点入队时，就可以知道该点必然不在环中，可以在集合中使用$cnt$数组记录该集合中不在环里的节点数量，使用$p$减去该集合对应的$cnt$即可得到$q$。

那么最后的答案即为环上点的贡献加上不在环上的点的贡献。

代码

#include <bits/stdc++.h>using namespace std;
typedef long long ll;
const int N = 3e5 + 5e2;int n, a[N], d[N], p[N], f[N], sum[N], cnt[N];
vector<int> G[N];
ll ans;
int find(int x) {return f[x] == x ? x : f[x] = find(f[x]);
}void merge(int a, int b) {int fa = find(a),fb = find(b);if (fa != fb) {f[fa] = fb;sum[fb] += sum[fa];}
}
queue<int> Q;
void solve() {cin >> n;for (int i = 1; i <= n; i++) {f[i] = i;sum[i] = 1;p[i] = 1;}for (int i = 1; i <= n; i++) {cin >> a[i];G[i].push_back(a[i]);d[a[i]]++;merge(i, a[i]);}for (int i = 1; i <= n; i++) {if (d[i] == 0) {Q.push(i);ans += 1;cnt[find(i)]++;}}while (!Q.empty()) {auto u = Q.front();Q.pop();for (auto v : G[u]) {d[v]--;p[v] += p[u];if (d[v] == 0) {cnt[find(v)]++;//记录当前集合不在环上的节点数量ans += p[v];//不在环上的点的贡献Q.push(v);}}}for (int i = 1; i <= n; i++) {if (i == f[i]) {//sum[i]是所有能到达当前环的点的个数//cnt[i]为不在环上的节点个数//sum[i] - cnt[i]即为环上的节点数量ans += 1ll * (sum[i] - cnt[i]) * sum[i];}}cout << ans << endl;
}int main() {solve();return 0;
}

F.Two Sequence Queries

更新中…

赛后交流

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

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

这篇关于AtCoder Beginner Contest 357 A~E(F更新中...)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---