#19223: 對於


2qbingxuan (程式初學者)

學校 : 臺北市立建國高級中學
編號 : 58274
來源 : [114.32.125.176]
最後登入時間 :
2024-04-01 20:23:17
b836. kevin戀愛攻略系列題-2 說好的霸王花呢?? | From: [210.71.78.241] | 發表日期 : 2019-09-17 13:53

最後1%有多筆詢問,間接禁止naive的迴圈作法

採用二分搜尋找「Kevin要拔幾次花瓣才能拔完」,因為Kevin拔了k次花瓣所拔的花瓣數可以很快求得

每筆詢問只需要O(logn),3ms內跑完,完全不須擔心TLE

 

#include <bits/stdc++.h>

using namespace std;

long long n,m;
long long sum(long long k) {
    // 1 + (1+m) + (1+m*2) + ... + (1+m*(k-1))
    return k + m*(k*(k-1)/2);
}
signed main() {
    ios_base::sync_with_stdio(0),cin.tie(0);
    while(cin >> n >> m) {
        long long s = 1, x = 0;
        while(sum(s) < n) s *= 2;
        while(s) {
            if(n >= sum(x+s)) x += s;
            s /= 2;
        }
        n -= sum(x);
        if(n == 0)
            cout << "Go Kevin!!\n";
        else
           cout << "No Stop!!\n";
    }
}

當然也可以用判別式O(1)判斷

 
ZeroJudge Forum