第十二届蓝桥杯

试题A:空间

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

using namespace std;

int main()
{
    cout<<256*1024*1024/4<<endl;
    return 0;
}

答案:67108864

试题B:卡片

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

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 <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
    {
        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;
    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 <cstring>
#include <algorithm>
#include <vector>

#define int long long

using namespace std;

signed main()
{
    int n;
    cin>>n;
    vector<int>d;
    for(int i=1;i*i<=n;i++)
       if(n%i==0)
       {
           d.push_back(i);
           if(n/i!=i)d.push_back(n/i);
       }
    int res=0;
    for(auto a:d)
       for(auto b:d)
          for(auto c:d)
             if(a*b*c==n)
                res++;
    cout<<res<<endl;

    return 0;
}
为了避免将重复的因子添加到向量d中，使用了if语句if(n/i!=i)。这个条件用于检查除数i是否与商n/i相等，如果它们不相等，则将商n/i添加到向量d中。

考虑以下情况：

当n是一个完全平方数时，例如n=16。

如果只简单地在循环中添加因子，那么在i=4时，4是16的一个因子，而商16/4也是4，这样在向量d中就会添加两次4，导致重复计算。
因此，通过检查if(n/i!=i)条件，可以确保只添加一次因子。
这种处理方式确保了向量d中不会出现重复的因子，从而避免了重复计算。

答案:2430

试题E:路径

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

答案:10266837