AtCoder ABC326

最近在準備資訊學科能力競賽區賽，剛好看到通知說今天晚上有一場 ABC
剛好有空就想說來打打看。
這次解出三題，對我來說算是一大突破，所以就乾脆寫個心得記錄一下 :D

注意事項

以下解法均不是官方解、正常解法。
都是我於賽中想出來的做法，所以存在相當多不完美的地方。
製作此筆記僅是紀錄學習過程，並非題解分享。

pA - 2UP3DOWN

題意

有座層樓的建築物
使用樓梯來往上走兩層樓以內，或者是往下走三層樓以內。
否則，就使用電梯。
問你是否會使用樓梯來從這第層樓移動到第層樓

想法：

先去比較和的大小，在去判斷是否合乎往上層內、往下層內的條件

#include <bits/stdc++.h>
#define int long long
#define F first
#define S second
#define endl "\n"
#define io ios_base::sync_with_stdio(0),cin.tie(0);

using namespace std;

signed main(void) {
    io;
    
    int x,y; cin >> x >> y;

    if(x > y) {
        if(x-y <= 3) cout << "Yes\n";
        else cout << "No\n";
    } else {
        if(y-x <= 2) cout << "Yes\n";
        else cout << "No\n";
    }
}

pB - 326-like Numbers

這題蠻有趣的 xD

題意

給你一個數字，判斷他是否為 326-like 的數字
如果是，則輸出的 326-like 數字

326-like：個位數百位數十位數

想法：

將拆分成百位數,十位數,個位數
然後去計算是否為
接著組合成一個新的數字
判斷是否
如果小於，我們要再去找下一個 326-like 的數字，且是的，
否則直接輸出即可。

但這題其實會有一種情況是寫特判會很麻煩的，
所以正解的話其實是要用迴圈去解出的。

但我這題沒有用迴圈去解💀
我是直接用去硬幹這題我太笨。
反正最多也才，就果斷直接用特判 💀

~~但也因為這樣直接讓我 WA 了次~~

#include <bits/stdc++.h>
#define int long long
#define F first
#define S second
#define endl "\n"
#define io ios_base::sync_with_stdio(0),cin.tie(0);

using namespace std;

signed main(void) {
    io;
    
    int n; cin >> n;
    int tt = n/10;
    int p = tt/10, t = tt%10, su = n%10;

    int newN = 0;

    if(p*t == su) cout << n << endl;
    else {
        newN += (p * 100 + t * 10) + p*t;
        su = newN%10;
        if(newN < n || su != p*t) {
            // 找下一個比它大的
            if(p >= 5 && p != 9 && t != 0) {
                p+=1;
                t=0;
                newN = (p * 100 + t * 10) + p*t;
            } else {
                t+=1;
                newN = (p * 100 + t * 10) + p*t;
                su = newN % 10;
                if(p*t != su) {
                    p+=1;
                    t = 0;
                    newN = (p * 100 + t * 10) + p*t;
                }
            }
        }
        cout << newN << endl;
    }
}

喜提 WA * 7，第次後都是最後一筆測資沒過，下次我會乖乖用迴圈

pC - Peak

題意

在數線上放了個禮物，每個禮物的位置為。
你需要選擇一段長度為的數線區間，並取得其中盡可能多的禮物。

想法：

二分搜。

我用一張圖解釋，裡面的數字來自於範例測資1

當我們定義右界時，我們將它設為（目前處理的禮物位置）加上區間長度
這代表了我們希望在數線上尋找的右區間的結束位置（右界）。

使用 lower_bound 函數，我們可以找到位於陣列中的數字中，第一個大於等於的數字。
這代表在我們的區間範圍內，所有不小於的數字都是符合我們的條件的。
在這筆範例測資中，於範圍內找到、、、這四個數字。
它們的位置都在區間內。
表示包含在區間內的禮物，總共有個。

#include <bits/stdc++.h>
#define int long long
#define F first
#define S second
#define endl "\n"
#define io ios_base::sync_with_stdio(0),cin.tie(0);

using namespace std;

signed main(void) {
    io;
    
    int n,m; cin >> n >> m;
    vector<int> v(n);

    for(int i = 0; i < n; ++i){
        cin >> v[i];
    }

    sort(v.begin(), v.end());

    int gift = 0;
    int l = 0,r=0;
    for(int i = 0; i < n; ++ i) {
        r = v[i] + m;
        int j = lower_bound(v.begin(), v.end(), r) - v.begin();
        int ac = j - i;
        gift = max(gift, ac);
    }
    cout << gift << endl;
}

備註：

lower_bound：找出vector中「大於或等於」val的「最小值」的位置：
1
auto it = lower_bound(v.begin(), v.end(), val);
upper_bound：找出vector中「大於」val的「最小值」的位置：
1
auto it = upper_bound(v.begin(), v.end(), val);

出處：Yui Huang 演算法學習筆記

心得

蠻有趣的比賽，能解到第三題真的心情很好

但第二題老實說是僥倖過的，因為沒有用它真正的迴圈解法
如果今天題目再變的更不一樣說不定就解不出來了😭

YuDong's Daily

AtCoder ABC326 解題心得

AtCoder ABC326

pA - 2UP3DOWN

想法：

pB - 326-like Numbers

想法：

pC - Peak

想法：

心得