C/C++刷题记录(基础)
注意事项
仅作学习之用，侵删 http://lx.lanqiao.cn/problemsets.page
运行限制一般为(做个参考)
最大运行时间：1s
最大运行内存: 256M
题目难不难是我的主观判断，并不客观，博主水平有限
第一个答案一般是我自己写的，尽管批评
一些值得记的小知识：
- 2147483647是计算机32位二进制最大有符号数
HelloWorld⭐
- 有疑问吗？😆
#include
using namespace std;
int main()
{
cout<< “Hello World!”;
return 0;
}
打印沙漏⭐⭐
- 当时写学C时候写的吧，学了一点C++
#include
#include
using namespace std;
const int stdnum = 100;
int Findfool(int num, int *shuzu, int *see);
int Star(int i, char stdr, int *shuzu);
int StarB(int i, char stdr, int *shuzu);
int main()
{
int num;
char chartemp;
int shuzu[stdnum] = {0};
int i = 0;
int see = 0;
for (i = 0; i < stdnum; i++)
{
shuzu\[i\] = 2 \* i + 1;
}
cin >> num >> chartemp;
i = Findfool(num, shuzu, &see);
Star(i, chartemp, shuzu);
StarB(i, chartemp, shuzu);
cout << num - see \* 2 - 1;
return 0;
}
int StarB(int i, char stdr, int *shuzu)
{
int j = 0, k = 0;
int white, tip;
tip = i;
for (int i = 1; i <= tip; i++)
{
white = (shuzu[tip] - shuzu[i]) / 2;
for (k = 0; k < white; k++)
{
cout << “ “;
}
for (j = 0; j < shuzu\[i\]; j++)
{
cout << stdr;
}
cout << endl;
}
return 0;
}
int Star(int i, char stdr, int *shuzu)
{
int j = 0, k = 0;
int white, tip;
tip = i;
for (; i >= 0; i–)
{
white = (shuzu[tip] - shuzu[i]) / 2;
for (k = 0; k < white; k++)
{
cout << “ “;
}
for (j = 0; j < shuzu\[i\]; j++)
{
cout << stdr;
}
cout << endl;
}
return 0;
}
int Findfool(int num, int *shuzu, int *see)
{
int sum = 0;
for (int j = 1; j < stdnum; j++)
{
sum = sum + shuzu[j];
if ((num - 1) / 2 <= sum)
{
*see = sum - shuzu[j];
return –j;
}
}
return 0;
}
个位数统计⭐⭐
答案一
此答案没有注意到1000位的限制
使用到了STL的map
#include
#include
int main()
{
int a = 0;
cin >> a;
int cont = 0;
map<int, int> mymap = {{0, 0},{1, 0},{2, 0},{3, 0}, {4, 0} ,{5, 0} ,{6, 0},{7, 0}, {8, 0} ,{9, 0}};
while (a != 0)
{
cont = a % 10;
a = a / 10;
mymap[cont]++;
}
for (map<int, int>::iterator it = mymap.begin(); it != mymap.end(); ++it)
{
//输出各个元素中的键和值
cout << it->first << “:” << it->second << ‘\n’;
}
return 0;
}
答案二
- 改进了一下，自我感觉良好
#include
#include
int main()
{
string getnum = “0”;
cin >> getnum;
map<char, int> mymap = {{‘0’, 0}, {‘1’, 0}, {‘2’, 0}, {‘3’, 0}, {‘4’, 0}, {‘5’, 0}, {‘6’, 0}, {‘7’, 0}, {‘8’, 0}, {‘9’, 0}};
for (int i = 0; i < getnum.length(); ++i)
{
mymap[getnum[i]]++;
}
for (map<char, int>::iterator it = mymap.begin(); it != mymap.end(); ++it)
{
if (it->second != 0)
{
cout << it->first << “:” << it->second << ‘\n’;
}
}
return 0;
}
摄氏度⭐
- 很简单不说了
#include
#include<math.h>
using namespace std;
int main()
{
int h;
cin >> h;
int c;
c = 5 * (h - 32) / 9;
cout << “Celsius = “<< c;
return 0;
}
单词统计⭐⭐
- 这个类似第3题但是要难一点
- 我用map发现必须从-1开始，max也得是>,很奇怪，改成从0开始和>=max自己跑是正常的，但是蓝桥的编译器过不去。
答案一
#include
#include
成绩统计⭐
答案一
#include
#include
using namespace std;
int main()
{
int number = 0;
int upsix = 0;
int upeight = 0;
int get= 0;
cin >> number;
for(int i = 0 ; i < number ;++i)
{
cin >> get ;
if(get >= 85)
{
upeight++;
}else if(get >= 60)
{
upsix++;
}
}
cout<<setprecision(2)<<(double)(upeight+upsix)*100/number<<”%”<<endl<<(double)(upeight)*100/number<<”%”; //setprecision(2）限定取整2位
return 0;
}
最短路⭐
答案一
- 填空题
#include
using namespace std;
int main()
{
cout << 6;
return 0;
}
回文日期⭐⭐⭐
- 这个题有一个坑就是最大的搜索范围应该为99999999
- 本题参考了题解
答案一
#include
using namespace std;
int months[] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
bool check(int y, int m, int d) //判断是否是合法日期
{
if (d <= 0 || m <= 0 || m >= 13)
return false;
if (m != 2)
{
if (d > months[m])
return false;
}
else
{
int days = months[2] + (y % 4 == 0 && y % 100 != 0 || y % 400 == 0);
if (d > days)
return false;
}
return true;
}
int flip(int x) //将数倒置
{
int res = 0;
while (x)
{
res = res * 10 + x % 10;
x /= 10;
}
return res;
}
bool st1, st2; //判断是否找到两个类型的日期，作者默认C++初始化为false，也可以初始化一下。
int ans1, ans2; //存放要输出的答案
int main()
{
int n;
cin >> n;
cout << st1 << “,” << st2 << endl;
for (int i = n + 1; i <= 99999999; i++)
{
int year = i / 10000, month = i % 10000 / 100, day = i % 100;
if (check(year, month, day))
{
//如果找到第一个答案，则无需判断，继续循环
if (i % 10000 == flip(year) && !st1)
st1 = true, ans1 = i;
//如果找到第二个答案，则无需判断，继续循环
if (i % 10000 == flip(year) && (month / 10 == day / 10) && (month % 10 == day % 10) && !st2)
st2 = true, ans2 = i;
}
//两个答案都找到则退出循环
if (st1 && st2)
break;
}
printf("%d\\n%d\\n", ans1, ans2);
return 0;
}
十六进制转八进制⭐⭐
答案一
- 我的答案，可以通过示例，但是不能通过测试，分析可能是溢出了，int的范围不够大，不超过100000应该说的是位。
#include
#include <math.h>
#include
#include
using namespace std;
int Transfrom(string num)
{
int sum = 0;
int n = num.size();
for (int i = 0, n = num.size() - 1; i < num.size(); i++, n–)
{
if (num[i] < 48 || num[i] > 70)
return 0; //排除不是可操作的情况
if (48 <= num[i] && num[i] <= 57)
{
sum = sum + (num[i] - 48) * pow(16, n);
}
else
{
sum = sum + (num[i] - 65 + 10) * pow(16, n);
}
}
return sum;
}
int main()
{
int n;
cin >> n;
vector<int> array;
string num;
for (int i = 0; i < n; i++)
{
cin >> num;
array.push_back(Transfrom(num));
}
for (vector<int>::iterator j = array.begin(); j != array.end(); ++j)
{
cout << oct << \*j <<endl;
}
}
答案二
#include
#include
using namespace std;
int main(){
int n;
cin>>n;
while(n–){
string str = “”;
cin>>str;
string res1 = “”; //保存十六进制转为二进制的数
for(int i = 0;i < str.length();++i){
switch(str[i]){ //从前到后依次替换并加到res1后
case ‘0’ : res1 += “0000”;break;
case ‘1’ : res1 += “0001”;break;
case ‘2’ : res1 += “0010”;break;
case ‘3’ : res1 += “0011”;break;
case ‘4’ : res1 += “0100”;break;
case ‘5’ : res1 += “0101”;break;
case ‘6’ : res1 += “0110”;break;
case ‘7’ : res1 += “0111”;break;
case ‘8’ : res1 += “1000”;break;
case ‘9’ : res1 += “1001”;break;
case ‘A’ : res1 += “1010”;break;
case ‘B’ : res1 += “1011”;break;
case ‘C’ : res1 += “1100”;break;
case ‘D’ : res1 += “1101”;break;
case ‘E’ : res1 += “1110”;break;
case ‘F’ : res1 += “1111”;break;
}
}
//判断二进制转八进制是否需要补0
int len2 = res1.length();
if(len2%3 == 1) res1 = “00”+res1;
if(len2%3 == 2) res1 = “0”+res1;
//生成八进制数
string res2 = “”;
for(int i = 0;i<len2;i+=3){
string temp = res1.substr(i,3);
if(i == 0 && temp == “000”) res2 += “”;
else res2 += (4*((temp[0])-‘0’)+2*((temp[1])-‘0’)+((temp[2])-‘0’))+’0’;
}
cout<<res2<<endl;
}
return 0;
}
答案三
这个代码简洁优美
关于ignore这个讲的很清楚 https://blog.csdn.net/wxbmelisky/article/details/48596881
#include
#include
#include
using namespace std;
int main()
{
int n, first;
string s;
(cin >> n).ignore();
cout.fill(‘0’);
for (int i = 0; i < n; i++)
{
getline(cin, s);
first = s.size() % 6 ? s.size() % 6 : 6; //先转头部1-6位
cout << oct << stoi(s.substr(0, first).c_str(), nullptr, 16);
for (int i = first; i < s.size(); i += 6) //后面每：6位HEX ==> 8位OCT
cout << oct << setw(8) << stoi(s.substr(i, 6).c_str(), nullptr, 16);
cout << endl;
}
}
排序⭐
答案一
- 这个也可以自己写一个排序
#include
#include
#include
using namespace std;
int main(){
int input;
int n;
cin >> n;
vector<int> array;
for(int i = 0; i < n ;i++){
cin>>input;
array.push_back(input);
}
sort(array.begin(),array.end()) ; //从小到大排序
for(vector<int>::iterator j = array.begin() ; j != array.end() ;j++){
cout<< *j<<” “;
}
return 0;
}
十六进制转十进制⭐
答案一
- 这里我偷了个懒直接用了十六转八的部分答案，但是只能拿75分，很明显还是溢出了
#include
#include <math.h>
#include
#include
using namespace std;
int Transfrom(string num)
{
int sum = 0;
int n = num.size();
for (int i = 0, n = num.size() - 1; i < num.size(); i++, n–)
{
if (num[i] < 48 || num[i] > 70)
return 0; //排除不是可操作的情况
if (48 <= num[i] && num[i] <= 57)
{
sum = sum + (num[i] - 48) * pow(16, n);
}
else
{
sum = sum + (num[i] - 65 + 10) * pow(16, n);
}
}
return sum;
}
int main()
{
string sixteen = “”;
cin >> sixteen;
cout << Transfrom(sixteen);
return 0;
}
答案二
- 参考了网上的资料改成longlong就可以把所有的例子过掉，但是还是觉得不妥，因为第9题已经吃过一次亏了，有没有不按位权相加的办法，之后再看看🚴
#include
#include <math.h>
#include
#include
using namespace std;
long long Transfrom(string num)
{
long long sum = 0; //这里改为longlong
int n = num.size();
for (int i = 0, n = num.size() - 1; i < num.size(); i++, n–)
{
if (num[i] < 48 || num[i] > 70)
return 0; //排除不是可操作的情况
if (48 <= num[i] && num[i] <= 57)
{
sum = sum + (num[i] - 48) * pow(16, n);
}
else
{
sum = sum + (num[i] - 65 + 10) * pow(16, n);
}
}
return sum;
}
int main()
{
string sixteen = “”;
cin >> sixteen;
cout << Transfrom(sixteen);
return 0;
}
十进制转十六进制⭐
问题描述：
十六进制数是在程序设计时经常要使用到的一种整数的表示方式。它有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进制表示
答案一
- 这个的坑可能就是0的处理
#include
#include
#include
using namespace std;
int main()
{
int num = 0;
cin >> num;
vector<char> str;
while (num >= 0)
{
switch (num % 16)
{
case 0:str.push_back(‘0’);break;
case 1:str.push_back(‘1’);break;
case 2:str.push_back(‘2’);break;
case 3:str.push_back(‘3’);break;
case 4:str.push_back(‘4’);break;
case 5:str.push_back(‘5’);break;
case 6:str.push_back(‘6’);break;
case 7:str.push_back(‘7’);break;
case 8:str.push_back(‘8’);break;
case 9:str.push_back(‘9’);break;
case 10:str.push_back(‘A’);break;
case 11:str.push_back(‘B’);break;
case 12:str.push_back(‘C’);break;
case 13:str.push_back(‘D’);break;
case 14:str.push_back(‘E’);break;
case 15:str.push_back(‘F’);break;
default:break;
}
num = num / 16;
if (num == 0)
{
break;
}
}
string sum = “”;
for (vector<char>::iterator i = str.end() - 1; i >= str.begin(); i–)
{
sum += *i;
}
cout << sum;
return 0;
}
特殊回文数⭐
答案一
- 写出来都想说一句: 机器，您受累了😆
#include
#include
#include
using namespace std;
int main()
{
int n = 0;
cin >> n;
for (int i = 10000; i <= 999999;++i)
{
int sum = 0;
int cont = 0;
int justice = i;
while(justice!=0)
{
sum = sum + justice % 10;
justice = justice / 10;
cont++;
}
if(sum == n)
{
if(cont == 5)
{
stringstream ss; //使用了字符串流，要加头文件
ss << i;
string num = ss.str();//int转换为string类型
if(num[0]==num[4]&&num[1]==num[3])
{
cout << i << endl;
}
}else if(cont == 6)
{
stringstream ss;
ss << i;
string num = ss.str();
if(num[0]==num[5]&&num[1]==num[4]&&num[2]==num[3])
{
cout << i << endl;
}
}
}
}
return 0;
}
回文数⭐
问题描述
1221是一个非常特殊的数，它从左边读和从右边读是一样的，编程求所有这样的四位十进制数。
输出格式
按从小到大的顺序输出满足条件的四位十进制数。
答案一
- 勿以简单而不做，没什么好说的
#include
#include
#include
using namespace std;
int main()
{
for (int i = 1000; i <= 9999; ++i)
{
stringstream ss;
ss << i;
string num = ss.str();
if (num[0] == num[3] && num[1] == num[2])
{
cout << i << endl;
}
}
return 0;
}
特殊数字⭐
问题描述
153是一个非常特殊的数，它等于它的每位数字的立方和，即153=1x1x1+5x5x5+3x3x3。编程求所有满足这种条件的三位十进制数。
输出格式
按从小到大的顺序输出满足条件的三位十进制数，每个数占一行。
答案一
- 勿以简单而不做，没什么好说的
#include
#include <math.h>
using namespace std;
int main()
{
int byte[3] = {0};
for (int i = 100; i <= 999; ++i)
{
int mid = i;
for (int j = 0; j < 3; ++j)
{
byte[j] = mid % 10;
mid = mid / 10;
}
int sum = pow(byte[0], 3) + pow(byte[1], 3) + pow(byte[2], 3);
if (i == sum)
{
cout << i << endl;
}
}
return 0;
}
杨辉三角⭐
问题描述
杨辉三角形又称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
#include <math.h>
using namespace std;
int main()
{
int n = 0;
cin >> n;
int sum[35][35] = {0};
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= i; j++)
{
if (i == 1 && j == 1)
{
sum[i][j] = 1;
}
else
{
sum[i][j] = sum[i - 1][j - 1] + sum[i - 1][j];
}
cout << sum[i][j] << “ “;
}
cout << endl;
}
return 0;
}
查找整数⭐
问题描述
给出一个包含n个整数的数列，问整数a在数列中的第一次出现是第几个。
输入格式
第一行包含一个整数n。
第二行包含n个非负整数，为给定的数列，数列中的每个数都不大于10000。
第三行包含一个整数a，为待查找的数。
输出格式
如果a在数列中出现了，输出它第一次出现的位置(位置从1开始编号)，否则输出-1。
样例输入
6
1 9 4 8 3 9
9样例输出
2
数据规模与约定
1 <= n <= 1000
答案一
- 确实是简单题，不用vecoter的话可能就稍微难一点
#include
#include
#include
using namespace std;
int main()
{
int n;
cin >> n; //数列的个数
vector<int> num;
int number;
for (int i = 0; i < n; ++i)
{
cin >> number;
num.push_back(number);
}
int find, count = 0,result = -1;
cin >> find;
for (vector<int>::iterator i = num.begin(); i != num.end(); ++i)
{
count++;
if (*i == find)
{
cout << count;
result = 1;
break;
}
}
if(result == -1)
{
cout << result;
}
return 0;
}
数列特征⭐
问题描述
给出n个数，找出这n个数的最大值，最小值，和。
输入格式
第一行为整数n，表示数的个数。
第二行有n个数，为给定的n个数，每个数的绝对值都小于10000。
输出格式
输出三行，每行一个整数。第一行表示这些数中的最大值，第二行表示这些数中的最小值，第三行表示这些数的和。
样例输入
5
1 3 -2 4 5样例输出
5
-2
11数据规模与约定
1 <= n <= 10000。
答案一
- 没什么难的
#include
#include
#include
using namespace std;
int main()
{
int n;
cin >> n;
vector<int> narray;
for (int i = 0; i < n; ++i)
{
int input;
cin >> input;
narray.push_back(input);
}
int max = *narray.begin(), min = *narray.begin(), sum = 0;
for (vector<int>::iterator i = narray.begin(); i != narray.end(); ++i)
{
sum = sum + *i;
if (max < *i)
{
max = *i;
}
if (min > *i)
{
min = *i;
}
}
cout << max << endl
<< min << endl
<< sum;
return 0;
}
字母图形⭐⭐
问题描述
利用字母可以组成一些美丽的图形，下面给出了一个例子：
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
#include <math.h>
using namespace std;
int main()
{
int n = 0, m = 0;
cin >> n >> m;
int begin = ‘A’;
for (int i = 0; i < n; ++i)
{
int mid = i;
for (int j = i; j > 0; –j)
{
if (mid - m >= j)
{
break;
}
cout << (char)(begin + j);
}
for (int j = 0; j < m - i; ++j)
{
cout << (char)(begin + j);
}
cout << endl;
}
return 0;
}
01字串⭐
问题描述
对于长度为5位的一个01串，每一位都可能是0或1，一共有32种可能。它们的前几个是：
00000
00001
00010
00011
00100
请按从小到大的顺序输出这32种01串。
输入格式
本试题没有输入。
输出格式
输出32行，按从小到大的顺序每行一个长度为5的01串。
样例输出
00000
00001
00010
00011
<以下部分省略>
答案一
- 主要是知道用法
#include
#include
using namespace std;
int main()
{
for (int i = 0; i < 32; ++i)
{
cout << bitset<5>(i) << endl;
}
return 0;
}
闰年判断⭐
问题描述
给定一个年份，判断这一年是不是闰年。
当以下情况之一满足时，这一年是闰年：
\1. 年份是4的倍数而不是100的倍数；
\2. 年份是400的倍数。
其他的年份都不是闰年
输入格式
输入包含一个整数y，表示当前的年份。
输出格式
输出一行，如果给定的年份是闰年，则输出yes，否则输出no。
样例输入
2013
样例输出
no
样例输入
2016
数据规模与约定
1990 <= y <= 2050。
答案一
- 这个是基础
#include
using namespace std;
int main()
{
int year = 0;
cin >> year;
if(year % 4 == 0 && year % 100 != 0 || year % 400 == 0)
{
cout << “yes”;
}else{
cout << “no”;
}
return 0;
}
Fibonacci数列⭐
问题描述
Fibonacci数列的递推公式为：Fn=Fn-1+Fn-2，其中F1=F2=1。
当n比较大时，Fn也非常大，现在我们想知道，Fn除以10007的余数是多少。
输入格式
输入包含一个整数n。
输出格式
输出一行，包含一个整数，表示Fn除以10007的余数。
说明：在本题中，答案是要求Fn除以10007的余数，因此我们只要能算出这个余数即可，而不需要先计算出Fn的准确值，再将计算的结果除以10007取余数，直接计算余数往往比先算出原数再取余简单。
样例输入
10
样例输出
55
样例输入
22
样例输出
7704
数据规模与约定
1 <= n <= 1,000,000。
答案一
- 用了递归先求了得数，不太理解他说的可以不求值的意思，输入55运行超时，它最大的数是999999，肯定是溢出了
#include
using namespace std;
int Fib(int n)
{
if (n == 1 || n == 2)
{
return 1;
}
else
{
return Fib(n - 1) + Fib(n - 2);
}
}
int main()
{
int n = 0;
cin >> n;
cout << Fib(n) % 10007;
return 0;
}
答案二
- 本答案取自原文链接：https://blog.csdn.net/u012110719/article/details/41704381
- 分析是同样求斐波那契，只不过在求和时将得数取余再相加，这样就减少了计算量
#include <stdio.h>
#define M 10007
int main()
{
int a1, a2;
a1 = a2 = 1;
int sum = 0, temp; // sum是保存余数的变量 ，temp是为了方便交换数据
long n; //因为n>=1 and n<=1000000
long i;
scanf(“%ld”, &n);
for (i = 1; i <= n; i++)
{
sum = a1 % M;
temp = a2;
a2 = (a1 + a2) % M; //这里
a1 = temp;
}
printf("%d\\n", sum);
return 0;
}
圆的面积⭐
问题描述
给定圆的半径r，求圆的面积。
输入格式
输入包含一个整数r，表示圆的半径。
输出格式
输出一行，包含一个实数，四舍五入保留小数点后7位，表示圆的面积。
样例输入
4
样例输出
50.2654825
数据规模与约定
1 <= r <= 10000。
说明：在本题中，输入是一个整数，但是输出是一个实数。对于实数输出的问题，请一定看清楚实数输出的要求，比如本题中要求保留小数点后7位，则你的程序必须严格的输出7位小数，输出过多或者过少的小数位数都是不行的，都会被认为错误。实数输出的问题如果没有特别说明，舍入都是按四舍五入进行。
本题对精度要求较高，请注意π的值应该取较精确的值。你可以使用常量来表示π，比如PI=3.14159265358979323，也可以使用数学公式来求π，比如PI=atan(1.0)*4。
答案一
#include
#include
using namespace std;
#define PI 3.14159265358979323
int main()
{
double r;
cin >> r;
double area = r * r * PI;
cout <<fixed<<setprecision(7)<<area;
return 0;
}
序列求和⭐
问题描述
求1+2+3+…+n的值。
输入格式
输入包括一个整数n。
输出格式
输出一行，包括一个整数，表示1+2+3+…+n的值。
样例输入
4
样例输出
10
样例输入
100
样例输出
5050
数据规模与约定
1 <= n <= 1,000,000,000。
说明：请注意这里的数据规模。
本题直接的想法是直接使用一个循环来累加，然而，当数据规模很大时，这种“暴力”的方法往往会导致超时。此时你需要想想其他方法。你可以试一试，如果使用1000000000作为你的程序的输入，你的程序是不是能在规定的上面规定的时限内运行出来。
本题另一个要值得注意的地方是答案的大小不在你的语言默认的整型(int)范围内，如果使用整型来保存结果，会导致结果错误。
如果你使用C++或C语言而且准备使用printf输出结果，则你的格式字符串应该写成%I64d以输出long long类型的整数。
答案一
- 很简单
#include
using namespace std;
int main()
{
long long n = 0, sum = 0; //要点在这里
cin >> n;
for (int i = 1; i <= n; ++i)
{
sum = sum + i;
}
cout << sum;
return 0;
}
阶乘计算⭐⭐⭐
- 问题描述
输入一个正整数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
答案一
- 又是一道感觉很难的的题，我的答案只能得30分，部分对部分错，部分运行超时
- 难点是当n很大时不能用数据类型来存储
- 尝试了vector，但是发现将会相当复杂
- 于是准备转为string，自己找了很多测试数据，到最后有小小的bug就是排除不了了
- 我突然想到，我为什么要用stirng，直接用数组不好嘛？
#include
#include
#include
#include
using namespace std;
int swap(string &A, string &B)
{
string c;
c = A;
A = B;
B = c;
return 0;
}
// 1234
// 129
// ____
// 1363
string sum(string x, string y)
{
string result; //每一个位的值乘出来的结果
int pull1 = 0; //进位
for (int i = 0, j = 0; j < y.length() | i < x.length(); ++j, ++i) //以后达到的条件为主
{
stringstream ss; //将i转为字符串
if (i >= x.length())
{
int value = 0 + (y[j] - 48) + pull1;
pull1 = value / 10;
ss << value % 10;
string mid = ss.str();
result += mid;
}
else if (j >= y.length())
{
int value = (x[i] - 48) + 0 + pull1;
pull1 = value / 10;
ss << value % 10;
string mid = ss.str();
result += mid;
}
else
{
int value = (x[i] - 48) + (y[j] - 48) + pull1;
pull1 = value / 10;
ss << value % 10;
string mid = ss.str();
result += mid;
}
}
// reverse(result.begin(), result.end()); // str执行完这句，就已经是逆序结果。
return result;
}
// 1234 x
// 129 y
// ____
// 11106
// 2468
// 1234
//______
// 159186
string multy(string x, string y)
{
// cout << “成功” << endl;
if (x.length() < y.length())
{
// cout << “2” << endl;
swap(x, y);
}
// cout << “进入函数后” << x << “ “ << y << endl;
string result[1000]; //每一个位的值乘出来的结果
int pull1 = 0; //进位初始化
for (int i = y.length() - 1, k = 0; i >= 0; –i, ++k)
{
pull1 = 0; //进位清零
int n = y.length() - 1 - i;
for (int c = 0; c < n; c++)
{
result[k] += “0”;
// cout << “1” << endl;
}
for (int j = x.length() - 1; j >= 0; –j)
{
int value = (x[j] - 48) * (y[i] - 48) + pull1;
// cout << “x,y:” << (x[j] - 48) << “ “ << (y[i] - 48) << endl;
// cout << “value:” << value << endl;
pull1 = value / 10;
stringstream ss; //将i转为字符串
ss << value % 10;
string mid = ss.str();
result[k] += mid;
}
if (pull1 != 0)
{
stringstream ss; //将i转为字符串
ss << pull1;
string mid = ss.str();
result[k] += mid;
}
// cout << “第” << i << “循环”
// << “的result[k]为：” << result[k] << endl;
if (k != 0)
{
result[0] = sum(result[0], result[k]);
}
}
reverse(result[0].begin(), result[0].end());
return result[0];
}
int main()
{
int n = 0;
cin >> n;
string result = “1”;
for (int i = 2; i <= n; i++)
{
stringstream ss; //将i转为字符串
ss << i;
string s1 = ss.str();
result = multy(result, s1);
}
cout << result;
return 0;
}
答案二
- 答案源自链接：https://blog.csdn.net/chensanwa/article/details/79013312
- 事实证明我想的太复杂
#include
#include <string.h>
using namespace std;
//全局变量数组，答主说可以避免函数之间的传值问题，在函数外的内存申请在堆中，在函数内的内存申请在栈中，栈的空间比堆小。
int a[10005];
int main ()
{
long n,temp;
//这是一个赋值操作，相当于初始化，我觉得可以不用这么写，答主说可以不写，原因是因为C++默认初始化好了吧
memset(a,0,sizeof(a));
cin>>n;
a[0]=1;
int s,c=0; //c 进位
for(int i=2;i<=n;i++)
{
for(int j=0;j<10000;j++){
s=a[j]*i+c;
a[j]=s%10;
c=s/10;
}
}
for(int i=10000;i>=0;i–){
if(a[i]!=0){
for(int j=i;j>=0;j–){
cout<<a[j];
}
break;
}
}
return 0;
}
高精度加法⭐⭐
问题描述
输入两个整数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
#include
#include
#include
using namespace std;
string sum(string x, string y)
{
string result; //每一个位的值乘出来的结果
int pull1 = 0; //进位
for (int i = x.length() - 1, j = y.length() - 1; j >= 0 | i >= 0; --j, --i) //以后达到的条件为主
{
stringstream ss; //将i转为字符串
if (i >= x.length())
{
int value = 0 + (y\[j\] - 48) + pull1;
pull1 = value / 10;
ss << value % 10;
string mid = ss.str();
result += mid;
}
else if (j >= y.length())
{
int value = (x\[i\] - 48) + 0 + pull1;
pull1 = value / 10;
ss << value % 10;
string mid = ss.str();
result += mid;
}
else
{
int value = (x\[i\] - 48) + (y\[j\] - 48) + pull1;
pull1 = value / 10;
ss << value % 10;
string mid = ss.str();
result += mid;
}
}
stringstream st; //将i转为字符串，这里必须重新定义不同的变量，不然回累积之前的字符串
if (pull1 != 0)
{
st << pull1;
string mid = st.str();
result += mid;
}
reverse(result.begin(), result.end()); // str执行完这句，就已经是逆序结果。
return result;
}
int main()
{
string a, b;
cin >> a >> b;
cout << sum(a, b);
return 0;
}
Huffuman树
Huffman树在编码中有着广泛的应用。在这里，我们只关心Huffman树的构造过程。
给出一列数{pi}={p0, p1, …, pn-1}，用这列数构造Huffman树的过程如下：
1
21. 找到{*pi*}中最小的两个数，设为*pa*和*pb*，将*pa*和*pb*从{*pi*}中删除掉，然后将它们的和加入到{*pi*}中。这个过程的费用记为*pa* + *pb*。
2. 重复步骤1，直到{*pi*}中只剩下一个数。在上面的操作过程中，把所有的费用相加，就得到了构造Huffman树的总费用。
本题任务：对于给定的一个数列，现在请你求出用该数列构造Huffman树的总费用。
例如，对于数列{pi}={5, 3, 8, 2, 9}，Huffman树的构造过程如下：
1. 找到{5, 3, 8, 2, 9}中最小的两个数，分别是2和3，从{pi}中删除它们并将和5加入，得到{5, 8, 9, 5}，费用为5。
2. 找到{5, 8, 9, 5}中最小的两个数，分别是5和5，从{pi}中删除它们并将和10加入，得到{8, 9, 10}，费用为10。
3. 找到{8, 9, 10}中最小的两个数，分别是8和9，从{pi}中删除它们并将和17加入，得到{10, 17}，费用为17。
4. 找到{10, 17}中最小的两个数，分别是10和17，从{pi}中删除它们并将和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
答案一
- 这个题看着笔记复杂，但是思路还是很清晰的。