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組省賽），今年題明顯比往年難了很多，考的知識面也覆寫廣了，難道是藍橋杯排名不斷上升，題也跟著變了味？不過省賽總體思路還是暴力加一些基本的數學知識，這次第一題完全就是考概念，，，第一題就白給了，確實蠻打擊人的，最后一次參加藍橋了，希望不會白給，