专栏文章

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

UUNNN
P14103题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@minqz0dy
此快照首次捕获于
2025/12/02 06:55
3 个月前
此快照最后确认于
2025/12/02 06:55
3 个月前
查看原文

题意

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

思路

简单模拟题，观察到数据范围除了 nn 以外都不超过 100100，因此可以直接暴力。
对于求交集操作，我们可以遍历到一个区间后再对另一组区间进行遍历，判断是否存在交集，即判断是否存在两个正整数 i∈[1,x],j∈[1,y]i \in [1, x], j \in [1, y]，使得 lb,j≤ra,il_{b, j} \le r_{a, i} 并且 la,i≤rb,jl_{a, i} \le r_{b, j}，如果满足，那么这两个区间交集的左端点就是 max⁡{la,i,lb,j}\max\{l_{a, i}, l_{b, j}\}，右端点就是 min⁡{ra,i,rb,j}\min\{r_{a, i}, r_{b, j}\}。
对于算分操作，遍历每个最终求出交集的区间，由于区间长度为 r−l+1r - l + 1，而由于长度为 mm 时得分为 11，每增加一个长度得分额外增加 11，因此得分为 r−l+1−m+1=r−l+2−mr - l + 1 - m + 1 = r - l + 2 - m，由于该结果可能存在负数，而由题意可以得知不满 mm 时得分为 00，所以单个区间的得分为 max⁡{0,r−l+2−m}\max\{0, r - l + 2 - m\}。
注意了，题目中说的是输出 在第 nn 天结束时他们的最终得分 ，而题目对区间端点的范围并没有限制在 [1,n][1, n] 之内，所以最终计算分数时需要注意右端点越界的情况，右端点需要取 min⁡{n,ri}\min\{n, r_i\} 才可计算第 nn 天的得分。并且左端点如果大于 nn，那么遍历直接结束。

Code

CPP
#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; // 结束 (｡･ω･｡)
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...