C++省赛B组个人题解（部分）

试题A：空间

题目

答案：67108864

分析
计算机组成原理题，一上来就栽跟头了。。。
1byte=8bits,Bit意为"位"或"比特"，是计算机运算的基础；
Byte意为"字节"，是计算机文件大小的基本计算单位；
8个二进制位构成1个"字节(Byte)"，即1Byte=8bit
所以1个32位二进制数占4个Byte。
答案为

试题B：卡片

题目

答案：3181

分析
打卡题

#include <bits/stdc++.h>
using namespace std;
int a[10];
bool ok(int x)  //每个数消耗卡片
{
    while(x)
    {
        int temp = x % 10;
        if(a[temp])
        {
            a[temp]--;
            x /= 10;
        }
        else
            return 0;
    }
    return 1;
}
int main()
{
    fill(a, a + 10, 2021); //总共的卡片数
    for (int i = 1;; i++)
    {
        if(ok(i))
            continue;
        else
        {
            cout << i - 1;
            break;
        }
    }
    return 0;
}

试题C：直线

题目

答案：40257

分析
一看像个数学题，可是又推不出数学公式，然后就分三种情况讨论，哈希统计个数，测试样例和自己测试的小样例都过了，不过好像数据大了，double精度不够用，因此需要调用2个坐标，求b，才能得到正确解
1.平行于y轴 直线表达式为x=？？？
2.平行于x轴 直线表达式为y=？？？
3.普通一次函数 直线表达式为y=kx+b

#include <bits/stdc++.h>
using namespace std;
set<pair<double, double> > ss; //普通的直线
set<double> dx,dy; //两种特殊的直线
struct point
{
    double x, y;
};
void solve(point a,point b)
{
    if(a.x==b.x)    //平行于y轴
        dx.insert(a.x);
    else if(a.y==b.y)    //平行于x轴
        dy.insert(a.y);
    else    //计算表达式y=kx+bb
    {
        double k = (b.y - a.y) / (b.x - a.x);
        // double bb = a.y - k * a.x;   //错误解
        //正解 运用两个点的坐标提升精度
        double bb = (a.y * b.x - a.x * b.y) / (b.x - a.x); 
        ss.insert(pair<double, double>(k, bb));
    }
}
int main()
{
    
    vector<point> v;
    for (int i = 0; i <= 19;i++)
    {
        for (int j = 0; j <= 20;j++)
        {
            point temp = {i * 1.0, j * 1.0};//转换为double
            v.push_back(temp);
        }
    }
    int len = v.size();
    for (int i = 0; i < len;i++)    //枚举所有的直线
    {
        for (int j = i + 1; j < len;j++)
        {
            solve(v[i], v[j]);
        }
    }
    cout << dx.size() + dy.size() + ss.size();  //三种直线集合个数求和
    return 0;
}

试题D：货物摆放

题目

答案：2430

分析
首先，这个数非常大，达到了1e16级别，所以直接枚举，是不可能的
题目要求3个数相乘，得到这个数，因此，这三个数必定是这个数的因子，所以我想到了首先求出这个数的所有因子。因子数求法可以参考我的文章求因子数
然后求因子复杂度只需要sqrt（n）级别，也就是1e8，这个复杂度是可以接受的，最后在求到的因字数中，枚举三个数的乘积是否等于这个数

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll n = 2021041820210418;
int main()
{
    set<ll> fac; //存放因子
    for (int i = 1; i <= sqrt(n);i++)
    {
        if(n%i==0)
        {
            fac.insert(i);
            fac.insert(n / i);
        }
    }
    vector<ll> v;  //  转存到数组里面，方便操作
    for(ll e:fac)   //foreach遍历
        v.push_back(e);
    int len = v.size();
    int cnt = 0;
    for (int i = 0; i < len;i++) //三重循环，枚举因子数乘积
        for (int j = 0; j < len;j++)
            for (int k = 0; k < len;k++)
            {
                if(v[i]*v[j]*v[k]==n)
                    cnt++;
            }
    cout << cnt;
    return 0;
}

试题E：路径

题目

答案：10266837

