题解：P14103 [ZJCPC 2017] Let's Chat

· · 题解

题意

给定两组区间，第一组有 x 个区间，第二组有 y 个区间，将这几个存在交集的区间的交集相并后，对于每个区间，若该区间长度为 m，那么该区间得分为 1，若长度大于 m，每增加一个长度就多加 1 分。问最终的总分。

思路

简单模拟题，观察到数据范围除了 n 以外都不超过 100，因此可以直接暴力。

对于求交集操作，我们可以遍历到一个区间后再对另一组区间进行遍历，判断是否存在交集，即判断是否存在两个正整数 i \in [1, x], j \in [1, y]，使得 l_{b, j} \le r_{a, i} 并且 l_{a, i} \le r_{b, j}，如果满足，那么这两个区间交集的左端点就是 \max\{l_{a, i}, l_{b, j}\}，右端点就是 \min\{r_{a, i}, r_{b, j}\}。

对于算分操作，遍历每个最终求出交集的区间，由于区间长度为 r - l + 1，而由于长度为 m 时得分为 1，每增加一个长度得分额外增加 1，因此得分为 r - l + 1 - m + 1 = r - l + 2 - m，由于该结果可能存在负数，而由题意可以得知不满 m 时得分为 0，所以单个区间的得分为 \max\{0, r - l + 2 - m\}。

注意了，题目中说的是输出 在第 n 天结束时他们的最终得分 ，而题目对区间端点的范围并没有限制在 [1, n] 之内，所以最终计算分数时需要注意右端点越界的情况，右端点需要取 \min\{n, r_i\} 才可计算第 n 天的得分。并且左端点如果大于 n，那么遍历直接结束。

Code

#include <iostream>
#include <cstdio>
using namespace std;
int t, n, m, x, y, len = 0, ans = 0;
struct node{
    int l, r;
};
node qj1[205], qj2[205], nq[405];
int main()
{
    scanf("%d", &t);
    while(t--){
        len = 0;
        ans = 0;
        for(int i = 0;i < 405;i++){
            if(i < 205LL){
                qj1[i].l = 0;
                qj1[i].r = 0;
                qj2[i].l = 0;
                qj2[i].r = 0;
            }
            nq[i].l = 0;
            nq[i].r = 0;
        } // 以上均为初始化操作
        scanf("%d%d%d%d", &n, &m, &x, &y);
        for(int i = 1;i <= x;i++) scanf("%d%d", &qj1[i].l, &qj1[i].r);
        for(int i = 1;i <= y;i++) scanf("%d%d", &qj2[i].l, &qj2[i].r);
        for(int i = 1;i <= x;i++){
            for(int j = 1;j <= y;j++){
                if(qj2[j].l <= qj1[i].r && qj2[j].r >= qj1[i].l){ // 存在交集
                    len++;
                    nq[len].l = max(qj2[j].l, qj1[i].l);
                    nq[len].r = min(qj2[j].r, qj1[i].r); // 存储交集
                }
            }
        }
        for(int i = 1;i <= len;i++){
            if(nq[i].l > n) break; // 左端点越界，循环结束
            int scr = min(n, nq[i].r) - nq[i].l + 2 - m; // 算分，注意右端点越界情况
            int tot = max(0, scr); // 最终得分
            ans = ans + tot; // 累加
        }
        printf("%d\n", ans); // 输出
    }
    return 0; // 结束 (｡･ω･｡)
}