普通题
BASIC-1 闰年判断
问题描述
-
资源限制
时间限制：1.0s 内存限制：256.0MB -
问题描述
给定一个年份，判断这一年是不是闰年。
当以下情况之一满足时，这一年是闰年：
1. 年份是4的倍数而不是100的倍数；
2. 年份是400的倍数。
其他的年份都不是闰年。 -
输入格式
输入包含一个整数y，表示当前的年份。 -
输出格式
输出一行，如果给定的年份是闰年，则输出yes，否则输出no。
说明：当试题指定你输出一个字符串作为结果（比如本题的yes或者no，你需要严格按照试题中给定的大小写，写错大小写将不得分。 -
样例输入
2013 -
样例输出
no -
样例输入
2016 -
样例输出
yes -
数据规模与约定
1990 <= y <= 2050。
代码
#include<iostream>
using namespace std;
int main(int argc, char const *argv[])
{
int year;
cin >> year;
if ((year % 4 == 0 && year % 100 != 0) || year % 400 == 0)
cout << "yes";
else
cout << "no";
return 0;
}
BASIC-2 01字串
问题描述
-
资源限制
时间限制：1.0s 内存限制：256.0MB -
问题描述
对于长度为5位的一个01串，每一位都可能是0或1，一共有32种可能。它们的前几个是：
00000
00001
00010
00011
00100
请按从小到大的顺序输出这32种01串。 -
输入格式
本试题没有输入。 -
输出格式
输出32行，按从小到大的顺序每行一个长度为5的01串。 -
样例输出
00000
00001
00010
00011
<以下部分省略>
代码
#include<bits/stdc++.h>
using namespace std;
int main(int argc, char const *argv[])
{
for (int i = 0; i < 32; i++)
cout << bitset<5>(i) << endl; //打印二进制的数字，长度为5
return 0;
}
BASIC-3 字母图形
问题描述
-
资源限制
时间限制：1.0s 内存限制：256.0MB -
问题描述
利用字母可以组成一些美丽的图形，下面给出了一个例子：
ABCDEFG
BABCDEF
CBABCDE
DCBABCD
EDCBABC
这是一个5行7列的图形，请找出这个图形的规律，并输出一个n行m列的图形。 -
输入格式
输入一行，包含两个整数n和m，分别表示你要输出的图形的行数的列数。 -
输出格式
输出n行，每个m个字符，为你的图形。 -
样例输入
5 7 -
样例输出
ABCDEFG
BABCDEF
CBABCDE
DCBABCD
EDCBABC -
数据规模与约定
1 <= n, m <= 26。
代码
#include<bits/stdc++.h>
using namespace std;
int main(int argc, char const *argv[])
{
int n,m;
cin >> n >> m;
string arr="A";
for (int i = 1; i < m; i++)
arr += 'A'+i;
for (int i = 1; i < n; i++)
{
arr.erase(arr.end()-1); //删除string中最后一个元素
arr.insert(arr.begin(), 'A'+i); //在string头部加入一个元素
}
cout << arr;
return 0;
}
BASIC-4 数列特征
问题描述
-
资源限制
时间限制：1.0s 内存限制：256.0MB -
问题描述
给出n个数，找出这n个数的最大值，最小值，和。 -
输入格式
第一行为整数n，表示数的个数。
第二行有n个数，为给定的n个数，每个数的绝对值都小于10000。 -
输出格式
输出三行，每行一个整数。第一行表示这些数中的最大值，第二行表示这些数中的最小值，第三行表示这些数的和。 -
样例输入
5
1 3 -2 4 5 -
样例输出
5
-2
11 -
数据规模与约定
1 <= n <= 10000。
代码
#include <bits/stdc++.h>
using namespace std;
int main()
{
vector<int> arr;
arr.reserve(10010); //将arr的容量（capacity）扩充至10010(放大到最大数据量)
int num;
cin >> num;
for (int i = 0; i < num; i++)
cin >> arr[i];
cout << *max_element(arr.begin(), arr.begin()+num) << endl; //返回最大值
cout << *min_element(arr.begin(), arr.begin()+num) << endl; //返回最小值
cout << accumulate(arr.begin(), arr.begin()+num, 0); //求和，参数分别为，开始位置、结束位置、求和过程的初始值
return 0;
}
BASIC-5 查找整数
问题描述
-
资源限制
时间限制：1.0s 内存限制：256.0MB -
问题描述
给出一个包含n个整数的数列，问整数a在数列中的第一次出现是第几个。 -
输入格式
第一行包含一个整数n。
第二行包含n个非负整数，为给定的数列，数列中的每个数都不大于10000。
第三行包含一个整数a，为待查找的数。 -
输出格式
如果a在数列中出现了，输出它第一次出现的位置(位置从1开始编号)，否则输出-1。 -
样例输入
6
1 9 4 8 3 9
9 -
样例输出
2 -
数据规模与约定
1 <= n <= 1000。
代码
#include <bits/stdc++.h>
using namespace std;
int main()
{
vector<int> arr;
arr.reserve(1010);
int num, find_number;
cin >> num;
for (int i = 0; i < num; i++)
cin >> arr[i];
cin >> find_number;
//find用于查找容器中所查内容的位置，distance用于计算所查位置元素与开始位置的偏移
int result = distance(arr.begin(), find(arr.begin(), arr.end(), find_number));
//判断容器中是否有所查找到内容
if(result == num) cout << "-1";
else cout << result+1;
return 0;
}
BASIC-6 杨辉三角形
问题描述
-
资源限制
时间限制：1.0s 内存限制：256.0MB -
问题描述
杨辉三角形又称Pascal三角形，它的第i+1行是(a+b)i的展开式的系数。
它的一个重要性质是：三角形中的每个数字等于它两肩上的数字相加。
下面给出了杨辉三角形的前4行：1 1 1 1 2 1 1 3 3 1给出n，输出它的前n行。
-
输入格式
输入包含一个数n。 -
输出格式
输出杨辉三角形的前n行。每一行从这一行的第一个数开始依次输出，中间使用一个空格分隔。请不要在前面输出多余的空格。 -
样例输入
4 -
样例输出
1
1 1
1 2 1
1 3 3 1 -
数据规模与约定
1 <= n <= 34。
代码
#include<iostream>
using namespace std;
int main()
{
int arr[35][35] = {0};
int n;
cin >> n;
for (int i = 0; i < n; i++)
{
for(int j = 0; j < n; j++)
{
if(i==j || j==0)
{
arr[i][j] = 1;
cout << 1 << " ";
if(i==j)
{
cout << endl;
break;
}
continue;
}
arr[i][j] = arr[i-1][j] + arr[i-1][j-1];
cout << arr[i][j] << " ";
}
}
return 0;
}
BASIC-7 特殊的数字
问题描述
-
资源限制
时间限制：1.0s 内存限制：512.0MB -
问题描述
153是一个非常特殊的数，它等于它的每位数字的立方和，即153=111+555+333。编程求所有满足这种条件的三位十进制数。 -
输出格式
按从小到大的顺序输出满足条件的三位十进制数，每个数占一行。
代码
#include<iostream>
using namespace std;
int main()
{
int a, b, c;
for(int i = 111; i < 999; i++)
{
a = i/100;
b = (i/10)%10;
c = i%10;
if(i == a*a*a + b*b*b + c*c*c)
{
cout << i << endl;
}
}
return 0;
}
BASIC-8 回文数
问题描述
-
资源限制
时间限制：1.0s 内存限制：512.0MB -
问题描述
1221是一个非常特殊的数，它从左边读和从右边读是一样的，编程求所有这样的四位十进制数。 -
输出格式
按从小到大的顺序输出满足条件的四位十进制数。
代码
#include<iostream>
using namespace std;
int main()
{
for(int i = 1000; i <= 9999; i++)
{
if(i/1000 == i%10 && (i/100)%10 == (i/10)%10)
cout << i << endl;
}
return 0;
}
BASIC-9 特殊回文数
问题描述
-
资源限制
时间限制：1.0s 内存限制：512.0MB -
问题描述
123321是一个非常特殊的数，它从左边读和从右边读是一样的。
输入一个正整数n， 编程求所有这样的五位和六位十进制数，满足各位数字之和等于n 。 -
输入格式
输入一行，包含一个正整数n。 -
输出格式
按从小到大的顺序输出满足条件的整数，每个整数占一行。 -
样例输入
52 -
样例输出
899998
989989
998899 -
数据规模和约定
1<=n<=54。
代码
#include<iostream>
using namespace std;
int main()
{
int n;
cin >> n;
for(int i = 10000; i <= 999999; i++)
{
if(i<100000)
if(i/10000 == i%10 && (i/1000)%10 == (i/10)%10)
if(i/10000 + (i/1000)%10 + (i/100)%10 +(i/10)%10 + i%10 == n)
cout << i << endl;
if(i>=100000)
if(i/100000 == i%10 && (i/10000)%10 == (i/10)%10 && (i/1000)%10 == (i/100)%10)
if(i/100000+ (i/10000)%10 + (i/1000)%10 + (i/100)%10 + (i/10)%10 + i%10 == n)
cout << i << endl;
}
return 0;
}
BASIC-10 十进制转十六进制
问题描述
-
资源限制
时间限制：1.0s 内存限制：512.0MB -
问题描述
十六进制数是在程序设计时经常要使用到的一种整数的表示方式。它有0,1,2,3,4,5,6,7,8,9,A,B,C,D,E,F共16个符号，分别表示十进制数的0至15。十六进制的计数方法是满16进1，所以十进制数16在十六进制中是10，而十进制的17在十六进制中是11，以此类推，十进制的30在十六进制中是1E。
给出一个非负整数，将它表示成十六进制的形式。 -
输入格式
输入包含一个非负整数a，表示要转换的数。0<=a<=2147483647 -
输出格式
输出这个整数的16进制表示 -
样例输入
30 -
样例输出
1E
代码
#include<iostream>
using namespace std;
int main(int argc, char const *argv[])
{
int num;
string sixteen="";
cin >> num;
if(num==0)
{
cout << '0';
return 0;
}
while(num)
{
char x = num % 16;
if(x>=10)
x=x-10+'A';
else
x+='0';
sixteen = x+sixteen;
num /= 16;
}
cout << sixteen;
}
BASIC-11 十六进制转十进制
问题描述
-
资源限制
时间限制：1.0s 内存限制：512.0MB -
问题描述
从键盘输入一个不超过8位的正的十六进制数字符串，将它转换为正的十进制数后输出。
注：十六进制数中的10~15分别用大写的英文字母A、B、C、D、E、F表示。 -
样例输入
FFFF -
样例输出
65535
代码
#include<iostream>
#include<math.h>
using namespace std;
int main(int argc, char const *argv[])
{
long long int ten=0;
string sixteen;
cin >> sixteen;
string arr(sixteen.rbegin(), sixteen.rend());
for(int i=0; i<arr.length(); i++)
{
if(arr[i]<='9')
ten += pow(16,i) * (arr[i]-'0');
else if(arr[i]>='A')
ten += pow(16, i) * (arr[i]-'A'+10);
}
cout << ten;
}
BASIC-12 十六进制转八进制
问题描述
-
资源限制
时间限制：1.0s 内存限制：512.0MB -
问题描述
给定n个十六进制正整数，输出它们对应的八进制数。 -
输入格式
输入的第一行为一个正整数n （1<=n<=10）。
接下来n行，每行一个由0~9、大写字母A~F组成的字符串，表示要转换的十六进制正整数，每个十六进制数长度不超过100000。 -
输出格式
输出n行，每行为输入对应的八进制正整数。
【注意】
输入的十六进制数不会有前导0，比如012A。
输出的八进制数也不能有前导0。
- 样例输入
2
39
123ABC - 样例输出
71
4435274
【提示】
先将十六进制数转换成某进制数，再由某进制数转换成八进制。
代码
#include<iostream>
#include<string>
using namespace std;
int main(int argc, char const *argv[])
{
int a;
cin >> a;
for (int i = 0; i < a; i++)
{
string data, bin="", octal="";
cin >> data;
for(int i = 0; i < data.size(); i++)
{
switch(data[i])
{
case '0':bin+="0000";break;
case '1':bin+="0001";break;
case '2':bin+="0010";break;
case '3':bin+="0011";break;
case '4':bin+="0100";break;
case '5':bin+="0101";break;
case '6':bin+="0110";break;
case '7':bin+="0111";break;
case '8':bin+="1000";break;
case '9':bin+="1001";break;
case 'A':bin+="1010";break;
case 'B':bin+="1011";break;
case 'C':bin+="1100";break;
case 'D':bin+="1101";break;
case 'E':bin+="1110";break;
case 'F':bin+="1111";break;
default:break;
}
}
int len = bin.size();
if(len % 3 == 1)
{
bin = "00" + bin;
len += 2;
}
else if(len % 3 == 2)
{
bin = "0" + bin;
len += 1;
}
for(int i = 0; i < len; i+=3)
{
int d = (bin[i]-'0')*4 + (bin[i+1]-'0')*2 + (bin[i+2]-'0');
octal+=(d+'0');
}
int p = 0;
while(octal[p]=='0') p++;
for(; p < octal.size(); p++)
cout << octal[p];
cout << endl;
}
return 0;
}
BASIC-13 数列排序
问题描述
-
资源限制
时间限制：1.0s 内存限制：512.0MB -
问题描述
给定一个长度为n的数列，将这个数列按从小到大的顺序排列。1<=n<=200 -
输入格式
第一行为一个整数n。
第二行包含n个整数，为待排序的数，每个整数的绝对值小于10000。 -
输出格式
输出一行，按从小到大的顺序输出排序后的数列。 -
样例输入
5
8 3 6 4 9 -
样例输出
3 4 6 8 9
代码
#include<iostream>
using namespace std;
int main(int argc, char const *argv[])
{
int arr[205], num;
cin >> num;
for(int i=0; i<num; i++)
cin >> arr[i];
for(int i=0; i<num-1; i++)
for(int j=0; j<num-1; j++)
if(arr[j]>arr[j+1])
{
int temp=arr[j];
arr[j]=arr[j+1];
arr[j+1]=temp;
}
for(int i=0; i<num; i++)
cout << arr[i] << " ";
}
vip题目
{% note warning %}
Warning [BASIC-27] 待做
{% endnote %}
BASIC-14 时间转换
问题描述
- 资源限制
时间限制：1.0s 内存限制：512.0MB - 问题描述
给定一个以秒为单位的时间t，要求用“<H>:<M>:<S>”的格式来表示这个时间。<H>表示时间，<M>表示分钟，而<S>表示秒，它们都是整数且没有前导的“0”。例如，若t=0，则应输出是“0:0:0”；若t=3661，则输出“1:1:1”。 - 输入格式
输入只有一行，是一个整数t（0<=t<=86399）。 - 输出格式
输出只有一行，是以“<H>:<M>:<S>”的格式所表示的时间，不包括引号。 - 样例输入
0 - 样例输出
0:0:0 - 样例输入
5436 - 样例输出
1:30:36
代码
#include<iostream>
using namespace std;
int main(int argc, char const *argv[])
{
int sec;
cin >> sec;
cout << sec/3600 << ":";
sec = sec%3600;
cout << sec/60 << ":";
sec = sec%60;
cout << sec;
}
BASIC-15 字符串对比
问题描述
- 资源限制
时间限制：1.0s 内存限制：512.0MB - 问题描述
给定两个仅由大写字母或小写字母组成的字符串(长度介于1到10之间)，它们之间的关系是以下4中情况之一：
1、两个字符串长度不等。比如 Beijing 和 Hebei
2、两个字符串不仅长度相等，而且相应位置上的字符完全一致(区分大小写)，比如 Beijing 和 Beijing
3、两个字符串长度相等，相应位置上的字符仅在不区分大小写的前提下才能达到完全一致（也就是说，它并不满足情况2）。比如 beijing 和 BEIjing
4、两个字符串长度相等，但是即使是不区分大小写也不能使这两个字符串一致。比如 Beijing 和 Nanjing
编程判断输入的两个字符串之间的关系属于这四类中的哪一类，给出所属的类的编号。 - 输入格式
包括两行，每行都是一个字符串 - 输出格式
仅有一个数字，表明这两个字符串的关系编号 - 样例输入
BEIjing
beiJing - 样例输出
3
代码
#include<bits/stdc++.h>
using namespace std;
int main(int argc, char const *argv[])
{
string arr, brr;
cin >> arr >> brr;
if(arr.length()!=brr.length())
{
cout << '1';
return 0;
}
else
{
if(arr==brr)
{
cout << '2';
return 0;
}
else
{
transform(arr.begin(), arr.end(), arr.begin(), ::toupper);
transform(brr.begin(), brr.end(), brr.begin(), ::toupper);
if(arr==brr)
{
cout << '3';
return 0;
}
cout << '4';
return 0;
}
}
}
BASIC-16 分解质因数
问题描述
- 资源限制
时间限制：1.0s 内存限制：512.0MB - 问题描述
求出区间[a,b]中所有整数的质因数分解。 - 输入格式
输入两个整数a，b。 - 输出格式
每行输出一个数的分解，形如k=a1a2a3...(a1<=a2<=a3...，k也是从小到大的)(具体可看样例) - 样例输入
3 10 - 样例输出
3=3
4=22
5=5
6=23
7=7
8=222
9=33
10=25
提示
先筛出所有素数，然后再分解。 - 数据规模和约定
2<=a<=b<=10000
代码
#include<iostream>
using namespace std;
int main(int argc, char const *argv[])
{
int a, b;
int arr[10005] = {2}, num = 1;
cin >> a >> b;
for(int i = 3; i <= b; i++)
{
bool a1 = true;
for(int j = 0; j < num; j++)
{
if( i%arr[j] )
continue;
else
{
a1 = false;
break;
}
}
if(a1)
arr[num++] = i;
}
for(int i = a; i <= b; i++)
{
cout << i <<"=";
int x = i;
for(int j = 0; j < num;)
{
if( x%arr[j] == 0)
{
if(x/arr[j]==1)
{
cout << arr[j] << endl;
break;
}
else
{
cout << arr[j] << "*";
x = x/arr[j];
}
}
else
j++;
}
}
return 0;
}
BASIC-17 矩阵乘法
问题描述
- 资源限制
时间限制：1.0s 内存限制：512.0MB - 问题描述
给定一个N阶矩阵A，输出A的M次幂（M是非负整数）
例如：
A =
1 2
3 4
A的2次幂
7 10
15 22 - 输入格式
第一行是一个正整数N、M（1<=N<=30, 0<=M<=5），表示矩阵A的阶数和要求的幂数
接下来N行，每行N个绝对值不超过10的非负整数，描述矩阵A的值 - 输出格式
输出共N行，每行N个整数，表示A的M次幂所对应的矩阵。相邻的数之间用一个空格隔开 - 样例输入
2 2
1 2
3 4 - 样例输出
7 10
15 22
代码
#include <iostream>
#include <cstring>
using namespace std;
int main(int argc, char const *argv[])
{
long long int arr[32][32]={0};
long long int brr[32][32]={0};
long long int crr[32][32];
int n, m, num=1;
cin >> n >> m;
if(m == 0)
{
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
{
if(i == j)
cout << 1 << " ";
else
cout << 0 << " ";
}
cout << endl;
}
return 0;
}
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
cin >> arr[i][j];
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
{
brr[i][j] = arr[i][j];
}
}
while(num < m)
{
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
{
crr[i][j] = 0;
for (int k = 0; k < n; k++)
{
crr[i][j] += arr[i][k] * brr[k][j];
}
}
}
num++;
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
{
brr[i][j] = crr[i][j];
}
}
}
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
{
cout << brr[i][j] << " ";
}
cout << endl;
}
return 0;
}
BASIC-18 矩形面积交
问题描述
- 资源限制
时间限制：1.0s 内存限制：512.0MB - 问题描述
平面上有两个矩形，它们的边平行于直角坐标系的X轴或Y轴。对于每个矩形，我们给出它的一对相对顶点的坐标，请你编程算出两个矩形的交的面积。 - 输入格式
输入仅包含两行，每行描述一个矩形。
在每行中，给出矩形的一对相对顶点的坐标，每个点的坐标都用两个绝对值不超过10^7的实数表示。 - 输出格式
输出仅包含一个实数，为交的面积，保留到小数后两位。 - 样例输入
1 1 3 3
2 2 4 4 - 样例输出
1.00
代码
#include<iostream>
#include<iomanip>
#include<cmath>
using namespace std;
int main()
{
double x1, y1, x2, y2;
double x3, y3, x4, y4;
double m1, m2, n1, n2;
cin >> x1 >> y1 >> x2 >> y2 >> x3 >> y3 >> x4 >> y4;
m1 = min(max(x1,x2), max(x3,x4));
n1 = min(max(y1,y2), max(y3,y4));
m2 = max(min(x1,x2), min(x3,x4));
n2 = max(min(y1,y2), min(y3,y4));
if(m1>m2 && n1>n2)
{
cout << setiosflags(ios::fixed) << setprecision(2);
cout << (m1-m2)*(n1-n2) << endl;
}
else
cout << "0.00" << endl;
return 0;
}
BASIC-19 完美的代价
问题描述
- 资源限制
时间限制：1.0s 内存限制：512.0MB - 问题描述
回文串，是一种特殊的字符串，它从左往右读和从右往左读是一样的。小龙龙认为回文串才是完美的。现在给你一个串，它不一定是回文的，请你计算最少的交换次数使得该串变成一个完美的回文串。
交换的定义是：交换两个相邻的字符
例如mamad
第一次交换 ad : mamda
第二次交换 md : madma
第三次交换 ma : madam (回文！完美！) - 输入格式
第一行是一个整数N，表示接下来的字符串的长度(N <= 8000)
第二行是一个字符串，长度为N.只包含小写字母 - 输出格式
如果可能，输出最少的交换次数。
否则输出Impossible - 样例输入
5
mamad - 样例输出
3
代码
#include<iostream>
using namespace std;
int main()
{
int n;
cin >> n;
string s;
cin >> s;
int num = n-1;
int odd = 0;
int flag = 0;
for(int i = 0; i < num; i++)
{
for(int j = num; j >= i; j--)
{
if(j == i)
{
if(n%2==0 || odd==1)
{
cout << "Impossible";
return 0;
}
odd += 1;
flag += n/2 - i;
}
else if(s[i] == s[j])
{
for(int k = j; k < num; k++)
{
swap(s[k], s[k+1]);
flag++;
}
num--;
break;
}
}
}
cout << flag;
return 0;
}
BASIC-20 数的读法
问题描述
- 资源限制
时间限制：1.0s 内存限制：512.0MB - 问题描述
Tom教授正在给研究生讲授一门关于基因的课程，有一件事情让他颇为头疼：一条染色体上有成千上万个碱基对，它们从0开始编号，到几百万，几千万，甚至上亿。
比如说，在对学生讲解第1234567009号位置上的碱基时，光看着数字是很难准确的念出来的。
所以，他迫切地需要一个系统，然后当他输入12 3456 7009时，会给出相应的念法：
十二亿三千四百五十六万七千零九
用汉语拼音表示为
shi er yi san qian si bai wu shi liu wan qi qian ling jiu
这样他只需要照着念就可以了。
你的任务是帮他设计这样一个系统：给定一个阿拉伯数字串，你帮他按照中文读写的规范转为汉语拼音字串，相邻的两个音节用一个空格符格开。
注意必须严格按照规范，比如说“10010”读作“yi wan ling yi shi”而不是“yi wan ling shi”，“100000”读作“shi wan”而不是“yi shi wan”，“2000”读作“er qian”而不是“liang qian”。 - 输入格式
有一个数字串，数值大小不超过2,000,000,000。 - 输出格式
是一个由小写英文字母，逗号和空格组成的字符串，表示该数的英文读法。 - 样例输入
1234567009 - 样例输出
shi er yi san qian si bai wu shi liu wan qi qian ling jiu
代码
#include<iostream>
using namespace std;
int main(int argc, char const *argv[])
{
string arr[]={"ling", "yi", "er", "san", "si", "wu", "liu", "qi", "ba", "jiu"};
string brr[]={"", "", "shi", "bai", "qian", "wan", "shi", "bai", "qian", "yi", "shi"};
string num;
cin >> num;
for (int i = 0; i < num.length(); i++)
{
int x = num[i]-'0';
if(0==x)
{
if(i!=num.length()-1 && num[i+1]-'0'!=0)
{
cout << arr[0] << " ";
}
}
else if(x==1)
{
if(i==num.length()-2)
cout << "yi shi" << " ";
else if(i==num.length()-6 || i==num.length()-10)
cout << "shi" << " ";
else
cout << "yi " << brr[num.length()-i] << " ";
}
else
{
cout << arr[x] << " ";
cout << brr[num.length()-i] << " ";
}
}
return 0;
}
BASIC-21 Sine之舞
问题描述
- 资源限制
时间限制：1.0s 内存限制：512.0MB - 问题描述
最近FJ为他的奶牛们开设了数学分析课，FJ知道若要学好这门课，必须有一个好的三角函数基本功。所以他准备和奶牛们做一个“Sine之舞”的游戏，寓教于乐，提高奶牛们的计算能力。
不妨设
An=sin(1–sin(2+sin(3–sin(4+...sin(n))...)
Sn=(...(A1+n)A2+n-1)A3+...+2)An+1
FJ想让奶牛们计算Sn的值，请你帮助FJ打印出Sn的完整表达式，以方便奶牛们做题。 - 输入格式
仅有一个数：N<201。 - 输出格式
请输出相应的表达式Sn，以一个换行符结束。输出中不得含有多余的空格或换行、回车符。 - 样例输入
3 - 样例输出
((sin(1)+3)sin(1–sin(2))+2)sin(1–sin(2+sin(3)))+1
代码
#include<iostream>
#include<sstream>
using namespace std;
string to_strings(int i)
{
string str;
stringstream ss;
ss<<i;
ss>>str;
return str;
}
int main(int argc, char const *argv[])
{
int N;
cin >> N;
string An[201]={};
An[1] = "sin(1)";
for (int i = 2; i < N+1; i++)
{
An[i] = "sin(1";
for (int j = 2; j <= i; j++)
{
if(j%2==0)
An[i] += "-sin("+to_strings(j);
else
An[i] += "+sin("+to_strings(j);
}
for(int j=0; j<i; j++)
An[i] += ")";
}
string ans = An[1]+"+"+to_strings(N);
for (int i = 2; i <= N; i++)
ans = "("+ans+")"+An[i]+"+"+to_strings(N-i+1);
cout << ans;
return 0;
}
BASIC-22 FJ的字符串
问题描述
- 资源限制
时间限制：1.0s 内存限制：512.0MB - 问题描述
FJ在沙盘上写了这样一些字符串：
A1 = “A”
A2 = “ABA”
A3 = “ABACABA”
A4 = “ABACABADABACABA”
… …
你能找出其中的规律并写所有的数列AN吗？ - 输入格式
仅有一个数：N ≤ 26。 - 输出格式
请输出相应的字符串AN，以一个换行符结束。输出中不得含有多余的空格或换行、回车符。 - 样例输入
3 - 样例输出
ABACABA
代码
#include <iostream>
using namespace std;
int main()
{
string arr = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
string flag = "";
int num;
cin >> num;
flag += "A";
if(num == 1)
{
cout << flag << endl;
return 0;
}
for (int i = 1; i < num; i++)
flag = flag + arr[i] + flag;
cout << flag;
return 0;
}
BASIC-23 芯片测试
问题描述
- 资源限制
时间限制：1.0s 内存限制：512.0MB - 问题描述
有n（2≤n≤20）块芯片，有好有坏，已知好芯片比坏芯片多。
每个芯片都能用来测试其他芯片。用好芯片测试其他芯片时，能正确给出被测试芯片是好还是坏。而用坏芯片测试其他芯片时，会随机给出好或是坏的测试结果（即此结果与被测试芯片实际的好坏无关）。
给出所有芯片的测试结果，问哪些芯片是好芯片。 - 输入格式
输入数据第一行为一个整数n，表示芯片个数。
第二行到第n+1行为n*n的一张表，每行n个数据。表中的每个数据为0或1，在这n行中的第i行第j列（1≤i, j≤n）的数据表示用第i块芯片测试第j块芯片时得到的测试结果，1表示好，0表示坏，i=j时一律为1（并不表示该芯片对本身的测试结果。芯片不能对本身进行测试）。 - 输出格式
按从小到大的顺序输出所有好芯片的编号 - 样例输入
3
1 0 1
0 1 0
1 0 1 - 样例输出
1 3
代码
#include<iostream>
using namespace std;
int main(int argc, char const *argv[])
{
int arr[22]={0};
int num, x;
cin >> num;
for (int i = 0; i < num; i++)
for (int k = 1; k <= num; k++)
{
cin >> x;
arr[k] += x;
}
for (int i = 1; i <= num; i++)
if ( arr[i]> num/2)
cout << i << " ";
return 0;
}
BASIC-24 龟兔赛跑预测
问题描述
- 资源限制
时间限制：1.0s 内存限制：512.0MB - 问题描述
话说这个世界上有各种各样的兔子和乌龟，但是研究发现，所有的兔子和乌龟都有一个共同的特点——喜欢赛跑。于是世界上各个角落都不断在发生着乌龟和兔子的比赛，小华对此很感兴趣，于是决定研究不同兔子和乌龟的赛跑。他发现，兔子虽然跑比乌龟快，但它们有众所周知的毛病——骄傲且懒惰，于是在与乌龟的比赛中，一旦任一秒结束后兔子发现自己领先t米或以上，它们就会停下来休息s秒。对于不同的兔子，t，s的数值是不同的，但是所有的乌龟却是一致——它们不到终点决不停止。
然而有些比赛相当漫长，全程观看会耗费大量时间，而小华发现只要在每场比赛开始后记录下兔子和乌龟的数据——兔子的速度v1（表示每秒兔子能跑v1米），乌龟的速度v2，以及兔子对应的t，s值，以及赛道的长度l——就能预测出比赛的结果。但是小华很懒，不想通过手工计算推测出比赛的结果，于是他找到了你——清华大学计算机系的高才生——请求帮助，请你写一个程序，对于输入的一场比赛的数据v1，v2，t，s，l，预测该场比赛的结果。 - 输入格式
输入只有一行，包含用空格隔开的五个正整数v1，v2，t，s，l，其中(v1,v2<=100;t<=300;s<=10;l<=10000且为v1,v2的公倍数) - 输出格式
输出包含两行，第一行输出比赛结果——一个大写字母“T”或“R”或“D”，分别表示乌龟获胜，兔子获胜，或者两者同时到达终点。
第二行输出一个正整数，表示获胜者（或者双方同时）到达终点所耗费的时间（秒数）。 - 样例输入
10 5 5 2 20 - 样例输出
D
4 - 样例输入
10 5 5 1 20 - 样例输出
R
3 - 样例输入
10 5 5 3 20 - 样例输出
T
4
代码
#include<iostream>
using namespace std;
int main(int argc, char const *argv[])
{
int v1, v2, t, s, l;
cin >> v1 >> v2 >> t >> s >> l;
int r1=0, r2=0, time=0;
while (++time)
{
r1+=v1; r2+=v2;
if(r1>=l || r2>=l)
{
if (r1 == r2)
cout << "D" << endl;
else if(r1>=l)
cout << "R" << endl;
else
cout << "T" << endl;
cout << time;
break;
}
if (r1-r2 >= t)
{
if( (l-r2)/v2 <= s )
{
cout << "T" << endl;
cout << time+(l-r2)/v2;
break;
}
r2+=v2*s;
time+=s;
}
}
return 0;
}
BASIC-25 回形取数
问题描述
- 资源限制
时间限制：1.0s 内存限制：512.0MB - 问题描述
回形取数就是沿矩阵的边取数，若当前方向上无数可取或已经取过，则左转90度。一开始位于矩阵左上角，方向向下。 - 输入格式
输入第一行是两个不超过200的正整数m, n，表示矩阵的行和列。接下来m行每行n个整数，表示这个矩阵。 - 输出格式
输出只有一行，共mn个数，为输入矩阵回形取数得到的结果。数之间用一个空格分隔，行末不要有多余的空格。 - 样例输入
3 3
1 2 3
4 5 6
7 8 9 - 样例输出
1 4 7 8 9 6 3 2 5 - 样例输入
3 2
1 2
3 4
5 6 - 样例输出
1 3 5 6 4 2
代码
#include<iostream>
#include<cstring>
using namespace std;
int arr[205][205];
int main(int argc, char const *argv[])
{
memset(arr,-1,sizeof(arr));
int m, n;
cin >> m >> n;
for (int i = 1; i <= m; i++)
for (int j = 1; j<=n ; j++)
cin >> arr[i][j];
cout << arr[1][1];
arr[1][1] = -1;
int flag = 0;
int x=1, y=1;
while(1)
{
if(arr[x+1][y]==-1 && arr[x-1][y]==-1 && arr[x][y+1]==-1 && arr[x][y-1]==-1)
break;
if (flag==0 && arr[x+1][y]==-1)
flag = (++flag)%4;
else if (flag==1 && arr[x][y+1]==-1)
flag = (++flag)%4;
else if (flag==2 && arr[x-1][y]==-1)
flag = (++flag)%4;
else if (flag==3 && arr[x][y-1]==-1)
flag = (++flag)%4;
switch (flag)
{
case 0: x++; break;
case 1: y++; break;
case 2: x--; break;
case 3: y--; break;
}
cout << " " << arr[x][y];
arr[x][y] = -1;
}
return 0;
}
BASIC-26 报时助手
问题描述
- 资源限制
时间限制：1.0s 内存限制：512.0MB - 问题描述
给定当前的时间，请用英文的读法将它读出来。
时间用时h和分m表示，在英文的读法中，读一个时间的方法是：
如果m为0，则将时读出来，然后加上“o'clock”，如3:00读作“three o'clock”。
如果m不为0，则将时读出来，然后将分读出来，如5:30读作“five thirty”。
时和分的读法使用的是英文数字的读法，其中0~20读作：
0:zero, 1: one, 2:two, 3:three, 4:four, 5:five, 6:six, 7:seven, 8:eight, 9:nine, 10:ten, 11:eleven, 12:twelve, 13:thirteen, 14:fourteen, 15:fifteen, 16:sixteen, 17:seventeen, 18:eighteen, 19:nineteen, 20:twenty。
30读作thirty，40读作forty，50读作fifty。
对于大于20小于60的数字，首先读整十的数，然后再加上个位数。如31首先读30再加1的读法，读作“thirty one”。
按上面的规则21:54读作“twenty one fifty four”，9:07读作“nine seven”，0:15读作“zero fifteen”。 - 输入格式
输入包含两个非负整数h和m，表示时间的时和分。非零的数字前没有前导0。h小于24，m小于60。 - 输出格式
输出时间时刻的英文。 - 样例输入
0 15 - 样例输出
zero fifteen
代码
#include<iostream>
using namespace std;
int main(int argc, char const *argv[])
{
string time[] = {"zero", "one", "two", "three", "four", "five", "six", "seven", "eight", "nine", "ten", "eleven", "twelve", "thirteen", "fourteen", "fifteen", "sixteen", "seventeen", "eighteen", "nineteen", "twenty", "thirty", "forty", "fifty"};
int h, m;
cin >> h >> m;
if(m == 0)
{
if(h <= 20)
cout << time[h] << " o'clock";
else
{
int a = h%10;
cout << "twenty " << time[a] << " o'clock";
}
}
else
{
if(h <= 20)
cout << time[h] << " ";
else
{
int a = h%10;
cout << "twenty " << time[a] << " ";
}
if(m <= 20)
cout << time[m];
else
{
int a = m%10, b = m/10;
cout << time[18+b] << " " << time[a];
}
}
return 0;
}
BASIC-27 2n皇后问题
问题描述
- 资源限制
时间限制：1.0s 内存限制：512.0MB - 问题描述
给定一个n*n的棋盘，棋盘中有一些位置不能放皇后。现在要向棋盘中放入n个黑皇后和n个白皇后，使任意的两个黑皇后都不在同一行、同一列或同一条对角线上，任意的两个白皇后都不在同一行、同一列或同一条对角线上。问总共有多少种放法？n小于等于8。 - 输入格式
输入的第一行为一个整数n，表示棋盘的大小。
接下来n行，每行n个0或1的整数，如果一个整数为1，表示对应的位置可以放皇后，如果一个整数为0，表示对应的位置不可以放皇后。 - 输出格式
输出一个整数，表示总共有多少种放法。 - 样例输入
4
1 1 1 1
1 1 1 1
1 1 1 1
1 1 1 1 - 样例输出
2 - 样例输入
4
1 0 1 1
1 1 1 1
1 1 1 1
1 1 1 1 - 样例输出
0
代码
BASIC-28 Huffuman树
问题描述
-
资源限制
时间限制：1.0s 内存限制：512.0MB -
问题描述
Huffman树在编码中有着广泛的应用。在这里，我们只关心Huffman树的构造过程。
给出一列数={p0, p1, …, pn-1}，用这列数构造Huffman树的过程如下：
1. 找到中最小的两个数，设为pa和pb，将pa和pb从中删除掉，然后将它们的和加入到中。这个过程的费用记为pa + pb。
2. 重复步骤1，直到中只剩下一个数。
在上面的操作过程中，把所有的费用相加，就得到了构造Huffman树的总费用。
本题任务：对于给定的一个数列，现在请你求出用该数列构造Huffman树的总费用。例如，对于数列={5, 3, 8, 2, 9}，Huffman树的构造过程如下：
1. 找到{5, 3, 8, 2, 9}中最小的两个数，分别是2和3，从中删除它们并将和5加入，得到{5, 8, 9, 5}，费用为5。
2. 找到{5, 8, 9, 5}中最小的两个数，分别是5和5，从中删除它们并将和10加入，得到{8, 9, 10}，费用为10。
3. 找到{8, 9, 10}中最小的两个数，分别是8和9，从中删除它们并将和17加入，得到{10, 17}，费用为17。
4. 找到{10, 17}中最小的两个数，分别是10和17，从中删除它们并将和27加入，得到{27}，费用为27。
5. 现在，数列中只剩下一个数27，构造过程结束，总费用为5+10+17+27=59。 -
输入格式
输入的第一行包含一个正整数n（n<=100）。
接下来是n个正整数，表示p0, p1, …, pn-1，每个数不超过1000。 -
输出格式
输出用这些数构造Huffman树的总费用。 -
样例输入
5
5 3 8 2 9 -
样例输出
59
代码
#include<iostream>
using namespace std;
int doingsort(int* arr, int left, int right)
{
int pCur = left;
int pPre = pCur-1;
int key = arr[right];
int mid = (left+right)/2;
if( (arr[mid]>=arr[left] && arr[mid]<=key) || (arr[mid]>=key && arr[mid]<=arr[left]) )
{
arr[right] = arr[mid];
arr[mid] = key;
}
else if( (arr[left]>=arr[mid] && arr[left]<=key) || (arr[left]>=key && arr[left]<=arr[mid]) )
{
arr[right] = arr[left];
arr[left] = key;
}
key = arr[right];
while(pCur < right)
{
if( arr[pCur]>key && ++pPre!=pCur)
{
int xxx = arr[pCur];
arr[pCur] = arr[pPre];
arr[pPre] = xxx;
}
pCur++;
}
arr[right] = arr[pPre+1];
arr[pPre+1] = key;
return ++pPre;
}
void quicksort(int* arr, int left, int right)
{
if(right-left >= 1)
{
int ret = doingsort(arr, left, right);
quicksort(arr, left, ret);
quicksort(arr, ret+1, right);
}
}
int main(int argc, char const *argv[])
{
int arr[101];
int num, sum=0;
cin >> num;
num--;
for (int i = 0; i <= num; i++)
cin >> arr[i];
while (num>0)
{
quicksort(arr, 0, num);
arr[--num] += arr[num+1];
sum += arr[num];
}
cout << sum;
return 0;
}
BASIC-29 高精度加法
问题描述
- 资源限制
时间限制：1.0s 内存限制：512.0MB - 问题描述
输入两个整数a和b，输出这两个整数的和。a和b都不超过100位。 - 算法描述
由于a和b都比较大，所以不能直接使用语言中的标准数据类型来存储。对于这种问题，一般使用数组来处理。
定义一个数组A，A[0]用于存储a的个位，A[1]用于存储a的十位，依此类推。同样可以用一个数组B来存储b。
计算c = a + b的时候，首先将A[0]与B[0]相加，如果有进位产生，则把进位（即和的十位数）存入r，把和的个位数存入C[0]，即C[0]等于(A[0]+B[0])%10。然后计算A[1]与B[1]相加，这时还应将低位进上来的值r也加起来，即C[1]应该是A[1]、B[1]和r三个数的和．如果又有进位产生，则仍可将新的进位存入到r中，和的个位存到C[1]中。依此类推，即可求出C的所有位。
最后将C输出即可。 - 输入格式
输入包括两行，第一行为一个非负整数a，第二行为一个非负整数b。两个整数都不超过100位，两数的最高位都不是0。 - 输出格式
输出一行，表示a + b的值。 - 样例输入
20100122201001221234567890
2010012220100122 - 样例输出
20100122203011233454668012
代码
#include<iostream>
using namespace std;
int main(int argc, char const *argv[])
{
string s1, s2;
cin >> s1 >> s2;
for (int i = 0; i < s1.length()/2; i++)
{
char a = s1[i];
s1[i] = s1[s1.length()-1-i];
s1[s1.length()-1-i] = a;
}
for (int i = 0; i < s2.length()/2; i++)
{
char a = s2[i];
s2[i] = s2[s2.length()-1-i];
s2[s2.length()-1-i] = a;
}
if( s1.length()<s2.length())
{
string x = s1;
s1 = s2;
s2 = x;
}
for (int i = 0; i < s2.length(); i++)
s1[i] += s2[i]-'0';
for (int i = 0; i < s1.length(); i++)
{
if( s1[i]-'0' > 9)
{
if (i != s1.length()-1)
{
char x = s1[i]-'0';
s1[i] = x % 10 + '0';
s1[i+1] += x/10;
}
else
{
char x = s1[i]-'0';
s1[i] = x % 10 + '0';
while(x/=10)
s1 += x%10 + '0';
}
}
}
for (int i = s1.length()-1; i >= 0; i--)
{
cout << s1[i];
}
return 0;
}
BASIC-30 阶乘计算
问题描述
- 资源限制
时间限制：1.0s 内存限制：512.0MB - 问题描述
输入一个正整数n，输出n!的值。
其中n!=123*…*n。 - 算法描述
n!可能很大，而计算机能表示的整数范围有限，需要使用高精度计算的方法。使用一个数组A来表示一个大整数a，A[0]表示a的个位，A[1]表示a的十位，依次类推。
将a乘以一个整数k变为将数组A的每一个元素都乘以k，请注意处理相应的进位。
首先将a设为1，然后乘2，乘3，当乘到n时，即得到了n!的值。 - 输入格式
输入包含一个正整数n，n<=1000。 - 输出格式
输出n!的准确值。 - 样例输入
10 - 样例输出
3628800
代码
#include<bits/stdc++.h>
using namespace std;
string arr = "1";
int main(int argc, char const *argv[])
{
int n, key=0;
cin >> n;
for(int i=2; i<=n; i++)
{
for(int j=0; j<arr.length(); j++)
{
key = (arr[j]-'0')*i + key;
arr[j] = key%10 + '0';
key /= 10;
}
while(key!=0)
{
char flag[2];
itoa(key % 10, flag, 10);
arr += flag;
key /= 10;
}
}
for(int i=arr.length()-1; i>=0; i--)
cout << arr[i];
return 0;
}
Q.E.D.