填空题
A的个数
以下是一个 25 行 25 列的字母矩阵，全部由字母 A 和 B 组成。 AAAAAAABABBAABABABAAAAAAA
ABBBBBABBAABBBBBABABBBBBA ABAAABABBBABAABBBBABAAABA
ABAAABABBBBBAABAABABAAABA ABAAABABBABABBABABABAAABA
ABBBBBABBBABAABBBBABBBBBA AAAAAAABABABABABABAAAAAAA
BBBBBBBBABAABABBBBBBBBBBB AABAABABBAAABBAAABABBBBBA
ABBABABBBABBAAAABBBBAAAAB BBBBAAABABAABABAABBBAABBA
BBAABABABAAAABBBAABBAAAAA ABABBBABAABAABABABABBBBBA
AAAABBBBBABBBBAAABBBABBAB AABAABAAABAAABAABABABAAAA
ABBBBBBBBABABBBBABAABBABA ABBBAAABAAABBBAAAAAAABAAB
BBBBBBBBABBAAABAABBBABBAB AAAAAAABBAAABBBBABABAABBA
ABBBBBABBAABABAAABBBABBAA ABAAABABABBBAAAAAAAAAABAA
ABAAABABABABBBABBAABBABAA ABAAABABBABBABABAABAABAAA
ABBBBBABABBBBBABBAAAABAAA AAAAAAABAABBBAABABABBABBA 请问在这个矩阵中有多少个字母A？
#include <bits/stdc++.h>
using namespace std;
int main()
{
string s="AAAAAAABABBAABABABAAAAAAAABBBBBABBAABBBBBABABBBBBAABAAABABBBABAABBBBABAAABAABAAABABBBBBAABAABABAAABAABAAABABBABABBABABABAAABAABBBBBABBBABAABBBBABBBBBAAAAAAAABABABABABABAAAAAAABBBBBBBBABAABABBBBBBBBBBBAABAABABBAAABBAAABABBBBBAABBABABBBABBAAAABBBBAAAABBBBBAAABABAABABAABBBAABBABBAABABABAAAABBBAABBAAAAAABABBBABAABAABABABABBBBBAAAAABBBBBABBBBAAABBBABBABAABAABAAABAAABAABABABAAAAABBBBBBBBABABBBBABAABBABAABBBAAABAAABBBAAAAAAABAABBBBBBBBBABBAAABAABBBABBABAAAAAAABBAAABBBBABABAABBAABBBBBABBAABABAAABBBABBAAABAAABABABBBAAAAAAAAAABAAABAAABABABABBBABBAABBABAAABAAABABBABBABABAABAABAAAABBBBBABABBBBBABBAAAABAAAAAAAAAABAABBBAABABABBABBA";
int res=0;
for(int i=0;i<s.size();i++)
if(s[i]=='A')res++;
cout<<res<<endl;
return 0;
}
最2数字
如果一个整数的某个数位包含 2 ，则称这个数为一个“最2数字”。例如：102、2021 都是最2数字。 请问在 1（含） 到 2021（含）
中，有多少个最2数字。
#include <bits/stdc++.h>
using namespace std;
int main()
{
int res=0;
for(int i=1;i<=2021;i++)
{
int x=i;
while(x)
{
int m=x%10;
x/=10;
if(m==2)
{
res++;
break;
}
}
}
cout<<res<<endl;
return 0;
}
最少次数
有一个整数 A=2021，每一次，可以将这个数加 1 、减 1 或除以 2，其中除以 2 必须在数是偶数的时候才允许。
例如，2021 经过一次操作可以变成 2020、2022。
再如，2022 经过一次操作可以变成 2021、2023 或 1011。
请问，2021 最少经过多少次操作可以变成 1。
#include <bits/stdc++.h>
using namespace std;
int dist[10010];
bool st[10010];
int main()
{
int n=2021;
queue<int>q;
q.push(n);
memset(dist,0x3f,sizeof dist);
dist[n]=0;
while(q.size())
{
auto t=q.front();
q.pop();
if(t==1)
{
cout<<dist[1]<<endl;
return 0;
}
if(t%2)
{
int j=t+1,k=t-1;
if(!st[j])
{
q.push(j);
st[j]=true;
dist[j]=dist[t]+1;
}
if(!st[k])
{
q.push(k);
st[k]=true;
dist[k]=dist[t]+1;
}
}
else
{
int h=t/2;
if(!st[h])
{
q.push(h);
st[h]=true;
dist[h]=dist[t]+1;
}
}
}
return 0;
}
超大玉螺旋丸
对于一个 n 行 m 列的表格，我们可以使用螺旋的方式给表格依次填上正整数，我们称填好的表格为一个螺旋矩阵。
例如，一个 4 行 5 列的螺旋矩阵如下：
1 2 3 4 5
14 15 16 17 6
13 20 19 18 7
12 11 10 9 8
请问，一个 30 行 30 列的螺旋矩阵，第 20 行第 20 列的值是多少？
#include <bits/stdc++.h>
using namespace std;
const int N=35;
int f[N][N];
int main()
{
int k=1;
f[1][1]=1;
int x=1,y=1;
while(k<30*30)
{
while(y<30&&!f[x][y+1])f[x][++y]=++k;
while(x<30&&!f[x+1][y])f[++x][y]=++k;
while(y>1&&!f[x][y-1])f[x][--y]=++k;
while(x>1&&!f[x-1][y])f[--x][y]=++k;
}
cout<<f[20][20]<<endl;
return 0;
}
二叉树的最大深度
一棵二叉树有2021个结点。该树满足任意结点的左子树结点个数和右子树的结点个数之差最多为1。
定义根结点的深度为0，子结点的深度比父结点深度多1。
请问，树中深度最大的结点的深度最大可能是多少？
#include <bits/stdc++.h>
using namespace std;
int main()
{
for(int i=0;i<31;i++)
{
if(pow(2,i)<=2021&&pow(2,i+1)>=2021)
{
cout<<i<<endl;
break;
}
}
return 0;
}
编程题
和尚挑水
#include <bits/stdc++.h>
using namespace std;
int a,t;
int main()
{
cin>>a>>t;
cout<<(int)ceil(t*1.0/a)<<endl;
return 0;
}
金融数字
在金融领域，通常将金额的百位和千位之间、十万位和百万位之间增加逗号（千分位分隔符），以方便阅读。一般从个位开始，每三位之前增加一个逗号。
例如：1234567890.00 通常写成 1,234,567,890.00。
注意小数点后固定保留 2 位。
给定一个包含千分位分隔符的数值，请读入后输出对应的不含千分位的数值，小数点仍然保留 2 位。
输入格式
输入一行包含一个由千分位分隔符的数值，恰好有 2 位小数。
输出格式
输出不含千分位分隔符的数值，保留 2 位小数。
样例输入
1,234,567,890.00
#include <bits/stdc++.h>
using namespace std;
int main()
{
string s;
cin>>s;
for(int i=0;i<s.size();i++)
{
if(s[i]!=',')
{
cout<<s[i];
}
}
return 0;
}
插座
问题描述
小蓝有一个插板，形状用一个 n * m 的01矩阵表示，0 表示板面，1 表示插孔。
小蓝还有一个插头，形状用一个 r * c 的01矩阵表示，0 表示没有伸出的部分，1 表示伸出的部分。插头伸出的部分必须插在插孔里面。
为了安全，插头插到面板上不能有任何部分超过插板边界（包括没有伸出的部分）。
插头和插板都不能旋转，也不能翻转。请求出插头插入插板的合理位置。
输入格式
输入的第一行包含两个整数 n, m。
接下来 n 行，每行一个长度为 m 的01串，表示插板的形状。
接下来一行包含两个整数 r, c。
接下来 r 行，每行一个长度为 c 的01串，表示插头的形状。
输出格式
如果插头没办法安全插入插板中，输出“NO”。否则输出两个数 a, b，表示插头的第 1 行第 1 列对应插板的第 a 行第 b 列。如果有多种情况满足要求，输出 a 最小的方案，如果 a 最小的方案有多个，输出在 a 最小的前提下 b 最小的方案。
样例输入
3 4
0110
0000
0000
3 3
000
010
000
样例输出
NO
样例说明
在插头不超出范围的前提下无法插入。
样例输入
4 7
1110100
1101111
0001111
0000011
2 3
111
011
样例输出
2 4
评测用例规模与约定
对于 50% 的评测用例，2 <= n, m, r, c <= 20。
对于所有评测用例，2 <= n, m, r, c <= 100。
#include <bits/stdc++.h>
using namespace std;
const int N=110;
char a[N][N],b[N][N];
int n,m,r,c;
bool check(int x,int y)
{
for(int i=0;i<r;i++)
{
for(int j=0;j<c;j++)
{
if(b[i][j]=='1'&&a[i+x][j+y]=='0')return false;
}
}
return true;
}
int main()
{
cin>>n>>m;
for(int i=0;i<n;i++)cin>>a[i];
cin>>r>>c;
for(int i=0;i<r;i++)cin>>b[i];
if(r>n||c>m)puts("NO");
for(int i=0;i<=n-r;i++)
{
for(int j=0;j<=m-c;j++)
{
if(a[i][j]=='1')
{
if(check(i,j))
{
cout<<i+1<<' '<<j+1<<endl;
return 0;
}
}
}
}
puts("NO");
return 0;
}
公约数
问题描述
给定正整数 a, b, c，请问有多少个正整数，是其中至少两个数的约数。
输入格式
输入一行包含三个正整数 a, b, c。
输出格式
输出一行包含一个整数，表示答案。
样例输入
30 70 35
样例输出
6
样例说明
1、2、5、7、10、35满足条件。
评测用例规模与约定
对于 50% 的评测用例，1 <= a, b, c <= 1000000。
对于所有评测用例，a, b, c 不超过 10**12（10的12次方）。
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
LL a,b,c;
map<LL,int>mp;
LL gcd(LL a,LL b)
{
return b?gcd(b,a%b):a;
}
void get_num(LL n)
{
for(LL i=1;i<=n/i;i++)
{
if(n%i==0)
{
mp[i]++;
if(i!=n/i)mp[n/i]++;
}
}
}
int main()
{
cin>>a>>b>>c;
LL x=gcd(a,b);
LL y=gcd(b,c);
LL z=gcd(a,c);
LL res=0;
get_num(x),get_num(y),get_num(z);
for(auto x:mp)
if(x.second>=1)
{
res++;
}
cout<<res<<endl;
}
|