前言
- 环境:Dev c++
- 万能头文件: #include<bits/stdc++.h>
- 水平不高,不喜勿喷,有问题可以评论区告诉我,谢谢
基础练习
BASIC-01 A+B问题
解题思路
AC代码
#include<bits/stdc++.h>
using namespace std;
int main() {
int a,b;
cin>>a>>b;
cout<<a+b;
return 0;
}
BASIC-02 序列求和
解题思路
AC代码
#include<bits/stdc++.h>
using namespace std;
int main() {
long long n;
cin>>n;
cout<<(1+n)*n/2;
return 0;
}
BASIC-03 圆的面积
解题思路
- 利用圆的面积公式
- pi需要定义,这里使用的是acos(-1.0)
- 注意输出格式
AC代码
#include<bits/stdc++.h>
#define pi acos(-1.0)
using namespace std;
int main() {
int r;
cin>>r;
double s=r*r*pi;
printf("%.7lf",s);
return 0;
}
BASIC-04 Fibonacci数列
解题思路
- 斐波那契数列
- 直接递归的方法超时了,就用数组存了一下
- 不用求出结果再取模,直接取模
AC代码
#include<bits/stdc++.h>
using namespace std;
long long a[1000050];
int main( )
{
int n;
cin>>n;
a[1]=a[2]=1;
for(int i=3;i<=n;i++)
{
a[i]=(a[i-1]+a[i-2])%10007;
}
cout<<a[n];
}
BASIC-1 闰年判断
解题思路
AC代码
#include<bits/stdc++.h>
using namespace std;
int main( )
{
int y;
cin>>y;
if((y%4==0&&y%100!=0)||y%400==0)
cout<<"yes";
else
cout<<"no";
return 0;
}
BASIC-2 01字串
解题思路
- 抱着好玩的想法,我将32个情况一一输出了,结果居然通过了??这也是没有办法的办法,代码就不贴了,就无脑输出就行了
- 我的方法是0-31一共32个数,想办法用二进制表示,
AC代码
#include<bits/stdc++.h>
using namespace std;
int main( )
{
for(int i=0;i<=31;i++)
{
int j=i;
cout<<j/16; //第一位表示有几个16
j%=16;
cout<<j/8; //对16取模后有几个8
j%=8;
cout<<j/4; //对8取模后有几个4
j%=4;
cout<<j/2; //对4取模后有几个2
j%=2;
cout<<j; //对2取模有几个1(即本身)
cout<<endl;
}
return 0;
}
BASIC-3 字母图形
解题思路
- 跟上题一样,如果实在没有方法,可以定义a[26][26]将完整的表输进去,然后再输出n行m列
- 先将对角线全赋值为A,再向左向右进行赋值
AC代码
#include<bits/stdc++.h>
using namespace std;
char a[27][27];
int main( )
{
int n,m;
cin>>n>>m;
for(int i=0;i<26;i++) //输入完整的表
{
a[i][i]='A';
for(int j=0;j<26-i;j++)
a[i][i+j]='A'+j;
for(int k=0;k<=i;k++)
a[i][i-k]='A'+k;
}
for(int i=0;i<n;i++) //输出n行m列
{
for(int j=0;j<m;j++)
{
cout<<a[i][j];
}
cout<<endl;
}
return 0;
}
BASIC-4 数列特征
解题思路
- 先把数存进数组
- 简单的最大最小值比较再赋值还有sum求和,注意maxm的初值要设的小于-10000,一开始我设的0没能过
AC代码
#include<bits/stdc++.h>
using namespace std;
int a[10050];
int main( )
{
int n;
cin>>n;
for(int i=0;i<n;i++)
{
cin>>a[i];
}
int maxm=-10010;
int minm=10010;
int sum=0;
for(int i=0;i<n;i++)
{
if(maxm<=a[i])
maxm=a[i];
if(minm>=a[i])
minm=a[i];
sum+=a[i];
}
cout<<maxm<<endl<<minm<<endl<<sum;
return 0;
}
BASIC-5 查找整数
解题思路
AC代码
#include<bits/stdc++.h>
using namespace std;
int a[1050];
int main( )
{
int n,m;
cin>>n;
for(int i=0;i<n;i++)
cin>>a[i];
cin>>m;
for(int i=0;i<n;i++)
{
if(a[i]==m)
{
cout<<i+1; //下标加一代表是第几个数,因为下标从0开始
return 0;
}
}
cout<<-1;
return 0;
}
BASIC-6 杨辉三角形
解题思路
AC代码
#include<bits/stdc++.h>
using namespace std;
int a[34][34];
int main( )
{
int n;
cin>>n;
for(int i=0;i<n;i++)
{
a[i][i]=1; //左对角线全赋为1
a[i][0]=1; //第一列全赋为1
}
for(int i=2;i<n;i++)
{
for(int j=1;j<i+1;j++)
a[i][j]=a[i-1][j-1]+a[i-1][j];//从a[2][1]开始遍历赋值,每个等于肩上的两数之和
}
for(int i=0;i<n;i++)
{
for(int j=0;j<i+1;j++) //这边的输出方法有点小讲究,我也不知道每行后面多个空格会不会错,但是这样写肯定没错
{
if(j==0)
cout<<a[i][j];
else
cout<<' '<<a[i][j];
}
cout<<endl;
}
return 0;
}
BASIC-7 特殊的数字
解题思路
AC代码
#include<bits/stdc++.h>
using namespace std;
int main( )
{
for(int i=100;i<=999;i++)
{
int n,a,sum=0;
n=i;
while(n)
{
a=n%10; //第一次循环a是个位的数字,第二次循环是十位的数字,第三次是百位的数字
n/=10;
sum+=pow(a,3);
}
if(sum==i)
cout<<i<<endl;
}
return 0;
}
BASIC-8 回文数
解题思路
- 一样通过剥离法,将每一位剥下来再乘10相加进行判断
AC代码
#include<bits/stdc++.h>
using namespace std;
int main( )
{
for(int i=1000;i<10000;i++)
{
int n,a,sum=0;
n=i;
while(n)
{
a=n%10;
n/=10;
sum*=10;
sum+=a;
}
if(i==sum)
cout<<i<<endl;
}
return 0;
}
BASIC-9 特殊回文数
解题思路
- 与上题类似,但还需要将剥离下来的数字进行相加求和,需要两个判断同时为true
AC代码
#include<bits/stdc++.h>
using namespace std;
int main( )
{
int m;
cin>>m;
for(int i=10000;i<1000000;i++)
{
int n,a,sum1=0,sum2=0;
n=i;
while(n)
{
a=n%10; //剥离个位
n/=10; //自身除10
sum1*=10;
sum1+=a; //sum1求翻转的数字
sum2+=a; //sum2求各位上数字之和
}
if(sum1==i && sum2==m)
cout<<i<<endl;
}
return 0;
}
BASIC-10 十进制转十六进制
解题思路
- 了解进制转化的方法,详情见代码注释
- 这种题不难但是麻烦,需要不断地进行修正调试
AC代码
#include<bits/stdc++.h>
using namespace std;
int main( )
{ long long n; //注意数据范围
cin>>n;
int i=0,j=0,k,r;
char ans[10];
if(n==0)
cout<<'0';
else
{ while(n) //这个循环是将十进制从后向前转为十六进制,最后需要倒序输出
{
r=n%16; //对16取模
if(r<10) //转为十六进制
ans[i++]=char(r+'0');
else
ans[i++]=char(r-10+'A');
n/=16; //n自身除16
}
}
for(k=i-1;k>=0;k--)
cout<<ans[k]; //倒序输出
return 0;
}
BASIC-11 十六进制转十进制
解题思路
- 以FFFF为例,第一次sum为15,第二次为1516+15,第三次为(1516+15)16+15,第四次为((1516+15)16+15)16+15,即15163+15*162+15161+15*160
AC代码
#include<bits/stdc++.h>
using namespace std;
int main( )
{
char a[8];
cin>>a;
long long sum=0;
for(int i=0;i<strlen(a);i++)
{
if(a[i]>='0' && a[i]<='9')
sum=sum*16+(int)(a[i]-'0');
else
sum=sum*16+(int)(a[i]-'A'+10);
}
cout<<sum;
return 0;
}
BASIC-12 十六进制转八进制
解题思路
AC代码
#include<bits/stdc++.h>
using namespace std;
string _16_2_(string str)
{
string a="";
for(int i=0;i<str.size();i++)
{
switch(str[i]) //将十六进制转为四位四位的二进制
{
case '0': a+= "0000"; break;
case '1': a+= "0001"; break;
case '2': a+= "0010"; break;
case '3': a+= "0011"; break;
case '4': a+= "0100"; break;
case '5': a+= "0101"; break;
case '6': a+= "0110"; break;
case '7': a+= "0111"; break;
case '8': a+= "1000"; break;
case '9': a+= "1001"; break;
case 'A': a+= "1010"; break;
case 'B': a+= "1011"; break;
case 'C': a+= "1100"; break;
case 'D': a+= "1101"; break;
case 'E': a+= "1110"; break;
case 'F': a+= "1111"; break;
default: break;
}
}
return a;
}
string _2_8(string str) //再将二进制转为八进制,注意要进行补0,将二进制补为3的整数倍
{
string a;
switch(str.size()%3)
{
case 0:break;
case 1:str="00"+str;break;
case 2:str="0"+str;break;
default:break;
}
for(int i=0;i<str.size();i+=3)
{
int m=(str[i]-'0')*4+(str[i+1]-'0')*2+(str[i+2]-'0');
a+=(m+'0');
}
return a;
}
int main( )
{
int n;
cin>>n;
string s;
while(n--)
{
cin>>s;
string a=_16_2_(s); //先转为二进制
string b=_2_8(a); //再转为八进制
int k=b.size();
int p=0;
while(b[p]=='0') p++; //题目中要求输出时前面不需要带0所以从不是0的时候开始
for(int i=p;i<k;i++) cout<<b[i];
if(n>=1) cout<<endl; //这一行必不可少,少输出换行就是错的的
}
return 0;
}
BASIC-13 数列排序
解题思路
- 方法一:利用c++的函数库sort进行排序
- 方法二:简单的排序算法,我这里写的是选择排序,还有很多种排序法
AC代码
#include<bits/stdc++.h>
using namespace std;
int main( )
{
int n;
cin>>n;
int a[250];
for(int i=0;i<n;i++)
cin>>a[i];
for(int i=0;i<n;i++)
{
for(int j=i+1;j<n;j++)
{
if(a[i]>a[j])
{
int temp=a[j];
a[j]=a[i];
a[i]=temp;
}
}
}
for(int i=0;i<n;i++)
{
if(i==0)
cout<<a[i];
else
cout<<' '<<a[i];
}
return 0;
}
至此非VIP的习题部分已经完毕
以下为VIP习题部分
BASIC-14 时间转换
解题思路
AC代码
#include<bits/stdc++.h>
using namespace std;
int main( )
{
int t;
cin>>t;
int h,m,s;
h = t / 3600; // 总分钟除3600==小时数
m = (t % 3600)/60; // 余数部分除60==分钟数
s = ( (t % 3600) % 60); // 余数部分除60==秒数
cout<<h<<':'<<m<<':'<<s<<endl;
return 0;
}
BASIC-15 字符串对比
解题思路
AC代码
#include<bits/stdc++.h>
#include<string.h>
using namespace std;
string f(string a) //将字符串全部转为大写
{
for(int i=0; i < a.size(); i++)
{
if(islower(a[i]))
a[i]=a[i]-32;
}
return a;
}
string a,b,A,B;
int main( )
{
cin>>a>>b;
A=f(a); //转大写
B=f(b); //转大写
if(a.length()!=b.length()) //长度不相等
cout<<'1'<<endl;
else if(a.compare(b)==0) //原字符串相等
cout<<'2'<<endl;
else if(A.compare(B)==0) //原字符串不相等,但不区分大小写时相等。即统一大小写后比较
cout<<'3'<<endl;
else //其他
cout<<'4'<<endl;
return 0;
}
BASIC-16 分解质因数
解题思路
- 遍历,判断是否素数,是素数输出本身
- 若不是素数,则进行自身整除素数(从小到大)
AC代码
#include<bits/stdc++.h>
using namespace std;
int a,b;
int isprime(int a) //判断是否素数
{
if(a==1 || a==2)
return 1;
for(int i=2;i<=sqrt(a);i++)
if(a%i==0)
return 0;
return 1;
}
int main( )
{
cin>>a>>b;
for(int i=a;i<=b;i++)
{
if(isprime(i)==1) //本身为素数
cout<<i<<'='<<i<<endl;
else
{
cout<<i<<'=';
int t=i;
for(int j=2;j<=t;j++) //枚举可能的因数
{
if(isprime(j)==1 && t%j==0) //因数是素数,且可以被整除
{
if(t==i) //注意输出的格式
cout<<j;
else
cout<<'*'<<j;
t/=j; //自身除以该因数后继续判断
j--; //需要自减,质因数可能相同如:8=2*2*2
}
}
cout<<endl;
}
}
return 0;
}
BASIC-17 矩阵乘法
解题思路
AC代码
#include<bits/stdc++.h>
using namespace std;
int main()
{
int N,M,i,j,k,t=1;//N是N阶矩阵,M是M次幂,i,j,k,t都是计数
scanf("%d%d",&N,&M);
int A[N][N],F[N][N],B[N][N];
for(i=0;i<N;i++)
{
for(j=0;j<N;j++)
{
scanf("%d",&A[i][j]);//给A矩阵赋值
B[i][j]=A[i][j];//让B矩阵和A矩阵相同
F[i][j]=0;
}
}
//注意:要对 M 的值讨论; M=0, M=1, M!=0&&M!=1; 这三种情况讨论
if(M==0)//对 M=0 的讨论
{
for(i=0;i<N;i++)
{
F[i][i]=1;
}
}
if(M==1)//对 M=1 的讨论
{
for(i=0;i<N;i++)
{
for(j=0;j<N;j++)
{
F[i][j]=A[i][j];
}
}
}
while(t<M)//对 M!=0&&M!=1 的讨论
{
for(i=0;i<N;i++)
{
for(j=0;j<N;j++)
{
F[i][j]=0;
for(k=0;k<N;k++)
{
F[i][j]+=A[i][k]*B[k][j];//此处用了矩阵乘法的规律
}
}
}//此处是A矩阵的平方,即是A*A;
for(i=0;i<N;i++)
{
for(j=0;j<N;j++)
{
B[i][j]=F[i][j];
}
}//此处是为更高次幂准备,即 A*A*A=F*A,但为了使用上面的规律,故F=B,使得:A*A*A=A*B
t++;//为了记住乘了几次
}
for(i=0;i<N;i++)
{
for(j=0;j<N;j++)
{
printf("%d ",F[i][j]);
}
printf("\n");
}//此处输出值
return 0;
}
BASIC-18 矩形面积交
解题思路
- 要求两个矩形的面积交集,只需要知道下方矩形的右上顶点 和上方矩形的左下顶点即可
AC代码
#include<bits/stdc++.h>
using namespace std;
int main()
{
double x1,y1,x2,y2,x3,y3,x4,y4;
cin>>x1>>y1>>x2>>y2>>x3>>y3>>x4>>y4;
double a1,a2,b1,b2;
a1=max(min(x1,x2),min(x3,x4));
a2=max(min(y1,y2),min(y3,y4));
b1=min(max(x1,x2),max(x3,x4));
b2=min(max(y1,y2),max(y3,y4));
if(b1 > a1 && b2 > a2) //判断是否有交集
printf("%.2f",(b1-a1)*(b2-a2));
else printf("0.00");
return 0;
}
BASIC-19 完美的代价
解题思路
AC代码
BASIC-20 数的读法
解题思路
AC代码
#include<bits/stdc++.h>
using namespace std;
int main()
{
char a[100];
int i,j,k,l;
char b[20][10]={"ling","yi","er","san","si","wu","liu","qi","ba","jiu"};
char c[20][10]={"","","shi","bai","qian","wan","shi","bai","qian","yi","shi"};
gets(a);
l=strlen(a); //取长度
for(i=0;i<l;i++){
j=a[i]-48;
if(j==0)
{
if(i<l-1 && a[i+1]!=48)
printf("%s ",b[j]);
}
else
if((l-i==2||l-i==6||l-i==10) && j==1)
printf("%s ",c[l-i]);
else if(a[i-1]==48 && j==1)
printf("%s ",c[l-i]);
else
printf("%s %s ",b[j],c[l-i]);
}
printf("\n");
return 0;
}
BASIC-21 Sine之舞
解题思路
- 直接根据规律进行输出
- A1=sin(1) A2=sin(1-sin(2))
- S1=A1+1=sin(1)+1 S2=(A1+2)A2+1=(sin(1)+2)sin(1-sin(2))+1
AC代码
#include<bits/stdc++.h>
using namespace std;
int n;
void A(int n) //求A
{
for(int i=1;i<=n;i++)
{
cout<<"sin("<<i;
if(i%2==0 && i!=n) //正负号交替
cout<<'+';
else if(i!=n)
cout<<'-';
}
for(int i=1; i<=n; i++)
{
cout<<")";
}
}
void S(int n) //求S
{
int i;
for(i=1;i<n;i++)
{
cout<<"(";
}
for(i=1;i<n;i++)
{
A(i);
cout<<"+"<<n-i+1<<")";
}
A(i);
cout<<"+"<<'1'<<endl;
}
int main( )
{
cin>>n;
S(n);
return 0;
}
BASIC-22 FJ的字符串
解题思路
AC代码
#include<bits/stdc++.h>
using namespace std;
int n;
int main( )
{
cin>>n;
string a="";
for(int i=1;i<=n;i++)
{
char b='A'+i-1;
a=a+b+a; //每次只改变中间的b值
}
cout<<a;
}
BASIC-23 芯片测试
解题思路
- 假设好芯片为m个,坏芯片为n个,由于坏芯片测试其他芯片的结果是随机的,则若一个芯片是好芯片,他的所有评测结果中满足:m<= 1的个数 <=m+n
- 即当一个芯片评测结果中1的个数大于0的个数时,该芯片为好芯片
- 即计算每一列中1和0的个数进行比较
AC代码
#include<bits/stdc++.h>
using namespace std;
const int N=25;
int n;
int g[N][N];
int main( )
{
cin>>n;
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
cin>>g[i][j];
int j=1,count=0;
while(j<=n)
{
int sum1=0,sum2=0; //sum1为1的数量,sum2为0的数量
for(int i=1;i<=n;i++)
{
if(g[i][j]==1)
sum1++;
else
sum2++;
}
if(sum1>sum2)
{
count++;
if(count==1)
cout<<j;
else
cout<<' '<<j;
}
j++;
}
return 0;
}
BASIC-24 龟兔赛跑预测
解题思路
- 乌龟跑完的时间是固定的,模拟兔子的时间然后进行比较
AC代码
#include<bits/stdc++.h>
using namespace std;
int v1,v2,t,s,l;
int main( )
{
cin>>v1>>v2>>t>>s>>l;
int T=l/v2; //乌龟跑的时间T为固定值
int sum1=0,sum2=0;
int ans=0;
while(1)
{
if(sum1==l) //兔子跑完
break;
sum1+=v1; //兔子跑的长度
sum2+=v2; //乌龟跑的长度
ans++; //ans为时间
if(sum1-sum2>=t && sum1!=l) //兔子超过乌龟t米
{
ans+=s; //兔子休息s秒
sum2+= v2*s; //乌龟跑s秒的距离
}
}
if(ans>T)
cout<<'T'<<endl<<T;
else if (ans < T)
cout<<'R'<<endl<<ans;
else
cout<<'D'<<endl<<T;
return 0;
}
BASIC-25 回形取数
解题思路
- 一个数组g进行取数,一个数组st进行标记,对取过数的位置进行标记
AC代码
#include<bits/stdc++.h>
using namespace std;
const int N=210;
int n,m;
int g[N][N];
bool st[N][N]={false};
int main( )
{
cin>>n>>m;
for(int i=0;i<n;i++)
for(int j=0;j<m;j++)
{
cin>>g[i][j];
st[i][j]=true;
}
int t=1;
int i=0,j=0;
cout<<g[0][0]; //[0][0]单独拉出来
st[0][0]=false;
while(t < n*m) //t为取数的总次数
{
while(i+1<n && st[i+1][j]) //用四个while循环进行蛇形取数
{
cout<<' '<<g[++i][j];
st[i][j]=false;
t++;
}
while(j+1<m && st[i][j+1])
{
cout<<' '<<g[i][++j];
st[i][j]=false;
t++;
}
while(i-1>=0 && st[i-1][j])
{
cout<<' '<<g[--i][j];
st[i][j]=false;
t++;
}
while(j-1>=0 && st[i][j-1])
{
cout<<' '<<g[i][--j];
st[i][j]=false;
t++;
}
}
return 0;
}
BASIC-26 报时助手
解题思路
AC代码
#include<bits/stdc++.h>
using namespace std;
int h,m;
void f(int n)
{
switch(n)
{
case 0:cout<<"zero";break;
case 1:cout<<"one";break;
case 2:cout<<"two";break;
case 3:cout<<"three";break;
case 4:cout<<"four";break;
case 5:cout<<"five";break;
case 6:cout<<"six";break;
case 7:cout<<"seven";break;
case 8:cout<<"eight";break;
case 9:cout<<"nine";break;
case 10:cout<<"ten";break;
case 11:cout<<"eleven";break;
case 12:cout<<"twelve";break;
case 13:cout<<"thirteen";break;
case 14:cout<<"fourteen";break;
case 15:cout<<"fifteen";break;
case 16:cout<<"sixteen";break;
case 17:cout<<"seventeen";break;
case 18:cout<<"eighteen";break;
case 19:cout<<"nineteen";break;
case 20:cout<<"twenty";break;
case 30:cout<<"thirty";break;
case 40:cout<<"forty";break;
case 50:cout<<"fifty";break;
}
}
int main( )
{
cin>>h>>m;
if(m==0)
{
if(h<=20)
f(h);
else //当数字大于20时,进行分离
{
f(h-h%10); //整十部分
cout<<' ';
f(h%10); //去掉整十的部分
}
cout<<" o'clock";
}
else
{
if(h<=20)
f(h);
else
{
f(h-h%10);
cout<<' ';
f(h%10);
}
cout<<' ';
if(m<=20)
f(m);
else
{
f(m-m%10);
cout<<' ';
f(m%10);
}
}
return 0;
}
BASIC-27 2n皇后问题
解题思路
AC代码
BASIC-28 Huffuman树
解题思路
AC代码
BASIC-29 高精度加法
解题思路
AC代码
#include<bits/stdc++.h>
#include<vector>
using namespace std;
const int N = 1e6+10;
vector<int> add(vector<int> &A,vector<int> &B)
{
vector<int> C;
int t=0;
for(int i=0;i<A.size()||i<B.size();i++)
{
if(i<A.size()) t+=A[i];
if(i<B.size()) t+=B[i];
C.push_back(t%10);
t /=10;
}
if(t)
C.push_back(1);
return C;
}
int main()
{
string a,b;
vector<int>A,B;
cin>>a>>b;
for(int i=a.size()-1;i>=0;i--) A.push_back(a[i]-'0');
for(int i=b.size()-1;i>=0;i--) B.push_back(b[i]-'0');
vector<int>C =add(A,B);
for(int i=C.size()-1;i>=0;i--) printf("%d",C[i]);
return 0;
}
BASIC-30 阶乘计算
解题思路
AC代码
#include<bits/stdc++.h>
using namespace std;
const int N=1000000;
int n;
vector<int> mul(vector<int> &A,int b)
{
vector<int> C;
int t=0;
for(int i=0;i<A.size()||t;i++)
{
if(i<A.size()) t+=A[i]*b;
C.push_back(t%10);
t/=10;
}
return C;
}
int main( )
{
string a="1";
cin>>n;
vector<int> A;
for(int i=a.size()-1;i>=0;i--) A.push_back(a[i]-'0');
for(int i=1;i<=n;i++)
{
A=mul(A,i);
}
for(int i=A.size()-1;i>=0;i--)
printf("%d",A[i]);
return 0;
}