ZOJ 3961 Let's Chat

传送门

给你A的区间和B的区间，然后问你重合的区间。答案就是求重合的区间长度-m+1的值。

因为数据量不大，所以就让A的每个区间都对B的区间进行匹配，然后求和就可以了。这就是一种暴力。

#include<bits/stdc++.h>
using namespace std;
const int maxn = 150;
typedef pair<int,int> pq;
pq x[maxn],y[maxn];
int main()
{
#ifndef ONLINE_JUDGE
    freopen("in", "r", stdin);
#endif
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int t,n,m,p,q;
    cin >> t;
    while(t--)
    {
        int ans = 0,k,l,r;
        cin >> n >> m >> p >> q;
        for(int i = 0;i < p; i++)
            cin >> x[i].first >> x[i].second;
        for(int i = 0;i < q; i++)
            cin >> y[i].first >> y[i].second;
        for(int i = 0;i < p; i++)
        {
            if(x[i].second - x[i].first + 1 < m)
                continue;
            for(int j = 0;j < q; j++)
            {

                if(y[j].second - y[j].first + 1 < m)
                    continue;
//                cout << ans << "*" << endl;
                l = max(x[i].first,y[j].first);
                r = min(x[i].second,y[j].second);
                k = r - l + 1;
                if(k >= m)
                    ans += k - m + 1;
            }
        }
        cout << ans << endl;
    }
    return 0;
}