Link

USACO 2022 December Contest, Silver Problem 3. Range Reconstruction

Question

\(r_{l,r}\) 表示 \(max[l,r]-min[l,r]\)

给出所有的 \(r_{i,j}\) 求一个可行的序列

Solution

我们可以发现两个性质，就是这个题目只记录插值

如果一个序列满足，把这个序列每个数加上或减去一个常数，都满足，所以我们可以把 \(a_1\) 强制设为 \(0\)
如果一个序列满足，把整个序列每个数变成自己的相反数，也满足

考虑到 \(N\) 比较小，那么我们可以从 \(a_1=0\) 开始搜索，分别在 \(a_{i+1}\) 处试着放 \(a_i+r_{i,i+1}\) 或者 \(a_i-r_{i,i+1}\) 每放一个看一下是否满足条件

#include<bits/stdc++.h>
using namespace std;
const int maxn=305;
const int INF=2e9;
typedef long long LL;
int N;
int ans[maxn],a[maxn][maxn];
int Max[maxn][maxn],Min[maxn][maxn];
void dfs(int pos){
    if(pos==N) {
        for(int i=1;i<=N;i++)
            printf("%d%c",ans[i],i==N?'\n':' ');
        exit(0);
    }
    int now_max=-INF,now_min=INF,flg=1;
    
    ans[pos+1]=ans[pos]+a[pos][pos+1];
    now_max=now_min=ans[pos+1];
    for(int i=pos;i;i--){
        now_max=max(now_max,ans[i]);now_min=min(now_min,ans[i]);
        if(now_max-now_min!=a[i][pos+1]) {flg=0;break;}
    }

    if(flg)dfs(pos+1);
    
    flg=1;
    ans[pos+1]=ans[pos]-a[pos][pos+1];
    now_max=now_min=ans[pos+1];
    for(int i=pos;i;i--){
        now_max=max(now_max,ans[i]);now_min=min(now_min,ans[i]);
        if(now_max-now_min!=a[i][pos+1]) {flg=0;break;}
    }
    if(flg)dfs(pos+1);
}
int main(){
    cin>>N;
    for(int i=1;i<=N;i++)
    for(int j=1;j<=N;j++){
        if(i>j) a[i][j]=0;
        else cin>>a[i][j];
    }
    ans[1]=0;
    dfs(1);
    return 0;
}