信息学与信息学竞赛习题题解
信息学与信息学竞赛习题题解
本帖子会不断更新进度！~
1.新建代码模板
本次使用C++语言，新建一个代码模板，方便后续使用。在小熊猫工具-代码模板-C++中新建一个代码模板，内容如下：1
2
3
4
5
using namespace std;
int main(){
return 0;
}
如果是蓝桥杯，这里有一些小建议建议你加上：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
using namespace std;
void solve(){
//这里写你的代码
}
signed main(){//signed避免int被改为long long报错，也是int类的
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);//上面三行修改cin/cout速读速写
int t=1;
//cin>>t;
while(t--){
solve();//蓝桥杯一般是多个测试用例，这里建议你写一个solve函数
}
return 0;
}
2.题解
如果本篇没有的话拿可能就是没写或者已经剪切进归类了
1043：整数大小比较
查看本题
【题目描述】
输入两个整数，比较它们的大小。若x>y，输出>；若x=y，输出=；若x< y，输出<。
【输入】
一行，包含两个整数x和y，中间用单个空格隔开。0≤x<232, −231≤y<231。【输出】一个字符。若x>y，输出 >；若x=y，输出 = ；若x< y，输出< ；
【输入样例】1000 100
【输出样例】>1
2
3
4
5
6
7
8
9
10
11
12
13
14
using namespace std;
int main(void){
int x,y;
cin>>x>>y;
switch (x<y) {
case 0:
if(x==y)cout<<"=";
else cout<<">";
break;
case 1:cout<<"<";
}
}
1048：有一门课不及格的学生
查看本题
【题目描述】
给出一名学生的语文和数学成绩，判断他是否恰好有一门课不及格(成绩小于60分)。若该生恰好有一门课不及格，输出1；否则输出0。
【输入】
一行，包含两个在0到100之间的整数，分别是该生的语文成绩和数学成绩。
【输出】
若该生恰好有一门课不及格，输出1；否则输出0。
【输入样例】50 80
【输出样例】11
2
3
4
5
6
7
8
9
using namespace std;
int main(void){
int chi,math;
cin>>chi>>math;
if((chi<60)+(math<60)==1)cout<<1;
else cout<<0;
}
1077：统计满足条件的4位数
查看本题
【题目描述】
给定若干个四位数，求出其中满足以下条件的数的个数：个位数上的数字减去千位数上的数字，再减去百位数上的数字，再减去十位数上的数字的结果大于零。
【输入】
输入为两行，第一行为四位数的个数n，第二行为n个的四位数。(n<=100)
【输出】
输出为一行，包含一个整数，表示满足条件的四位数的个数。
【输入样例】1
25
1234 1349 6119 2123 5017
【输出样例】31
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
using namespace std;
int main(void){
int n,x,g,num=0;
cin>>n;
for(int i=1;i<=n;i++){
cin>>x;
g=x%10;
x/=10;
while(x){
g=g-x%10;
x/=10;
}
if(g>0)num++;
}
cout<<num;
}
1138：将字符串中的小写字母转换成大写字母
查看本题
题目详见1138：将字符串中的小写字母转换成大写字母
因为可能包含空格，所以我们需要输入getline(cin,s);代替cin>>s;1
2
3
4
5
6
7
8
9
10
11
12
13
14
using namespace std;
int main(){
string s;
getline(cin,s);
int n=s.size();
for(int i=0;i<n;i++){
if(islower(s[i])){
s[i]=toupper(s[i]);
}
}
cout<<s<<endl;
return 0;
}
或者按照传统方法；1
2
3
4
5
6
7
8
9
10
11
12
13
14
using namespace std;
int main(){
string s;
getline(cin,s);
int n=s.size();
for(int i=0;i<n;i++){
if(s[i]>='a'&&s[i]<='z'){
s[i]=s[i]-32;
}
}
cout<<s<<endl;
return 0;
}
1153：绝对素数
查看本题
【题目描述】
如果一个自然数是素数,且它的数字位置经过对换后仍为素数,则称为绝对素数,例如13。试求出所有二位绝对素数。
【输入】
（无）
【输出】
所有二位绝对素数（由小到大，一个数一行）。
【输入样例】
（无）
【输出样例】
（无）1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
using namespace std;
bool isprime(int x){
for(int i=2;i*i<=x;i++){
if(x%i==0)return false;
}
return true;
}
int main(void){
for(int i=11;i<=97;i++){
if(isprime(i)&&isprime(i%10*10+i/10)){
cout<<i<<endl;
}
}
}
1165：Hermite多项式
查看本题
用递归的方法求Hermite多项式的值，题目详见
1165：Hermite多项式1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
using namespace std;
int x;
double h(int n){
if(n==0)return 1;
if(n==1)return 2*x;
return 2*x*h(n-1)-2*(n-1)*h(n-2);
}
int main(void){
int n;
scanf("%d%d",&n,&x);
printf("%.2lf",h(n));
}
1166：求f(x,n)
查看本题
题目详见1166：求f(x,n)1
2
3
4
5
6
7
8
9
10
11
12
13
14
using namespace std;
double f(float x,int n){
if(n==1)return sqrt(1+x);
else return sqrt(n+f(x,n-1));
}
int main(void){
double x,n;
cin>>x>>n;
printf("%.2lf",f(x,n));
}
1167：再求f(x,n)
查看本题
题目详见1167：再求f(x,n)1
2
3
4
5
6
7
8
9
10
11
12
13
14
using namespace std;
double f(float x,int n){
if(n==1)return x/(1+x);
else return x/(n+f(x,n-1));
}
int main(void){
int x,n;
cin>>x>>n;
printf("%.2lf",f(x,n));
}
1177：奇数单增序列
查看本题
题目详见1177：奇数单增序列1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
using namespace std;
int a[509],x,m;
int main()
{
int n;cin>>n;
for(int i=1;i<=n;i++){
cin>>x;
if(x%2==1)a[++m]=x;
}
sort(a,a+1+m);
for(int i=1;i<=m;i++)cout<<a[i]<<", "[i==m];
return 0;
}
1178：成绩排序
查看本题
题目详见1178：成绩排序1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
using namespace std;
struct stu{
string name;
int score;
}a[21];
int n;
int main()
{
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
cin>>n;
for(int i=1;i<=n;i++)cin>>a[i].name>>a[i].score;
sort(a+1,a+1+n,[](stu x,stu y){
if(x.score==y.score) return x.name<y.name;
else return x.score>y.score;
});
for(int i=1;i<=n;i++)cout<<a[i].name<<" "<<a[i].score<<'\n';
return 0;
}
1181：整数奇偶排序
查看本题
题目详见1181：整数奇偶排序1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
using namespace std;
int a[20],b[20],x,m,n;
int main()
{
for(int i=1;i<=10;i++){
cin>>x;
if(x%2==1)a[++m]=x;
else b[++n]=x;
}
sort(a+1,a+1+m,[](const int u,const int v){
return u>v;
});
sort(b+1,b+1+n);
for(int i=1;i<=m;i++)cout<<a[i]<<" ";
for(int i=1;i<=n;i++)cout<<b[i]<<" ";
return 0;
}
1184：明明的随机数
查看本题
题目详见1184：明明的随机数1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
using namespace std;
int a[1010],n,m,x;
int main()
{
cin>>n;
for(int i=1;i<=n;i++){
cin>>x;
if(a[x]==0)m++;
a[x]++;
}
cout<<m<<endl;
for(int i=1;i<=1000;i++){
if(a[i]){//while如果要全部输出的话
cout<<i<<" ";
// a[i]--;
}
}
return 0;
}
1188：菲波那契数列(2)
查看本题
题目详见1188：菲波那契数列(2)1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
using namespace std;
int b[1000001]; //提前计算出数列每一项的值 （这里本地会报错，但是OJ上不会）
int main() {
int n;
cin>>n;
int a[n];
for(int i=0; i<n; i++) {
cin>>a[i];
}
b[0]=1;
b[1]=1;
//计算数列
for(int i=2; i<=1000000; i++) {
b[i]=(b[i-1]+b[i-2])%1000;//利用高精度思想，每次计算后都取模
}
for(int i=0; i<n; i++) {
cout<<b[a[i]-1]<<endl;//输出第i位的值，由于数列下标从0开始，要减1
}
}
1189：Pell数列
查看本题
题目详见1189：Pell数列1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
using namespace std;
int a[1000005];//这里本地会报错，但是OJ上不会
int main()
{
int n, x;
a[1] = 1, a[2] = 2;
for(int i = 3; i <= 1000000; ++i)
a[i] = (2*a[i-1] + a[i-2])%32767;
cin >> n;
for(int i = 1; i <= n; ++i)
{
cin >> x;
cout << a[x] << endl;
}
return 0;
}
1190：上台阶
查看本题
题目详见1190：上台阶1
2
3
4
5
6
7
8
9
10
11
12
13
14
using namespace std;
long long f[81],n;
int main(void){
f[1]=1;f[2]=2;f[3]=4;
for(int i=4;i<=70;i++)
f[i]=f[i-1]+f[i-2]+f[i-3];
cin>>n;
while(n){
cout<<f[n]<<endl;
cin>>n;
}
return 0;
}
1200：分解因数
查看本题
题目详见1200：分解因数1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
using namespace std;
int tot;
void f(int n, int m){
if(n==1){
tot++;
return;
}
for(int i=m;i<=n;i++)
if(n%i==0)f(n/i,i);
}
int main(){
int n,a;
cin>>n;
for(int i=1;i<=n;i++){
tot=0;
cin>>a;
f(a,2);
cout<<tot<<endl;
}
return 0;
}
1205：汉诺塔问题
查看本题
题目详见1205：汉诺塔问题
主题cin/cout会超时，尽管取消同步流也超时（ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);），所以只能用scanf/printf1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
using namespace std;
void hanoi(int n, char a, char b, char c){
if(n==0)return;
hanoi(n-1,a,c,b);
printf("%c->%d->%c\n",a,n,b);
hanoi(n-1,c,b,a);
}
int main(){
int n;
char a,b,c;
scanf("%d %c %c %c",&n,&a,&b,&c);
hanoi(n,a,b,c);
return 0;
}
1207：求最大公约数问题
查看本题
题目详见1207：求最大公约数问题1
2
3
4
5
6
7
8
9
10
11
using namespace std;
int gcd(int m,int n){
return n==0?m:gcd(n,m%n);
}
int main(){
int m,n;
cin>>m>>n;
cout<<gcd(m,n);
return 0;
}
1222：放苹果
查看本题
题目详见1222：放苹果1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
using namespace std;
int m,n,K;
void dfs(int p,int a,int l){
if(p==n&&a==m){
K++;
return;
}
if(p==n || a>m)return;
for(int i=l;i<=m;i++)
dfs(p+1,a+i,i);
}
int main(){
int t;
cin>>t;
while(t--){
K=0;
cin>>m>>n;
dfs(0,0,0);
cout<<K<<endl;
}
return 0;
}
1310：【例2.2】车厢重组
查看本题
题目详见1310：【例2.2】车厢重组1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
using namespace std;
int a[10010],n,num;
int main()
{
cin>>n;
for(int i=1;i<=n;i++)cin>>a[i];
for(int i=1;i<=n-1;i++)//冒泡排序
for(int j=1;j<=n-i;j++)
if(a[j]>a[j+1]){
swap(a[j],a[j+1]);
num++;
}
cout<<num;
return 0;
}
1315：【例4.5】集合的划分
查看本题
题目详见1315：【例4.5】集合的划分1
2
3
4
5
6
7
8
9
10
11
12
13
using namespace std;
long long s(int n,int k){
if(n<k||k==0)return 0;
if(n==k||k==1)return 1;
return s(n-1,k-1)+k*s(n-1,k);
}
int main(){
int n,k;
cin>>n>>k;
cout<<s(n,k)<<endl;
return 0;
}
1317：【例5.2】组合的输出
查看本题
题目详见1317：【例5.2】组合的输出1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
using namespace std;
int n,r,a[25],f[25];
void print(){
for(int i=1;i<=r;i++){
cout<<setw(3)<<a[i];
}
cout<<endl;
}
void dfs(int k){
for(int i=a[k-1]+1;i<=n;i++){
if(!f[i]){
a[k]=i;f[i]=1;
if(k==r)print();
else dfs(k+1);
f[i]=0;
}
}
}
int main(){
cin>>n>>r;
dfs(1);
return 0;
}
1318：【例5.3】自然数的拆分
查看本题
题目详见1318：【例5.3】自然数的拆分1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
using namespace std;
const int N=1e5+9;
int n,a[N],tot;
void print(int k){
cout<<n<<"="<<a[1];
for(int i=2;i<=k;i++){
cout<<"+"<<a[i];
}
// tot++;
cout<<endl;
}
void dfs(int k,int s){
for(int i=a[k-1];i<=s;i++){
if(i<n){
a[k]=i;s-=i;
if(s==0)print(k);
else dfs(k+1,s);
s+=i;
}
}
}
int main(){
cin>>n;
a[0]=1;
dfs(1,n);
// cout<<"total="<<tot;
return 0;
}
2048：【例5.18】串排序
查看本题
题目详见2048：【例5.18】串排序1
2
3
4
5
6
7
8
9
10
using namespace std;
int main(){
int n;cin>>n;
string s[21];
for(int i=0;i<n;i++)cin>>s[i];
sort(s,s+n);
for(int j=0;j<n;j++)cout<<s[j]<<endl;
return 0;
}
2059：【例3.11】买笔
查看本题
【题目描述】
期末来临了，班长小Q决定将剩余班费x元钱，用于购买若干支钢笔奖励给一些学习好、表现好的同学。已商店里有三种钢笔，它们的单价为6元、5元和4元。小Q想买尽量多的笔（鼓励尽量多的同学），同时他又不想有剩余钱。请您编一程序，帮小Q制订出一种买笔的方案。
【输入】
一个正整数x（剩余班费）。
【输出】
一行，依次为6元、5元和4元钱笔的数目，用一个空格隔开。
【输入样例】10
【输出样例】1 0 11
2
3
4
5
6
7
8
9
10
11
12
13
14
using namespace std;
int x,n6,n5,n4;
int main(void){
cin>>x;
n4=x/4;
switch (x%4) {
case 1:n4--;n5++;break;
case 2:n4--;n6++;break;
case 3:n4-=2;n5++;n6++;
}
cout<<n6<<" "<<n5<<" "<<n4;
}