P8902

Mikefeng · 2022-12-25 12:28:21 · 题解

[USACO22DEC] Range Reconstruction S

题目描述

Bessie 有一个数组 a_1, \cdots, a_N，其中 1 \le N \le 300 并对于所有 i 有 0 \le a_i \le 10^9。她不会告诉你数组 a 本身，但她会告诉你 a 的每个子数组的全距。也就是说，对于每对索引 i \le j，Bessie 告诉你 r_{i,j}= \max a[i \cdots j]-\min a[i \cdots j]。给定这些 r 的值，构造一个可以作为 Bessie 的原始数组的数组。你的数组中的数值应在 [−10^9,10^9] 范围内。

做法

我们发现最有用的 r 是 r_{i,i+1}，因为它可以告诉我们相邻两个数的差，于是就已经得到了 2^n 的暴力解法。

暴力显然过不去，然而我们又发现一条性质，如果我们知道相邻三个数的极差，又知道了相邻两个数的差，我们是可以断定三个数之间的相对关系的，因为假设两个数的差分别是 a,b，那么三个数的极差一定是 a+b 或 |a-b|。

所以我们先假定前两个数是第一个数更大，这样可以依次推出后面的数应该是几。

交了一发WA了。。。

这时发现如果前两个数相同，我们不能知道第三个数，因为不管第三个数更大还是更小三个数的极差都一样，所以我们推广一下做法，找到相邻的三组不一样的数，这样仍然能利用三组数的极差和相邻两组数分别的差算出答案。

代码

代码实现非常简洁。

const ll N=305;
const ll inf=1e18;
ll n,lst,minn=inf;
ll ans[N];
ll a[N][N];
int main(){
    n=read();
    F(i,1,n) F(j,i,n) a[i][j]=read();
    ans[1]=0;ans[2]=ans[1]+a[1][2];
    lst=2;
    F(i,3,n){
        if(a[lst-1][i]==a[lst-1][lst]+a[lst][i]){
            if(ans[lst]<ans[lst-1]) ans[i]=ans[lst]-a[lst][i];
            else ans[i]=ans[lst]+a[lst][i];
        }else{
            if(ans[lst]<ans[lst-1]) ans[i]=ans[lst]+a[lst][i];
            else ans[i]=ans[lst]-a[lst][i];
        }
        if(a[i-1][i]!=0) lst=i;
    }
    F(i,1,n) minn=min(minn,ans[i]);
    F(i,1,n) ans[i]-=minn;
    F(i,1,n){
        printf("%lld",ans[i]);
        if(i!=n) putchar(' ');
    }
    printf("\n");
    return 0;
}