1.试题 A:空间
小蓝准备用256MB的内存空间开一个数组,数组的每个元素都是32位二进制整数,如果不考虑程序占用的空间和维护内存需要的辅助空间,请问256MB的空间可以存储多少个32位二进制整数?
答案:67108864
2.试题 B:数字卡片
小蓝有很多数字卡片,每张卡片上都是数字0到9。
小蓝准备用这些卡片来拼一些数。他想从1开始拼出正整数,每拼一个,就保存起来,卡片就不能用来拼其他数了。
小蓝想知道自己能从1拼到多少。
例如,当小蓝有30张卡片,其中0到9各3张,则小蓝可以拼出1到10,但是拼到11时卡片只有一张了,不够拼出11。
现在小蓝手里有0到9的卡片各2021张,共20210张,请问小蓝可以从1 拼到多少?
提示:建议使用计算机编程解决问题。
#include<iostream>
#include<algorithm>
using namespace std;int is(int n){int c=0;int temp=0;while(n!=0){temp=n%10;if(temp==1)c++;n=n/10;}return c;
} int main(){int i=0;int count=0;for(i=1;;i++){count+=is(i);if(count==2021){printf("%d",i);break;}} return 0;
}
答案:3181
3.试题 D:货物摆放
方法一:
这里我先是找出了n的因式分解式子:
#include<iostream>
#include<algorithm>
#include<vector>
#define ll long long
using namespace std;int main(){ll n=2021041820210418;vector<ll> v;v.push_back(1);ll i=0,temp=pow(n,0.5);for(i=2;i<=temp;i++){if(n%i==0){v.push_back(i);n=n/i;i=1;}}auto it=v.begin();for(;it<v.end();it++){cout<<*it<<" ";}}
//输出因式分解式子为:
1 2 3 3 3 17 131 2857 5882353
结合题目,对该因式分解式子进行分析可得,如果我们要找出三个数乘起来是n的话(分顺序),那么其实就是一个排列组合的问题,题目中的数据过于大,可以转变成其他因式进行暴力搜索。举个例子,上述的因式分解其实可以转变成:1 2 3 3 3 5 7 11 13 .
//根据以上分析,因为时间复杂度大大降低了,直接暴搜就行。代码如下:
int main(){int n=1*2*27*5*7*11*13;int i=0,j=0,z=0;int count=0;for(i=1;i<=n;i++)for(j=1;j<=n/i;j++) if(n%(i*j)==0){ count++;} cout<<count;return 0;
}
//输出结果为2430
方法二:
这种方法比较容易。就是找出n的所有因子,然后进行暴力搜索就可以了。因为n比较大,所以我们需要学会降低运行的时间复杂度。
#include<iostream>
#include<algorithm>
#include<vector>
#define ll long long
using namespace std;int main(){vector<ll> v;ll n=2021041820210418;ll i=0,count=0;for(i=1;i<=sqrt(n);i++){if(n%i==0){v.push_back(i);v.push_back(n/i);}}sort(v.begin(),v.end()); for(i=0;i<v.size();i++)for(int j=0;j<v.size();j++){ll l=v[i]*v[j]; if(n%l==0){ count++; }}cout<<count;return 0;
}
//输出结果为2430
答案:2430