P9094 [PA2020] Mieszanie kolorów题解

hao_416 · 2025-01-04 17:10:59 · 题解

题目传送门

题解如下：⬇️

思路：

看到这道题和旁边的标签，明显是一道差分题。（让某一区间全+，-）当时的思路就是"数字一加，判断是不是3就完事儿了？"

但是 蓝+蓝+黄，黄+蓝+蓝，黄+蓝+蓝+黄，黄+黄+黄+黄+黄+蓝......还等于绿啊！可是，这几个用数字表示出来不是3，3，3，3，而是4，5，6，7。那么，我们就不能只用一个cha[]了，就得用红，黄，蓝三个cha[]。

因此 ，我们要在每一次输入k时，要先判断他是什么颜色，然后将 那个颜色 的cha[]l - r的区间加。最后，前缀和+判断蓝黄两个cha[]有没有数据 （要有） &&红的cha[]有没有数据 (没有是正确的) 。

最终AC代码

#include<iostream>
#include<cmath>
#include<string>
#include<cstring>
#include<algorithm>

using namespace std;

const int N=1e6+5;
int n,m,l,r,k,y[N],b[N],h[N],cnt; //几个cha[]
int main(){
    cin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        cin>>l>>r>>k;
        if(k==1)//如果是黄
        {
            y[l]++;
            y[r+1]--; 
        }
        else if(k==2)//如果是蓝
        {
            b[l]++;
            b[r+1]--; 
        }
        else if(k==3)//如果是红
        {
            h[l]++;
            h[r+1]--; 
        }
    }
    for(int i=1;i<=n;i++)
    {
        y[i]+=y[i-1];//还原
        b[i]+=b[i-1];//还原
        h[i]+=h[i-1];//还原
        if(y[i]!=0&&b[i]!=0&&h[i]==0)
        {
            cnt++; 
        }
    }
    cout<<cnt;
    return 0;//别忘露.
}