每日“二”题

十年OI一场空,不开longlong见祖宗

目录

A

题解:

最值问题,一个条件在变,考虑使用二分:
我们每次查找一个可切的最大巧克力,二分判断能不能这么切即可。

C++代码

void solve() {
    int n, k, l = 1, r = 0, ans;
    cin >> n >> k;
    vector<pair<int, int>>qwq(n);
    for(auto &x : qwq) {
        cin >> x.first >> x.second;
        int mx = max(x.first, x.second);
        r = max(mx, r); //确定一个二分最大值,这里其实也可以给一个很大的值减少代码量
    }
    while(l <= r) { //二分答案
        int mid = l + r >> 1;
        //check() 按一般背的板子来是写一个 check() 我这里为了方便直接写这里面了
        int tot = 0;
        for(auto x : qwq)tot += (x.first / mid) * (x.second / mid);
        if(tot < k)r = mid - 1;
        //check()截止
        else l = mid + 1;
    }
    cout << r;
}

B

题解:

我们创建一个前缀和数组,接着看一下里面同余的有几个数即可
(为什么同余就说明有倍数呢?这是因为:
如果两数之间和不为k倍数,则余数一定不同,容易可得自行证明吧XD

C++代码

void solve() {
    ll n, k, i, j,ans=0;
    cin >> n >> k;
    vector<ll>qwq(n + 1); //前缀和数组
    vector<ll>qaq(k + 1); //等效哈希表->map
    for(i = 1;i <= n;++i) {
        cin >> qwq[i];
        //qwq[i] %= k; 这个并不重要,可以省略
        qwq[i] += qwq[i - 1]; //前缀和,解题关键1
    }
    // 试了下暴力,并不能过
    for(i = 0;i <= n;++i)ans += qaq[qwq[i] % k]++; //同余,解题关键2
    cout << ans;
}