2021年第12届蓝桥杯第一场学习笔记

A 空间

#include<iostream>
#include<stdio.h>
using namespace std;
int main(){
    long  int a=256*1024*1024/4;
    cout<<a<<endl;
    printf("result: %d",a);
    return 0;
}

B 卡片

#include<iostream>
#include<stdio.h>
#include<cstring>
#include<algorithm>
using namespace std;
int s[10];
// 卡片题目做模拟
bool card(int j){

    while(j){
        int k = j % 10;
        j = j/10;
        if(--s[k]<0){
            return true;
        }
    }
    return false;
}

int main(){
    // 思路：用一张少一张
    for(int i=0;i<10;i++) s[i]=2021;
    for(int j=1; ;j++){
        if(card(j)){
            cout<<j-1;
            return 0;
        }
    }
    return 0;
}

C 直线

注意：Trick:

• 判断两个Double是否相等可以借助差值是否小于1e-8
• 求斜率分母不可以为0

#include<iostream>
#include<stdio.h>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
const int N=200000;
int n=0;
struct Line{
    double k,b;
    bool operator < (const Line&t)const{
        // k,b运算符重载
        if(k!=t.k) return k<t.k;
        return b<t.b;
    }
}line[N];
int main(){
    // 直线：判断K,B是否相等
    // 每个数据都有k,b两个元素
    // 计算所有直线
    for(int x1=0;x1<20;x1++){
            for(int x2=0;x2<20;x2++){
                for(int y1=0;y1<21;y1++){
                    for(int y2=0;y2<21;y2++)
                    if(x2!=x1){
                        double k = (double)(y2-y1) / (x2-x1);
                        double b = y1 - k*x1;
                        //cout<<k<<" "<<b<<endl;
                        line[n++]={k,b};
                    }
                }
            }
    }
    sort(line,line+n);
    int res=1;
    for(int i=1;i<n;i++){
        if(fabs(line[i-1].k-line[i].k)>1e-8 || fabs(line[i-1].b-line[i].b)>1e-8){
            // 两条直线斜率相差大于1e-8则为不同直线
            res++;
        }
    }
    cout<<res+20;
    return 0;
}

D 货物摆放

方案一： 直接暴力

A:2430

#include<iostream>
#include<stdio.h>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long LL;
int main(){
    LL n=2021041820210418;
    LL res = 0;
    for(LL i=1;i*i*i<=n;i++){
        if(n % i==0)
        for(LL j=i;i*j*j<=n;j++){
            if(n / i % j == 0){
                LL k = n / i / j;
                // 如果三个均相等
                if(i==j && j==k) res++;
                else if (i!=j &&j!=k && i!=k) res+=6;
                else res+=3;
            }
        }
    }
    cout<<res;
    return 0;
}

E 路径

最后一道填空题

模板题，然而我记不住模板

欧几里得，最短路径
参考大佬的代码：
https://www.acwing.com/activity/content/code/content/1175272/
A:10266837

#include <iostream>
#include <cstring>
#include <algorithm>

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 ++ ;
}

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])     // 如果队列中已存在j，则不需要将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);
            add(i, j, i * j / d);
        }

    spfa();
    printf("%d\n", dist[n]);
    return 0;
}

作者：yxc
链接：https://www.acwing.com/activity/content/code/content/1175272/
来源：AcWing
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

F 时间显示

送分题

看好测试用例 调试一下就可以了

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

typedef long long LL;

int main()
{
    LL n;
    cin >> n;
    n /= 1000;
    n %= 86400;
    int h = n / 3600;
    n %= 3600;
    int m = n / 60;
    int s = n % 60;
    printf("%02d:%02d:%02d\n", h, m, s);
    return 0;
}

G: 砝码称重

背包问题

闫式dp/dfs 还没学会…

参考大佬的算法

#include <bits/stdc++.h>

using namespace std;

const int N = 110, M = 2e5 + 10;
int sum;
int n;
int w[N];
bool f[N][M];

int main() {

    cin>>n;
    for (int i = 1; i <= n; i++)
    {
        scanf("%d", &w[i]);
        sum+=w[i];
    }

    f[0][0]=true;

    for (int i = 1; i <= n;i++)
        for (int j = 0; j <=sum;j++)
            f[i][j]=f[i-1][j]||f[i-1][j+w[i]]||f[i-1][abs(j-w[i])];
                //只要有一个非空,f[i][j]就非空
    int ans = 0;
    for (int i = 1; i <=sum;i++)
        if(f[n][i])ans++;//不为零说明可以选出这个质量的砝码

    cout << ans;

    return 0;
}

作者：数学汤家凤
链接：https://www.acwing.com/solution/content/21995/
来源：AcWing
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

H 杨辉三角

看上去简单，实际上AC不出…

I 双向排序

思路：
30%的题目应该可以两个sort 混点分

#include<iostream>
#include<stdio.h>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long LL;

bool cmp1(int a,int b){
    // 升序
    return a<=b;
}

bool cmp2(int a,int b){
    // 降序
    return a>=b;
}

int main(){

    int n,m;
    cin>>n>>m;
    int a[100000];
    for(int i=0;i<n;i++){
        a[i]=i+1;
    }

    while(m--){
        int p,q;
        cin>>p>>q;
        if(p==0) sort(a,a+q,cmp2);
        else sort(a+q,a+n,cmp1);
    }

    for(int i=0;i<n;i++){
        cout<<a[i]<<" ";
    }

    return 0;
}