分析
一开始没看懂题，跳过去了，最后20分钟才想起思路，寒假刷pat的题库终于在蓝桥起作用了，有惊无险。。。
考点就是求最小公倍数和最短路径算法dijstra
推荐柳神的最短路径算法模板dfs最短路径
不过此题也可以用dp做，过程貌似更简洁

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll inf = 1e12;
int vis[2050];
ll e[2050][2050], dis[2050];
ll gcd(ll a,ll b)   //求最大公因数
{
    return a % b == 0 ? b : gcd(b, a % b);
}
ll lcm(ll a,ll b)	//求最小公倍数
{
    return a * b / gcd(a, b);
}
int main()
{
    fill(dis, dis + 2050, inf);
    fill(e[0], e[0] + 2050 * 2050, inf);
    for (int i = 1; i <= 2021;i++)
    {
        for (int j = 1; j <= 21;j++)    //21步以内有效
        {
            int k = i + j;  //i为起点，k为终点
            if(k>2021)
                break;
            e[i][k] = e[k][i] = lcm(i, k);
        }   
    }
    dis[1] = 0;
    //最短路径模板  dijstra算法
    for (int i = 1; i <= 2021;i++)
    {
        ll u = -1, minn = inf;
        for (int j = 1; j <= 2021;j++)//找到起点
        {
            if(!vis[j]&&dis[j]<minn)
            {
                minn = dis[j];
                u = j;
            }
        }
        if(u==-1)
            break;
        vis[u] = 1;
        for (int v = 1; v <= 2021;v++)
        {
            if(!vis[v])
                dis[v] = min(dis[v], e[u][v] + dis[u]);
        }
    }
    cout << dis[2021];
    return 0;
}

试题F：时间显示

题目

分析
打卡题，注意题目说法，毫秒直接舍去

#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
int main()
{
    ll n;
    int mod = 3600 * 24;//一天的秒数
    cin >> n;
    n /= 1000;	//舍去毫秒
    n %= mod;
    int h = (n / 3600) % 24;
    int m = ((n % 3600)/60)%60;
    int s = n % 60;
    printf("%02d:%02d:%02d", h, m, s);
    return 0;
}

试题G：砝码称重

题目

分析
dp题，看了5分钟没思路，跑路了

试题H：杨辉三角形

题目

分析
看到这题心就凉了，可能有数学公式，但是考试时我肯定推不出来，就直接暴力模拟了，只开了一维数组，每开辟新的一行，就复制一份，判断每个元素是否等于n
（大数据超时）：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
vector<ll> a;
int main()
{
    ll n;
    cin >> n;
    ll cnt = 2;
    if (n == 1)
        cout << 1;
    else
    {
        a.push_back(1); //第二层
        a.push_back(1); 
        while (1)
        {
            cnt++; //第cnt层
            vector<ll> temp(a); //复制上一份
            for (ll i = 1; i < cnt - 1; i++)
            {
                temp[i] = a[i] + a[i - 1];
                if (temp[i] == n) //找到了这个数
                {
                    ll ans = cnt* (cnt - 1) / 2;
                    ans += (1 + i);
                    cout << ans;
                    return 0;
                }
            }
            temp.push_back(1);  //末尾元素
            a = temp;
        }
    }
    return 0;
}

试题I：双向排序

题目

分析
直接一步步排序的，看上去太简单了，希望没有坑。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
bool cmp(int a,int b)
{
    return a > b;
}
int main()
{
    int n, m;
    cin >> n >> m;
    int a[n];
    for (int i = 0; i < n;i++)
        a[i] = i + 1;
    for (int i = 0; i < m;i++)
    {
        int p, q;
        scanf("%d %d", &p, &q);
        if(p==0)
            sort(a, a + q,cmp);
        else
            sort(a + q - 1, a + n);
    }
    for (int i = 0; i < n;i++)
    {
        printf("%d", a[i]);
        if(i!=n-1)
            printf(" ");
    }
    return 0;
}

试题J：括号序列

分析
dp，白给。输出了s长度等于1~3的答案，希望能混到测试样例。

个人总结：

第二次参加蓝桥杯（B组省赛），今年题明显比往年难了很多，考的知识面也覆盖广了。难道是蓝桥杯排名不断上升，题也跟着变了味？不过省赛总体思路还是暴力加一些基本的数学知识。这次第一题完全就是考概念。。。第一题就白给了，确实蛮打击人的。最后一次参加蓝桥了，希望不会白给。