每日“二”题

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

目录

• 每日“二”题
  • A
  • B

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;
}