Friedforks's blog

Silver: Range Reconstruction

[P8902 USACO22DEC] Range Reconstruction S - 洛谷

这道构造题只要想清楚其实还是比较好做的。(但是如果没想出来就容易绷不住).对于任何的一个a[i],它都可以是: diff[i-1][1]\pm a[i-1]的。所以现在的问题就是，我们如何确定是+还是-。

对于这个问题, 如果用暴力，就是O(2^N)，非常爆炸。

我们可以考虑从后往前推：先选取+的情况，然后检测是否有效。如果无效，就选择-。关键的问题是如何检测是否有效

首先，在测试样例#4 中，我们可以发现：如果我们从后往前推(a[n-1]->a[0])，可以在每一个i都都选用之前的范围，也就是diff[i][0~~N-i]，对a[i~~N]中的max-min进行检验。以下是核心代码：

// given that at position i:
int current_max=INT_MIN;
int current_min=INT_MAX;
for(int j=i;j<n;j++){
    current_max=max(current_max,a[j]);
    current_min=min(current_min,a[j]);
    if(current_max-current_min!=diff[i][j-i]){'
        // invalid
    }
}
// valid for every case

通过这个步骤，我们就可以从后往前推了

//
// Created by Chixiyu on 12/3/2023.
// Range reconstruction s (construction)

#include <bits/stdc++.h>
using namespace std;

int main(){
    //input
    int n;
    cin>>n;
    int** diff=new int*[n];
    for(int i=0;i<n;i++){
        diff[i]=new int[n];
    }
    vector<int> a(n,0);
    for(int i=0;i<n;i++){
        for(int j=0;j<n-i;j++){
            cin>>diff[i][j];
        }
    }

    for(int i=n-2;i>=0;i--){// inverse iteration
        auto check=[&]()->bool{
            int mx=INT_MIN;
            int mn=INT_MAX;
            for(int j=i;j<n;j++) {
                mx=max(mx,a[j]);
                mn=min(mn,a[j]);
                if((mx-mn)!=diff[i][j-i]){
                    return false;

                }
            }
            return true;
        };
        // 1. put it in to check if valid
        a[i]=a[i+1]+diff[i][1];
        if(!check())// not valid
            a[i]=a[i+1]-diff[i][1];// the other way round
    }
    for (const auto &item: a) {
        cout<<item<<' ';
    }
}

Silver: Range Reconstruction

Silver: Range Reconstruction

评论