1、A空间

题目：

        小蓝准备用 256MB 的内存空间开一个数组，数组的每个元素都是 32 位二进制整数，如果不考虑程序占用的空间和维护内存需要的辅助空间，请问256MB 的空间可以存储多少个 32 位二进制整数？

解答 ：

1MB=1024KB=1024*1024B=1024*1024*8b

256MB=256*1024*1024*8b
256MB/32b=67108864

答案： 

67108864

2、B卡片

题目：

        小蓝有很多数字卡片，每张卡片上都是数字0到9。小蓝准备用这些卡片来拼一些数，他想从1开始拼出正整数，每拼一个，就保存起来，卡片就不能用来拼其它数了。小蓝想知道自己能从1拼到多少。例如，当小蓝有30张卡片，其中0到9各3张，则小蓝可以拼出1到10,但是拼11时卡片1已经只有一张了，不够拼出11。现在小蓝手里有0到9的卡片各2021张，共20210张，请问小蓝可以从1拼到多少?
提示:建议使用计算机编程解决问题。
[答案提交]
        这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一
个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。

分析 ：

        容易发现数字1的的使用频率最高，只需要统计数字1的数量即可。

        采用除法和取余的方法求解某位的数字大小。

解答： 

#include<iostream>
using namespace std;
#define k 1
int main() {int count = 0, i;for(i = 0; i < 100000; i++) {if(i % 10 == k) {count++;}if((i / 10) % 10 == k) {count++;}if((i / 100) % 10 == k) {count++;}if((i / 1000) % 10 == k) {count++;}if((i / 10000 )%10== k) {count++;}if((i / 100000 )%10== k) {count++;}if(count == 2021) {break;}}cout<<i<<endl;return 0;
}

        没有注意到数字1的使用频率较高，可以暴力解法，对每个数的进行计数，附上代码 。需要注意的是memset不可以给int的数组赋值为2021，每个int需要占用四个字节。

#include <bits/stdc++.h>
using namespace std;
int num[10];
int isempty(){if(num[0]==0||num[1]==0||num[2]==0)return 1;else if(num[3]==0||num[4]==0||num[5]==0)return 1;else if(num[6]==0||num[7]==0||num[8]==0||num[9]==0)return 1;elsereturn 0;}
int main() {//memset(num,0x7e5,sizeof(num));for(int i=0;i<10;i++){num[i]=2021;}int count = 0, i,weishu=0;for(int i=0;i<10000;i++){if(i<10)  weishu=1;else if(i<100)   weishu=2;else if(i<1000)   weishu=3;else if(i<10000)   weishu=4;switch(weishu){case 4: num[(i/1000)%10]--;case 3: num[(i/100)%10]--;case 2: num[(i/10)%10]--;case 1: num[i%10]--;break;default:cout<<"ERROR"<<endl;break;}count = i;if(isempty()) break;}cout<<count<<endl;return 0;
}

答案： 

3181

 3、C直线

题目：

        在平面直角坐标系中，两点可以确定–条直线。如果有多点在一条直线上，那么这些点中任意两点确定的直线是同一条。给定平面上2×3个整点{(x,y)0≤x<2,0≤y<3,x∈Z,y∈Z}，即横坐标是0到1 (包含0和1)之间的整数、纵坐标是0到2(包含0和2)之间的整数的点。这些点一-共确定了11 条不同的直线。给定平面上20×21个整点{(x,y)l0≤x< 20,0≤y<21,x∈Z,y∈Z},即横
坐标是0到19(包含0和19)之间的整数、纵坐标是0到20(包含0和20)之间的整数的点。请问这些点- – 共确定了多少条不同的直线。
[答案提交]
        这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为- –
个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。 

 分析：

        每条直线的斜率和截距都是唯一的，可以通过使用set<pair<type,type> >a来去掉重复项，需要注意double类型和float类型的数据精度，在计算截距是需要手动化简公式，不要直接使用之前算出的斜率k计算截距b，因为截距k本身就是一个不精确的数。将一下type换为float也可以得到相同的答案。

解答： 

