4月16日（周六）又打了一场ABC。
结果：A，B题 AC（300分），C、D题?TLE。
目录
网址
https://atcoder.jp/contests/abc248视频讲解
ABC 248 A~D 讲解
A题
题目描述
A - Lacked Number /
Time Limit: 2 sec / Memory Limit: 1024 MB
Score : 100 points
Problem Statement
You are given a string S of length exactly 9 consisting of digits. One but all digits from 0 to 9 appear exactly once in S.
Print the only digit missing in S.
Constraints
S is a string of length 9 consisting of digits.
All characters in S are distinct.
Input
Input is given from Standard Input in the following format:
S
Output
Print the only digit missing in S.
Sample Input 1
Copy
023456789
Sample Output 1
Copy
1
The string 023456789 only lacks 1. Thus, 1 should be printed.
Sample Input 2
Copy
459230781
Sample Output 2
Copy
6
The string 459230781 only lacks 6. Thus, 6 should be printed.
Note that the digits in the string may not appear in increasing order.题目分析
题目大意：
输入一个字符串，包含0~9中的9个数字，输出缺失的数。
思路：
先排序，再把字符串从头到尾循环。当i≠s[i]，输出i，return 0。如果全部循环过一遍还没return 0，直接输出9（博主刚开始没cout<<9，WA了2次）。
题目代码
初次提交的WA代码：
#include<bits/stdc++.h>
using namespace std;
int main(){
string s;
cin>>s;
sort(s.begin(),s.end());
for(int i=0;i<s.size();i++) if(s[i]!=i+'0') {
cout<<i;
return 0;
}
return 0;
}
//ACplease!!!
/* printf(" \n");
printf(" \n");
printf(" * * * * * * * * * * * * \n");
printf(" * * * * * * * * \n");
printf(" * * * * * * * * \n");
printf(" * * * * * \n");
printf(" * * * * * \n");
printf(" * * * * * \n");
printf(" * * * * * \n");
printf(" * * * * * \n");
printf(" * * * * * \n");
printf(" * * * * * * * * * * * * * * * * * * * * * * * * \n");
*/ 再次提交的WA代码：
#include<bits/stdc++.h>
using namespace std;
int main(){
string s;
cin>>s;
sort(s.begin(),s.end());
for(int i=0;i<(int)s.size();i++) if(s[i]!=i+'0') {
cout<<i;
return 0;
}
return 0;
}
//ACplease!!!
/* printf(" \n");
printf(" \n");
printf(" * * * * * * * * * * * * \n");
printf(" * * * * * * * * \n");
printf(" * * * * * * * * \n");
printf(" * * * * * \n");
printf(" * * * * * \n");
printf(" * * * * * \n");
printf(" * * * * * \n");
printf(" * * * * * \n");
printf(" * * * * * \n");
printf(" * * * * * * * * * * * * * * * * * * * * * * * * \n");
*/ 最后的AC代码：
#include<bits/stdc++.h>
using namespace std;
int main(){
string s;
cin>>s;
sort(s.begin(),s.end());
for(int i=0;i<(int)s.size();i++) if(s[i]!=i+'0') {
cout<<i;
return 0;
}
cout<<9;
return 0;
}
//ACplease!!!
/* printf(" \n");
printf(" \n");
printf(" * * * * * * * * * * * * \n");
printf(" * * * * * * * * \n");
printf(" * * * * * * * * \n");
printf(" * * * * * \n");
printf(" * * * * * \n");
printf(" * * * * * \n");
printf(" * * * * * \n");
printf(" * * * * * \n");
printf(" * * * * * \n");
printf(" * * * * * * * * * * * * * * * * * * * * * * * * \n");
*/ 知识讲解
如果有小白不懂排序，可以看下这篇我写的文章：
B题
题目描述
B - Slimes /
Time Limit: 2 sec / Memory Limit: 1024 MB
Score : 200 points
Problem Statement
There are A slimes.
Each time Snuke shouts, the slimes multiply by K times.
In order to have B or more slimes, at least how many times does Snuke need to shout?
Constraints
1≤A≤B≤10
9
2≤K≤10
9
All values in input are integers.
Input
Input is given from Standard Input in the following format:
A B K
Output
Print the answer.
Sample Input 1
Copy
1 4 2
Sample Output 1
Copy
2
We start with one slime. After Snuke's first shout, we have two slimes; after his second shout, we have four slimes. Thus, he needs to shout at least twice to have four or more slimes.
Sample Input 2
Copy
7 7 10
Sample Output 2
Copy
0
We have seven slimes already at the start.
Sample Input 3
Copy
31 415926 5
Sample Output 3
Copy
6
题目分析
题目大意：
有一种史莱姆。每次Snuke喊叫时，史莱姆会乘以K倍。
为了有B或更多史莱姆，Snuke至少需要喊多少次？
思路：水题…… 直接无限循环，每次翻倍，当数量≥B时，跳出。
题目代码
AC代码（水……）：
#include<bits/stdc++.h>
using namespace std;
int main(){
long long a,b,k;
cin>>a>>b>>k;
for(long long i=0;;i++){
if(a>=b){
cout<<i;
return 0;
}
a*=k;
}
return 0;
}
//ACplease!!!
/* printf(" \n");
printf(" \n");
printf(" * * * * * * * * * * * * \n");
printf(" * * * * * * * * \n");
printf(" * * * * * * * * \n");
printf(" * * * * * \n");
printf(" * * * * * \n");
printf(" * * * * * \n");
printf(" * * * * * \n");
printf(" * * * * * \n");
printf(" * * * * * \n");
printf(" * * * * * * * * * * * * * * * * * * * * * * * * \n");
*/ 题目备注
我不相信这题有人WA。
欢迎参与文章底部的投票收集。
C题
题目描述
C - Dice Sum /
Time Limit: 2 sec / Memory Limit: 1024 MB
Score : 300 points
Problem Statement
How many integer sequences of length N, A=(A
1
?
,…,A
N
?
), satisfy all of the conditions below?
1≤A
i
?
≤M (1≤i≤N)
i=1
∑
N
?
A
i
?
≤K
Since the count can get enormous, find it modulo 998244353.
Constraints
1≤N,M≤50
N≤K≤NM
All values in input are integers.
Input
Input is given from Standard Input in the following format:
N M K
Output
Print the answer.
Sample Input 1
Copy
2 3 4
Sample Output 1
Copy
6
The following six sequences satisfy the conditions.
(1,1)
(1,2)
(1,3)
(2,1)
(2,2)
(3,1)
Sample Input 2
Copy
31 41 592
Sample Output 2
Copy
798416518
Be sure to print the count modulo 998244353.题目分析
题目大意：
很短的题目，不解释了。
思路: TLE思路见代码。
题目代码
递归TLE代码：
#include<bits/stdc++.h>
using namespace std;
long long ans=0,n,m,k;
void dfs(long long num,long long sum,long long pos){
sum+=num;
if(pos==n&&sum<=k){
ans++;
return;
}
if(sum>k) return;
for(long long i=1;i<=m;i++)
dfs(i,sum,pos+1);
}
int main(){
cin>>n>>m>>k;
dfs(0,0,0);
cout<<ans%998244353;
return 0;
}
//ACplease!!!
/* printf(" \n");
printf(" \n");
printf(" * * * * * * * * * * * * \n");
printf(" * * * * * * * * \n");
printf(" * * * * * * * * \n");
printf(" * * * * * \n");
printf(" * * * * * \n");
printf(" * * * * * \n");
printf(" * * * * * \n");
printf(" * * * * * \n");
printf(" * * * * * \n");
printf(" * * * * * * * * * * * * * * * * * * * * * * * * \n");
*/ 其它
D题TLE。
其他没做。
我的Atcoder账号
joe_zxq - AtCoder
https://atcoder.jp/users/joe_zxq
版权声明
————————————————
版权声明：本文为CSDN博主「joe_zxq21」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明， ?不欢迎?? 欢迎大家的转载和关注。
