题目分析
A 数青蛙
根据青蛙的个数分类计算：
- 青蛙数小于等于
2
2
2：此时青蛙数、眼睛数、嘴巴数和腿数读出来只读1
1
1 个字，故此时一句话14
14
14 个字。 - 青蛙数大于
2
2
2，小于等于5
5
5：此时青蛙数、眼睛数和嘴巴数读出来只读1
1
1 个字，腿数读出来只读2
2
2 个字，故此时一句话15
15
15 个字。 - 青蛙数大于
5
5
5，小于等于9
9
9：此时青蛙数和嘴巴数读出来只读1
1
1 个字，眼睛数读出来只读2
2
2 个字，腿数读出来只读3
3
3 个字，故此时一句话17
17
17 个字。 - 青蛙数等于
10
10
10：此时青蛙数和嘴巴数读出来只读1
1
1 个字，眼睛数和腿数读出来只读2
2
2 个字，故此时一句话16
16
16 个字。 - 青蛙数大于
10
10
10，小于等于14
14
14：此时青蛙数和嘴巴数读出来只读2
2
2 个字，眼睛数和腿数读出来只读3
3
3 个字，故此时一句话20
20
20 个字。 - 青蛙数等于
15
15
15：此时青蛙数、嘴巴数、眼睛数和腿数读出来只读2
2
2 个字，故此时一句话18
18
18 个字。 - 青蛙数大于
15
15
15，小于等于19
19
19：此时青蛙数和嘴巴数读出来只读2
2
2 个字，眼睛数和腿数读出来只读3
3
3 个字，故此时一句话20
20
20 个字。 - 青蛙数等于
20
20
20：此时青蛙数、嘴巴数、眼睛数和腿数读出来只读2
2
2 个字，故此时一句话18
18
18 个字。
综上所述，可以得到共有
2
×
14
+
3
×
15
+
4
×
17
+
16
+
4
×
20
+
18
+
4
×
20
+
18
=
28
+
45
+
68
+
16
+
80
+
18
+
80
+
18
=
353
2 imes14+3 imes15+4 imes17+16+4 imes20+18+4 imes20+18=28+45+68+16+80+18+80+18=353
2×14+3×15+4×17+16+4×20+18+4×20+18=28+45+68+16+80+18+80+18=353 个字。
B 互质
解法一
对于任意两个数
x
x
x 和
y
y
y，如果它们互质，那么
gcd
(
x
,
y
)
\gcd(x,y)
gcd(x,y) 的值就会等于
1
1
1。所以可以用
1
1
1 到
2020
2020
2020 中的数都与
1018
1018
1018 计算一次最大公因数，如果结果为
1
1
1，就累加个数。
代码如下：
#include
#include
using namespace std;
signed main() {
ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
int ans=0;
for(int i=1;i<=2020;++i) if(__gcd(i,1018)==1) ++ans;//如果最大公因数为1就累加和
cout<<ans;
return 0;
}
最终得到答案为
1008
1008
1008。
解法二
将
2018
2018
2018 分解质因数得到
2
×
509
=
1018
2 imes509=1018
2×509=1018。
在
1
1
1 到
2020
2020
2020 中，有
2020
÷
2
=
1010
2020\div2=1010
2020÷2=1010 个数是
2
2
2 的倍数。
在
1
1
1 到
2020
2020
2020 中，有
⌊
2020
÷
509
⌋
=
3
\lfloor 2020\div509\rfloor=3
⌊2020÷509⌋=3 个数是
509
509
509 的倍数。
在
1
1
1 到
2020
2020
2020 中
2
2
2 和
509
509
509 共有的倍数有
⌊
2020
÷
lcm
(
2
,
509
)
⌋
=
⌊
2020
÷
1018
⌋
=
1
\lfloor2020\div ext{lcm}(2,509)\rfloor=\lfloor2020\div1018\rfloor=1
⌊2020÷lcm(2,509)⌋=⌊2020÷1018⌋=1 个。
故得出在
1
1
1 到
2020
2020
2020 中与
2018
2018
2018 互质的数有
2020
−
1010
−
3
+
1
=
1008
2020-1010-3+1=1008
2020−1010−3+1=1008 个。
C 车牌
用 dfs 进行搜索即可。
代码如下：
#include
using namespace std;
int ans=0;
void dfs(string str) {//dfs搜索
if(str.size()==6) {//有6位了累加答案
++ans;
return;
}
if(str.size()<3) {//当前长度小于3
for(string i="0";i[0]<='9';++i[0]) if(str.size()<2||!(str[str.size()-1]==i[0]&&str[str.size()-2]==str[str.size()-1])) dfs(str+i);
for(string i="A";i[0]<='F';++i[0]) if(str.size()<2||!(str[str.size()-1]==i[0]&&str[str.size()-2]==str[str.size()-1])) dfs(str+i);
}
//当前长度大于3
else for(string i="0";i[0]<='9';++i[0]) if(!(str[str.size()-1]==i[0]&&str[str.size()-2]==str[str.size()-1])) dfs(str+i);
}
signed main() {
ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
dfs("");
cout<<ans;
return 0;
}
D Fibonacci 集合
可以使用优先队列。
对于任意一个队列中的元素
x
x
x，判断
3
×
x
+
2
3 imes x+2
3×x+2、
5
×
x
+
3
5 imes x+3
5×x+3 和
8
×
x
+
5
8 imes x+5
8×x+5 是否已经出现过，未出现过就将其压入队列中。若
x
x
x 是队列中第第
2020
2020
2020 个元素时，就输出
x
x
x。
代码如下：
#include
#include
using namespace std;
bool flag[1000000];//统计该值是否出现过
int num;//统计当前元素是第几个
signed main() {
priority_queue<int,vector<int>,greater<int>>que;//优先队列
que.push(1),que.push(2),que.push(3),que.push(5),que.push(8),flag[1]=flag[2]=flag[3]=flag[5]=flag[8]=true;
while(!que.empty()) {
++num;//累加个数
if(num==2020) {
cout<<que.top();//如果是第2020个就输出
return 0;
}
//判断是否出现过，若未出现，将其压入队列
if(flag[que.top()*3+2]==false) flag[que.top()*3+2]=true,que.push(que.top()*3+2);
if(flag[que.top()*5+3]==false) flag[que.top()*5+3]=true,que.push(que.top()*5+3);
if(flag[que.top()*8+5]==false) flag[que.top()*8+5]=true,que.push(que.top()*8+5);
que.pop();//记得出队
}
return 0;
}
最终得到答案为
41269
41269
41269。
E 上升子串
因为没有数据，就只附个代码了（思路：深搜）：
#include
using namespace std;
int ans,n,m,sum[1000][1000];//n为行数，m为列数
string str[1000];
int dfs(int x,int y) {
if(sum[x][y]) return sum[x][y];//已经搜索过就不用再搜
sum[x][y]=1;//初始赋值为1
//搜索
if(x+1<n&&str[x+1][y]>str[x][y]) sum[x][y]+=dfs(x+1,y);
if(x&&str[x-1][y]>str[x][y]) sum[x][y]+=dfs(x-1,y);
if(y+1<n&&str[x][y+1]>str[x][y]) sum[x][y]+=dfs(x,y+1);
if(y&&str[x][y-1]>str[x][y]) sum[x][y]+=dfs(x,y-1);
return sum[x][y];//放回答案
}
signed main() {
ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
cin>>n>>m;
for(int i=0;i<n;++i) cin>>str[i];
for(int i=0;i<n;++i) for(int j=0;j<m;++i) ans+=dfs(i,j);//搜索，累加答案
cout<<ans;
return 0;
}
请注意：本题正确答案是
qwq
exttt{qwq}
qwq！
Code
#include
using namespace std;
signed main() {
ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
string ans[]={
"353",
"1008",
"4002750",
"41269",
"qwq"
};
cout<<ans[getchar()-'A'];
return 0;
}