#include <bits/stdc++.h>
using namespace std;
//y=kx+b
#define type double
struct point
{type k;type b;
};
point s;
type p_k[100000];
type p_b[100000];
int num=0;
void search_sign(type *p_k);
#define hang 20
#define lie 21
set<pair<type,type> >a;
int main() {s.b=s.k=0;for(int x1 = 0; x1 < hang; x1++) {for(int y1 = 0; y1 < lie; y1++) {//可以令x2和y2从x1和y1开始循环，减少时间复杂度for(int x2 = 0; x2 < hang; x2++) {for(int y2 = 0; y2 < lie; y2++) {//如果斜率为0或者无穷直接忽略if(x1 == x2 || y1 == y2) {continue;}/*s.k = (y1 - y2) * 1.0 / (x1-x2);s.b = ((x2*y1-x1*y2)*1.0)/((x2-x1)*1.0);search_sign(p_k);*/double k = (y1 - y2) * 1.0 / (x1-x2);double b= ((x2*y1-x1*y2)*1.0)/((x2-x1)*1.0);a.insert(make_pair(k,b));}}}}cout<<"线条的个数"<<a.size()+hang+lie<<endl;//cout<<"线条的个数"<<num+hang+lie<<endl;return 0;
}
void search_sign(type *px)
{//查看斜率ktype* weizhi=find(px,p_k+num-1,s.k);if (*weizhi!=s.k){p_k[num]=s.k;p_b[num]=s.b;//cout<<"y="<<p_k[num]<<"x+"<<p_b[num]<<endl;num++;}else{int sign=weizhi-p_k;// cout<<"    sign="<<sign<<endl;if((p_b[sign]!=s.b)){if(sign!=(num-1)){search_sign(&p_k[sign+1]);}else{p_k[num]=s.k;p_b[num]=s.b;//cout<<"y="<<p_k[num]<<"x+"<<p_b[num]<<endl;num++;}}}
}

答案： 

线条的个数40257

        上述代码注释部分为未使用set的解决方法，速度相对较慢，但仍能求解，其中利用find语句查找了数组对应元素的位置，方法如下:

#include<bits/stdc++.h>
#include <iostream>
using namespace std;
int main(){int num[10];for(int i=0;i<10;i++){num[i] = i+3;//3 4 5 6 7......}//从num到num+9（共10个int空间）查找数字5，//查找到返回5，未查找到返回最后一个数num[max]。//尤其需要注意最后一个数是不是要查找的数int* weizhi=find(num,num+10-1,5);//利用地址找到下标位置。int sign=weizhi-num;cout<<"地址"<<weizhi<<endl;cout<<"被查的数"<<*weizhi<<endl;cout<<"对应下标"<<sign<<endl;return 0;
}

运行结果： 

地址0x61fde8
被查的数5
对应下标2

4、 D货物摆放

问题：

        小蓝有一个超大的仓库，可以摆放很多货物。现在，小蓝有n箱货物要摆放在仓库，每箱货物都是规则的正方体。小蓝规定了长、宽、高三个互相垂直的方向，每箱货物的边都必须严格平行于长、宽、高。小蓝希望所有的货物最终摆成-一个大的立方体。即在长、宽、高的方向.上分别堆L、W、H的货物，满足n=LxWx H。给定n，请问有多少种堆放货物的方案满足要求。例如，当n=4时，有以下6种方案: 1x1x4、1x2x2、1x4x1. 2x1x2、2x2x 1、4x 1x 1。请问，当n= 2021041820210418 (注意有 16位数字)时，总共有多少种方案?
提示:建议使用计算机编程解决问题。
[答案提交]
这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为- –
个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。

分析： 

        2021041820210418是一个16位数，需要采用long long来定义数据类型，其次需要在循环上跳出冗余，避免不必要的时间开销。

解答： 

#include<bits/stdc++.h>
using namespace std;
#define input 2021041820210418
//在循环上跳出冗余，避免不必要的时间开销
const int maxn=32000;
long long num[maxn],n,ans[maxn],cnt,len;
int main() {int n;long long L, W, H;for (L = 1; L*L*L <= input; L++){if(input%L!=0)  continue;//L不是约数for (W = L; W*W <=(input/L); W++){//W从L开始循环，小于L的不能能还为约数if((input/L)%W!=0)  continue;//W不是约数H=input/L/W;if(W==L && L==H)    n++;//三个数相同，只有一种组合else if(W==L||W==H||L==H) n+=3;//两个数相同，有三种组合else n+=6;//三个数都不同，有六种组合}}cout<<n<<endl;return 0;
}

答案： 

2430

       也可以求解所有质数，然后排列组合去重，这里 提供一种利用递归求解所有质数的方法  

#include<bits/stdc++.h>
using namespace std;
#define input 2021041820210418
//在循环上跳出冗余，避免不必要的时间开销
const int maxn=32000;
long long num[maxn],n,ans[maxn],cnt,len;
//求解所有约数的方法，调用递归时间上更快
//是质数返回0;
bool isprime(long long n){if(n==1) return 0;if(n==2) return 1;for(long long i=2;i<=sqrt(n)+1;i++) if(n%i==0) return 0;return 1;
}
void getnum(long long n){if(n==1) return;          //递归边界，如果n==1就returnfor(long long i=2;i<=sqrt(n)+1;i++){if(n%i==0){num[++len]=i;if(isprime(n/i)) num[++len]=n/i;else getnum(n/i);break;               //最后记得break}}
}
int main(){//scanf("%d",&n);n=2021041820210418;if(isprime(n)){cout<<n<<"="<<n;return 0;}getnum(n);cout<<n<<"=";for(long long i=1;i<=len;i++){if(i==1) cout<<num[i];else cout<<"*"<<num[i];}
}

运行结果：

2021041820210418=2*3*3*3*17*131*2857*5882353
Process returned 0 (0x0)   execution time : 0.020 s
Press any key to continue.

5、 E路径

题目：

        小蓝学习了最短路径之后特别高兴，他定义了一个特别的图，希望找到图中的最短路径。小蓝的图由2021个结点组成，依次编号1至2021.对于两个不同的结点a, b,如果a和b的差的绝对值大于21，则两个结点之间没有边相连:如果a和b的差的绝对值小于等于21，则两个点之间有一条长度为a和b的最小公倍数的无向边相连。例如:结点1和结点23之间没有边相连:结点3和结点24之间有一条无向边，长度为24; 结点15和结点25之间有一-条无向边，长度为75.请计算，结点1和结点2021之间的最短路径长度是多少。提示:建议使用计算机编程解决题。
[答案提交]
        这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为–
个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。

分析： 

        最短路径采用dijkstra算法，求解最小公倍数不可以使用穷举法，时间复杂度过大，无法计算，可以采用辗转相除法计算出最大公约数后，用两数的乘积除以最大公约数来计算。 

解答： 

#include <bits/stdc++.h>
using namespace std;
//N为节点个数
#define N 2021
int point[N+1][N+1];//储存点
int dis[N+1];//储存当前起点到达其他点的距离
bool vis[N+1];//判断该点是否确定//1为确定,0为不确定
void dijkstra(){//起点为1memset(vis,false,sizeof(vis));vis[1]=1;dis[1]=0;//起点到起点距离为1for(int i=1;i<=N;i++){dis[i]=point[1][i];}for(int i=1;i<=N;i++){int x=0;for(int j=1;j<=N;j++){if(dis[j]<dis[x] && vis[j]==0)  x=j;}vis[x]=1;for(int j=1;j<=N;j++){if((dis[x]+point[x][j])<dis[j]) dis[j]=dis[x]+point[x][j];}}
}//求解最大公约数，不用先比较两数的大小，会自己翻转
int gcd(int a, int b){return b==0? a : gcd(b, a%b);}
//利用最小公倍数=a*b/（a与b的最大公约数）
int get_w(int a, int b){if(abs(a-b)>21)return 0x3f3f3f3f;elsereturn a* b / gcd(a, b) ;
}int main()
{int u,v,w;memset(dis,0x3f3f3f3f,sizeof(dis));for(int i=0;i<(N+1);i++){point[i][i]=0;for(int j=0;j<(N+1);j++){if(i==0 || j==0)     point[i][j]=point[j][i]=0x3f3f3f3f;else if(i!=j){point[i][j]=point[j][i]=get_w(i,j);}}}dijkstra();cout<<dis[2021]<<endl;return 0;
}

答案：

10266837

6、F时间显示

时间限制: 1.0s内存限制: 256.0MB本题总分: 15 分
        小蓝要和朋友合作开发一个时间显示的网站。在服务器上，朋友已经获取了当前的时间，用一个整数表示，值为从1970年1月1日00:00:00到当前时刻经过的毫秒数。现在，小蓝要在客户端显示出这个时间。小蓝不用显示出年月日，只需要显示出时分秒即可，毫秒也不用显示，直接舍去即可。给定一个用整数表示的时间，请将这个时间对应的时分秒输出。[输入格式]
        输入一行包含一个整数， 表示时间。
[输出格式]
        输出时分秒表示的当前时间，格式形如HH:MM:SS，其中HH表示时，值
为0到23，MM表示分，值为0到59，ss 表示秒，值为0到59.时、分、秒
不足两位时补前导0。
[样例输入1]
        46800999
[样例输出1]
        13:00:00
[样例输入2]

        1618708103123
[样例输出2]
        01 :08:23
[评测用例规模与约定]
        对于所有评测用例，给定的时间为不超过108的正整数。

分析：

        很简单，注意一下时分秒的关系就好了。

解答： 

#include <bits/stdc++.h>
using namespace std;
#define type long long
#define n1 46800999
#define n2 1618708103123
int main()
{type day=n1%86400000;type hh=day/3600000;type mm=(day%3600000)/60000;type ss=(day%60000)/1000;if(hh>9) cout<<hh<<":";else cout<<0<<hh<<":";if(mm>9) cout<<mm<<":";else cout<<0<<mm<<":";if(ss>9) cout<<ss<<endl;else    cout<<0<<ss<<endl;cout << setw(2) << setfill('0') <<hh<<":";cout << setw(2) << setfill('0')<<mm<<":";cout << setw(2) << setfill('0')<<ss<< endl;
}

7、G砝码称重 

题目：

时间限制: 1.0s内存限制: 256.0MB本圆总分: 20 分
[问题描述]
        你有一架天平和N个砝码，这N个砝码重量依次是W, w…., Wy.请你计算-共可以称出多少种不同的重量?注意砝码可以放在天平两边.
[输入格式]
        输入的第一行包含一个整数N.
        第二行包含N个整数: W, W, W…, Wy.
[输出格式]
        输出一个整数代表答案。
[样例输入]
        146
[样例输出]
        10
[样例说明]
        能称出的10种重量是:1.2.3.4.5.6.7.9.10.11.
        1= 1;
        2-6-4(天平-边放6,另一边放4);
        3=4-1:4-4:
        5=6- 1;
        6= 6;
        7= 1+6:
        9=4+6- 1:
        10=4+ 6:
        11=1+4+6.
[评测用例规模与约定]
        对于50%的评测用例。1≤N≤15。
        对于所有评测用例，1≤N≤100，N个砝码总重不超过100000

 分析：

        采用动态规划的思路进行解答，但此问题和常见的动态规划问题存在一定的区别，首先，普通的动态规划只有整数，但砝码的加减会有负数的情况，其次，普通的动态规划是求解“最短路径”和或者“为达到某一个明确的指标有多少种组合”这一类问题，但当前问题解决的是“利用现有的资源可以达到多少种不同的指标。”虽然二者稍有区别但总体思路类似。        

        dp[i][j]表示j千克的砝码利用i,i-1,i-1…对应的砝码有多少种组合方式。

        当指标重量等于即将需要添加的砝码时，dp[i][j]=dp[i-1][j]+1;

        当指标重量不等于即将需要添加的砝码时，dp[i][j]=dp[i-1][j]+dp[i-1][abs(j-mg[i])]; dp[i-1][abs(j-mg[i])]为利用前i-1个砝凑出重量差的组合总数。

解答： 

#include<bits/stdc++.h>
using namespace std;
int mg[105];
int dp[105][1000000];
set<int>a;
int main(){int n=0;int sum=0;int ans=0;cin>>n;for(int i=1;i<=n;i++){cin>>mg[i];sum+=mg[i];}for(int i=1;i<=n;i++){for(int j=1;j<=sum;j++){if(mg[i]==j)    dp[i][j]=dp[i-1][j]+1;else if(mg[i]!=j)    dp[i][j]=dp[i-1][j]+dp[i-1][abs(j-mg[i])];if(dp[i][j]>0)  a.insert(j);}}for(int i=1;i<=sum;i++)ans+=dp[n][i];//cout<<"ans="<<ans<<endl;cout<<"a.size()="<<a.size()<<endl;// set<int>::iterator b=a.end();// cout<<b<<endl;return 0;}

答案： 

3
1 4 6
a.size()=10

也可以将二维数组dp的数据类型改为bool，输出ans即为正确答案。

8、H杨辉三角

 问题：

分析： 

        题目本身的难度不是很大，比较棘手的时N的范围和1s的时间限制。

        初步思路为生成杨辉三角阵存储在数组中，然后通过find查询其位于数组的位置（find查询到第一个后就会停止向后查找）。观察到左右两侧的数字均为1，其数组下标序列分别为{1 2 4 7 11…}和{1 3 6 10 15}，相邻两数之间的差值序列为等差数列。杨辉三角中间的数由其两肩的数相加得到，所求数和其两件数的数组下标关系为sanjiao[i]=sanjiao[i-line]+sanjiao[i-line+1]，line为所求数对应的行数。初步思路代码如下

解答： 

#include<bits/stdc++.h>
using namespace std;
#define N 1000000000
//int sanjiao[N+1];
int main()
{//直接定义数组会出现溢出int *sanjiao=NULL;sanjiao=(int *)malloc(sizeof(int)*(N+1));if(sanjiao==NULL)  cout<<"Failed"<<endl;sanjiao[0]=0x3f3f3f3f;sanjiao[1]=1;int m=2,n=3;int m0=2,n0=3;int line=2,line0=2;//生成杨辉三角for(int i=2;i<=N;i++){if(i==m){sanjiao[i]=1;m+=m0;m0++;}else if(i==n){sanjiao[i]=1;n+=n0;n0++;}else{sanjiao[i]=sanjiao[i-line]+sanjiao[i-line+1];}line0--;if(!line0){line++;line0=line;}}int a=6;//cin>>a;int *weizhi=find(sanjiao+1,sanjiao+N,a);if(*weizhi!=a)cout<<"ERROR"<<endl;else{int here=weizhi-sanjiao;cout<<here<<endl;}return 0;
}

分析：

        可以发现，此方法满足N的范围，但是时间严重超标，方法需要改进。

        同时，就此方法而言，需要注意，在main里直接定义数组，数组（int）不可大于524288，为什么？因为用 C 语言直接定义数组，数组空间是开辟在 C 语言占用内存空间的栈区，而栈区开辟的内存有限导致内存溢出。stack的内存为2M，则2M=2*1024KB=2*1024*1024B=2,097,152B，其中可以容纳的int型变量为（2019152/4）=524,288个，程序实测，可以容纳518080个int型。

        想要解决此问题，可以使用全局变量和malloc函数，使用malloc函数动态分配空间至堆区可以有效解决此问题，其大小有电脑配置决定。具体细节可以参考这一篇博客。

        C/C++开大数组溢出问题

        争对生成完整的杨辉三角阵所需的时间开销过大这一问题，可以通过以下方法来解决：

        修改代码执行顺序，先输入需要查询的数，然后在生成杨辉三角阵，在生成杨辉三角阵的同时查看是否有需要查询的数，若找到，则立即停止后续杨辉三角阵的生成，直接输出退出程序，反之继续执行阵的生成与查找。具体代码如下。

优化代码：

#include<bits/stdc++.h>
using namespace std;
#define N 1000000000
#define type int
//int sanjiao[N+1];
int main()
{//直接定义数组会出现溢出type *sanjiao=NULL;sanjiao=(type *)malloc(sizeof(type)*(N+1));if(sanjiao==NULL)  cout<<"Failed"<<endl;sanjiao[0]=0x3f3f3f3f;sanjiao[1]=1;int m=2,n=3;int m0=2,n0=3;int line=2,line0=2;type a=10;//cin>>a;//生成杨辉三角for(int i=2;i<=N;i++){if(i==1){cout<<1<<endl;break;}else if(i==m){sanjiao[i]=1;m+=m0;m0++;}else if(i==n){sanjiao[i]=1;n+=n0;n0++;}else{sanjiao[i]=sanjiao[i-line]+sanjiao[i-line+1];}line0--;if(!line0){line++;line0=line;}if(sanjiao[i]==a){cout<<i<<endl;break;}if(i==N){cout<<"ERROR"<<endl;break;}}/*type a=10;cin>>a;type *weizhi=find(sanjiao+1,sanjiao+N,a);if(*weizhi!=a)cout<<"ERROR"<<endl;else{type here=weizhi-sanjiao;cout<<here<<endl;}*/return 0;
}

        此处查找的type a=10000;可以发现，时间消耗减少，但仍然存在问题，如果所查找的数不在范围内，仍然需要生成完整的杨辉三角阵，其时间消耗仍然大于1s。 

9、I双向排序

分析： 

        使用库中的排序函数sort直接求解，可能在数组过大时会遇到麻烦，先这样解决吧，需要注意sort排序的参数，对应数组下标为前闭后开区间。

解答： 

#include<bits/stdc++.h>
using namespace std;
bool down(int a,int b){return a>b;
}
bool up(int a,int b){return a<b;
}
int main(){int m,n;cin>>n>>m;int *a=NULL;a=(int *)malloc(sizeof(int)*n);if(a==NULL) cout<<"Failed"<<endl;for(int i=0;i<n;i++)a[i]=i+1;for(int i=0;i<m;i++){static bool p;static int q;cin>>p>>q;if(p==0){sort(a,a+q,down);}else{sort(a+q-1,a+n,up);}}for(int i=0;i<n;i++)cout<<a[i]<<" ";return 0;
}

测试结果： 

3 3
0 3
1 2
0 2
3 1 2

 9、J括号序列

        dp有点难，先不做了。。。。。。。。