文章目录

• 题目结构
• • 第一题 空间
  • 第二题 卡片
  • 第三题 直线
  • 第四题 货物摆放
  • 第五题 路径
  • 第六题 时间显示

题目结构

项目	题型	分值	题型
第一题	结果填空	5	空间（单位换算）
第二题	结果填空	5	卡片（模拟）
第三题	结果填空	10	直线（数学）
第四题	结果填空	10	货物摆放（数学）
第五题	结果填空	15	路径（最短路径）
第六题	程序设计	15	时间显示（时间换算/取位数）
第七题	程序设计	20	砝码称重（DP）
第八题	程序设计	20	杨辉三角
第九题	程序设计	25	双向排序
第十题	程序设计	25	括号序列

---

第一题 空间

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

进值转换：1MB=1024KB 1KB=1024B 1B=8位

cout<<256*1024*1024/4<<endl;

第二题 卡片

1. 用数组计数，从2021减
2. 枚举取位数
3. excel+word检验

#include <iostream>
#include <cmath>
#include <algorithm>
#include <iomanip>
using namespace std;
int cnt[10]={0};
int main(){
    for(int i=0;i<=9;i++) cnt[i]=2021;
    for(int i=1;;i++){
        int t=i;
        while(t){
            if(cnt[t%10]==0) {
                cout<<i-1;
                return 0;
            };
            cnt[t%10]--;
            t/=10;
        }
    }
    return 0;
}

第三题 直线

1. 确定直线用两点式：(y1-y2)x+(x2-x1)y+(x1y2-x2y1)=0
2. 枚举所有的直线
3. 使用set去重
4. pair存放坐标

#include<iostream>
#include<vector>
#include<set>
using namespace std;
typedef pair<int,int> PII;
typedef pair<PII,int> PIII;
vector<PII> v;
set<PIII> s;
int x,y;
int gcd(int a,int b){
    if(b==0) return a;
    return gcd(b,a%b);
}
int main(){
    cin>>x>>y;

    for(int i=0;i<x;i++){
        for(int j=0;j<y;j++){
            v.push_back({i,j});
        }
    }

    for(int i=0;i<v.size();i++){
        for(int j=i+1;j<v.size();j++){
            int x1=v[i].first;
            int y1=v[i].second;
            int x2=v[j].first;
            int y2=v[j].second;
            int A=y1-y2,B=x2-x1,C=x1*y2-x2*y1;
            int gcdd=gcd(gcd(A,B),C);
            s.insert({{B/gcdd,A/gcdd},C/gcdd});
        }
    }
    
    cout<<s.size();
    return 0;
    //答案40257
}

第四题 货物摆放

1. 找到因子数组（平方循环技巧）
2. 遍历因子数组判断乘积是否为n并计数

#include<iostream>
using namespace std;
typedef long long ll;
ll a[5000];
ll len=0,cnt=0;
int main()
{
    ll n=2021041820210418;
    for(ll i=1;i*i<=n;i++){
        if(n%i==0){
            a[len++]=i;
            if(i!=n/i){
                a[len++]=n/i;
            }
        }
    }
    for(ll i=0;i<len;i++){
        for(ll j=0;j<len;j++){
            for(ll k=0;k<len;k++){
                if(a[i]*a[j]*a[k]==n){
                    cnt++;
                }
            }
        }
    }
    cout<<cnt<<endl;
} // namespace std;

第五题 路径

1. 首先确定使用弗洛伊德算法求解最短路径（三个循环）
2. 使用邻接矩阵构造图
3. 弗洛伊德求最短路径得到结果
4. 注意邻接矩阵的数据类型应该为long long 因为无穷大设置的为1e18

#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;
#define INF 1e18;
ll mp[3000][3000];
int gcd(int a,int b){
    if(b==0) return a;
    else return gcd(b,a%b);
}
void Floyd(int n){
    for(int k=1;k<=n;k++){
        for(int i=1;i<=n;i++){
            for(int j=1;j<=n;j++){
                mp[i][j] = min(mp[i][j], mp[i][k] + mp[k][j]);
            }
        }
    }
}
int main()
{
    int n=2021;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            if(i==j) mp[i][j]=0;
            else if(abs(i-j)<=21) mp[i][j]=mp[j][i]=i*j/gcd(i,j);
            else mp[i][j]=mp[j][i]=INF;
        }
    }
    Floyd(n);
    cout<<mp[1][2021]<<endl;
    return 0;
} // namespace std;

第六题 时间显示

所有数据不超过10^18

#include <iostream>
#include <stdio.h>
using namespace std;
long long t,h,m,s,ms;
int main()
{
    cin>>t;
    t=t/1000;
    h=t/3600%24;
    m=t/60%60;
    s=t%60;
    printf("%02lld:%02lld:%02lld",h,m,s);
    return 0;
}