AtCoder Beginner Contest 357 A~E(F更新中…)
A.Sanitize Hands(模拟)
题意
有
n
n
n个外星人排队对手消毒，其中第
i
i
i个外星人有
H
i
H_i
Hi只手需要消毒，已知消毒液共能使用
M
M
M次，每次可以对一只手消毒，问：总共有多少个外星人的全部手都完成消毒了。
分析
本题并不是一个贪心的题目，而是直接对输入的数据从左往右进行操作，依次判断剩余的消毒液是否足够完成消毒，如果可以，就减去需要使用的量，否则，结束循环。
代码
#include
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
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
k，我们定义
k
k
k等级的地毯需要满足以下要求：
0
0
0等级的地毯是一个
1
×
1
1 imes 1
1×1的网格，且这个网格为黑色。
对于
k
>
0
k > 0
k>0的情况，
k
k
k等级的地毯是一个
3
k
×
3
k
3^{k} imes 3^{k}
3k×3k的网格，可以将这个网格分为
9
9
9个
3
k
−
1
×
3
k
−
1
3^{k – 1} imes 3^{k – 1}
3k−1×3k−1部分。
中心的部分全部都是空白的
其余的8个部分均与
k
−
1
k – 1
k−1等级的地毯一致
给出一个正整数
n
n
n，请你输出
n
n
n等级的地毯
分析
先完成一个
0
0
0等级的地毯，然后按要求依次制作出
1
,
2
,
…
,
n
1, 2, \ldots, n
1,2,…,n等级的地毯，即依次将
i
−
1
i – 1
i−1等级的地毯作为左上角，然后在剩余的
7
7
7个部分复制一遍
i
−
1
i – 1
i−1等级的地毯。
经过
n
n
n次操作后，即得到了
n
n
n等级的地毯。
代码
#include
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
N
N,定义
V
N
V_N
VN为将
N
N
N个数字
N
N
N拼在一起获得的数字，请你求出
V
N
V_N
VN
m
o
d
mod
mod
998244353
998244353
998244353的结果。
分析
定义
K
K
K为
N
N
N的十进制数字数位，定义模数
998244353
998244353
998244353为
P
P
P。
那么有：
V
N
=
N
+
N
⋅
1
0
K
+
N
⋅
1
0
2
K
+
…
+
1
0
(
N
−
1
)
K
V_N = N + N \cdot 10^{K} + N \cdot 10^{2K} + \ldots + 10^{(N – 1)K}
VN=N+N⋅10K+N⋅102K+…+10(N−1)K
V
N
=
N
(
1
+
1
0
K
+
1
0
2
K
+
…
+
1
0
(
N
−
1
)
K
)
V_N = N(1 + 10^{K} + 10^{2K} + \ldots + 10^{(N – 1)K})
VN=N(1+10K+102K+…+10(N−1)K)
V
N
=
N
(
1
0
N
K
−
1
)
1
0
K
−
1
V_N = \frac{N(10^{NK} – 1)}{10^{K} – 1}
VN=10K−1N(10NK−1)
得到这个式子后，即可计算得到最后的答案，而算式中间会出现两个long long范围相乘的算式，可以使用__int128类型进行运算。
hint: 除法需要转化为乘法逆元
代码
#include
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
N
N个点的有向图，点
i
i
i仅包含一条走向
a
i
a_i
ai出边（存在
i
=
a
i
i = a_i
i=ai，即该点不存在出边）。
定义
f
(
i
)
f(i)
f(i)为从点
i
i
i出发可以到达的节点个数(包含节点自身)，请你求出：
∑
i
=
1
n
f
(
i
)
\sum\limits_{i = 1}^{n}f(i)
i=1∑nf(i)
分析
由于每个点仅包含一条出边，那么如果图上成环，必然是这些点首尾相连形成的，且环中不可能存在出边能走向不在环中的点。
那么只要是能到达环的点，均能到达环中的任意点，令
p
p
p为能到达环中的点的数量，
q
q
q为环中包含的点的数量，那么环中的点产生的贡献即为
p
×
q
p imes q
p×q。
对于
p
p
p，可以使用并查集将所有存在边的点连接到同一个集合中，每个集合中的节点数量即为当前的
p
p
p。
对于不在环上的点，产生的贡献即为能到达该点的节点个数，可以使用拓扑排序进行状态继承，每次当节点入度为0时记录该节点的贡献。
对于
q
q
q，在拓扑排序中有节点入队时，就可以知道该点必然不在环中，可以在集合中使用
c
n
t
cnt
cnt数组记录该集合中不在环里的节点数量，使用
p
p
p减去该集合对应的
c
n
t
cnt
cnt即可得到
q
q
q。
那么最后的答案即为环上点的贡献加上不在环上的点的贡献。
代码
#include
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，赛后大家可以一起交流做题思路，分享做题技巧，欢迎大家的加入。
