目录
试题A：空间
//一字节等于8位，1MB=2＾20 B
#include<iostream>
using namespace std;
int main(){
cout<<256*1024*1024/4<<endl;
return 0;
}?答案：67108864
试题B：卡片
#include <iostream>
using namespace std;
int s[10];
bool check(int x){
while(x){
int t=x%10;
x/=10;
if(--s[t]<0)return false;
}
return true;
}
int main(){
for(int i=0;i<10;i++)s[i]=2021;
for(int i=1;;i++){
if(!check(i)){
cout<<i-1<<endl;
return 0;
}
}
return 0;
} 答案：3181
试题C：直线
#include<iostream>
#include<cmath>
#include<algorithm>
#include<cstring>
using namespace std;
const int N=200000;
int n;
struct Line{
double k,b;
bool operator< (const Line& t)const{ //sort排序函数按照斜率k先排
if(k!=t.k)return k<t.k;
return b<t.b;
}
}l[N];
int main(){
for(int x1=0;x1<20;x1++)
for(int y1=0;y1<21;y1++)
for(int x2=0;x2<20;x2++)
for(int y2=0;y2<21;y2++){
if(x1!=x2){
double k=(double)(y2-y1)/(x2-x1);
double b=y1-k*x1;
l[n++]={k,b};
}
}
sort(l,l+n);
int res=1; //l[0]是第一个 ，第一个数没有枚举
for(int i=1;i<n;i++){
if(fabs(l[i].k-l[i-1].k)>1e-8||fabs(l[i].b-l[i-1].b)>1e-8)
res++;
}
cout<<res+20<<endl;
return 0;
}
答案：40257
试题D：货物摆放
#include<iostream>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<vector>
using namespace std;
typedef long long LL;
const LL N=2021041820210418;
int res=0;
int main()
{
vector<LL> d;
//求公约数 然后枚举
for(LL i=1;i*i<=N;i++){
if(N%i==0){
d.push_back(i);
if(N/i!=i) d.push_back(N/i);
}
}
cout<<d.size();
for(LL a=0;a<d.size();a++)
for(LL b=0;b<d.size();b++)
for(LL c=0;c<d.size();c++)
if(d[c]*d[a]*d[b]==N)
res++;
cout<<res<<endl;
return 0;
} 答案：2430
试题E：路径
spfa算法
#include<iostream>
#include<algorithm>
#include<cmath>
#include<cstring>
using namespace std;
const int N=2200,M=N*50;
int n;
int h[N],e[M],w[M],ne[M],idx;// 邻接表存图
int q[N],dist[N];//前驱点和最短路
bool st[N];//判断是否在队列中
int gcd(int a,int b){
return b?gcd(b,a%b):a;//欧几里得求最大公约数
}
void add(int a,int b,int c){//增加一条a->b的边，边权为c
e[idx]=b,w[idx]=c,ne[idx]=h[a],h[a]=idx++;
//e[idx] 为当前idx编号的边指向的终点节点
//w[idx] 为当前idx编号的边权重
//ne 存储邻接表链表，当前值对应邻接表中下一个的地址，类似于值是指针
//h[a] 一直指向a邻接表头插法起点，其实是最后一个，指针保留的方式也是向前
}
void spfa(){//求1号点到n号点的最短路距离
int hh=0,tt=0;
memset(dist,0x3f,sizeof dist);//清空 赋值
dist[1]=0;
q[tt++]=1;
st[1]=true;
while(hh!=tt){
int t=q[hh++];
if(hh==N)hh=0;
st[t]=false;
for(int i=h[t];i!=-1;i=ne[i]){
int j=e[i];
if(dist[j]>dist[t]+w[i]){
dist[j]=dist[t]+w[i];
if(!st[j]){
q[tt++]=j;
if(tt==N)tt=0;
st[j]=true;
}
}
}
}
}
int main(){
n=2021;
memset(h,-1,sizeof h);//清空 赋值
for(int i=1;i<=n;i++){
for(int j=max(1,i-21);j<=min(n,i+21);j++){
int d=gcd(i,j);//求i和j的最大公约数
add(i,j,i*j/d);//最大公倍数=两数之积/最大公约数
}
}
spfa();
cout<<dist[n]<<endl;
return 0;
}
dijkstra算法
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
const int N=2510;
int g[N][N],dist[N],st[N];
int n=2021;
int gcd(int a, int b)
{
return b ? gcd(b, a % b) : a;
}
int lcm(int a,int b){
return a*b/gcd(a,b);
}
int dijkstra(){
memset(dist,0x3f,sizeof dist);
dist[1]=0;
for(int i=1;i<=n;i++){
int t=-1;
for(int j=1;j<=n;j++){
if(!st[j] && (t==-1 || dist[j]<dist[t]))
t=j;
}
st[t]=1;
for(int j=1;j<=n;j++){
dist[j]=min(dist[j],dist[t]+g[t][j]);
}
}
return dist[n];
}
int main(){
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++){
if(i!=j){
if(fabs(i-j)<=21){
g[i][j]=lcm(i,j);
g[j][i]=lcm(i,j);
}
else{
g[i][j]=0x3f3f3f3f;
g[j][i]=0x3f3f3f3f;
}
}
}
cout<<dijkstra();
//cout<<0x3f3f3f3f;
return 0;
}
答案：10266837