题解：P9426 [蓝桥杯 2023 国 B] 抓娃娃

· · 题解

大致思路：

此题的关键在于我们不难发现，如果我们选择了线段的一半及以上，无论从左往右，还是从右往左，抑或中间断开，它都必定包含了这条线段的中点。那么我们就可以在输入的时候，记录它的中点并放在数组里面，然后进行一个简单的前缀和预处理，最后统计并输出一个区间框住的线段即可。

细节处理：

此题也没什么太大的坑，就是在实现的时候可能会出现中点是个小数的情况，但是也很好处理，比较不动脑子的方法就是判断下如果中点的值除以 2 余 1，那么就把它加 1，否则就不变。还有就是数组大小，一定看好数据范围，不要开大也不要开小。有点啰嗦了，如果觉得这里说得太复杂，请直接跳过看代码。

代码：

#include <bits/stdc++.h>
using namespace std;
int a[1000005];
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n , m;
    cin >> n >> m;
    for(int i = 1 ; i <= n ; ++i) {
        int l , r;
        cin >> l >> r;
        if((l + r) % 2 == 1) a[(l + r) / 2 + 1]++;
        else a[(l + r) / 2]++;
    }
    for(int i = 1 ; i <= 1e6 ; ++i){
        a[i] += a[i - 1];
    }
    for(int i = 1 ; i <= m ; ++i){
        int l , r;
        cin >> l >> r;
        cout << a[r] - a[l - 1] << endl;
    }
    return 0;
}

最后:

希望这篇题解能帮到各位，因为这道题没有测试点，所以大家都不知道自己正确与否，如果认为题解有误，欢迎指正，不胜感激。