solution-P2294

luqyou · 2023-02-26 09:44:00 · 题解

提供一种不一样的思路。

我们可以根据读入的区间和来算出一些区间的和。如果跟已知冲突，那么输出 false，否则输出 true。

考虑如何来算出区间和。

每次我们读入的区间 [l,r] 会把区间 [1,n] 分成 3 个区间：[1,l)，[l,r] 以及 (r,n] 。

我们令 s_{i,j} 为区间 [i,j] 的和，那么用循环 i 遍历这三个区间。

分类讨论：

• 若 $s_{i,r}$，$s_{i,l-1}$ 都已知，则检查 $s_{i,l-1}+s_{l,r}$ 是否等于 $s_{i,r}$，如果不是则返回 `false`； 若 $s_{i,r}$ 未知，$s_{i,l-1}$ 已知，则 $s_{i,r}=s_{i,l-1}+s_{l,r}$； 若 $s_{i,r}$ 已知，$s_{i,l-1}$ 未知，则 $s_{i,l-1}=s_{i,r}-s_{l,r}$。
• 若 $s_{l,i}$，$s_{i+1,r}$ 都已知，则检查 $s_{l,i}+s_{i+1,r}$ 是否等于 $s_{l,r}$，如果不是则返回 `false`； 若 $s_{l,i}$ 未知，$s_{i+1,r}$ 已知，则 $s_{l,i}=s_{l,r}-s_{i+1,r}$； 若 $s_{l,i}$ 已知，$s_{i+1,r}$ 未知，则 $s_{i+1,r}=s_{l,r}-s_{l,i}$。
• 若 $s_{r+1,i}$，$s_{l,i}$ 都已知，则检查 $s_{l,r}+s_{r+1,i}$ 是否等于 $s_{l,i}$，如果不是则返回 `false`； 若 $s_{r+1,i}$ 未知，$s_{l,i}$ 已知，则 $s_{r+1,i}=s_{l,i}-s_{l,r}$； 若 $s_{r+1,i}$ 已知，$s_{l,i}$ 未知，则 $s_{l,i}=s_{l,r}+s_{r+1,i}$。

于是我们就可以这样判断出来了。

代码

#include<bits/stdc++.h>
using namespace std;
int t,n,m,s[101][101];
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    cin>>t;
    while(t--){
        memset(s,0x7f,sizeof s);
        cin>>n>>m;
        bool ok=1;
        for(int i=1;i<=m;i++){
            int l,r,v;
            cin>>l>>r>>v;
            s[l][r]=v;
         //一段区间=0x7f7f7f7f代表这段区间未知
            for(int j=r+1;j<=n;j++){//情况3
                if(s[r+1][j]!=0x7f7f7f7f&&s[l][j]!=0x7f7f7f7f){
                    if(s[l][r]+s[r+1][j]!=s[l][j]){
                        ok=0;
                    }
                }
                if(s[r+1][j]==0x7f7f7f7f&&s[l][j]!=0x7f7f7f7f){
                    s[r+1][j]=s[l][j]-s[l][r];
                }
                if(s[r+1][j]!=0x7f7f7f7f&&s[l][j]==0x7f7f7f7f){
                    s[l][j]=s[l][r]+s[r+1][j];
                }
            }
            for(int j=l-1;j>=1;j--){//情况1
                if(s[j][l-1]!=0x7f7f7f7f&&s[j][r]!=0x7f7f7f7f){
                    if(s[l][r]+s[j][l-1]!=s[j][r]){
                        ok=0;
                    }
                }
                if(s[j][l-1]==0x7f7f7f7f&&s[j][r]!=0x7f7f7f7f){
                    s[j][l-1]=s[j][r]-s[l][r];
                }
                if(s[j][l-1]!=0x7f7f7f7f&&s[j][r]==0x7f7f7f7f){
                    s[j][r]=s[l][r]+s[j][l-1];
                }
            }
            for(int j=r;j>=l;j--){//情况2
                if(s[l][j]!=0x7f7f7f7f&&s[j+1][r]!=0x7f7f7f7f){
                    if(s[l][j]+s[j+1][r]!=s[l][r]){
                        ok=0;
                    }
                }
                if(s[l][j]==0x7f7f7f7f&&s[j+1][r]!=0x7f7f7f7f){
                    s[l][j]=s[l][r]-s[j+1][r];
                }
                if(s[l][j]!=0x7f7f7f7f&&s[j+1][r]==0x7f7f7f7f){
                    s[j+1][r]=s[l][r]-s[l][j];
                }
            }
        }
        if(ok) cout<<"true"<<endl;
        else cout<<"false"<<endl;
    }
    return 0;
}