P9947 题解

Luogu_916767 · 2024-01-09 22:21:08 · 题解

In Luogu

题目大意

给出一个 n-1 位的序列 b_{1},b_{1},b_{1},\dots,b_{n-1}。求一个序列 a，使 a_{i} + a_{i+1} = b_{i}。

思路分析

观察题目数据范围，可以发现其实 n 并不是特别大。不难发现，只要我们知道这个序列中任何一位，就可以推出整个序列。所以，我们可以枚举第一位，并验证是否符合题目要求，最后只要找到一个符合要求的，直接输出答案就好（保证存在至少一个满足条件的 a）。

具体实现

除了判断是否合法之外就没什么难的了吧？

判断是否合法

bool flag = 1;
for(int j = 1; j <= n; j ++ ){
    if(!mp[j]){
        flag = 0;
        break;
    }
}
if(flag){
    for(int j = 1; j <= n; j ++ ){
        cout<<ans[j]<<" ";
    }
    return 0;
}

提示

不要忘记每次检查完之后要把 mp 全部清空。

综上。

Code

#include<bits/stdc++.h>

using namespace std;

int n;
int a[1001];
int ans[1001];
map<int,bool> mp;

int main(){
    cin>>n;
    for(int i = 1; i < n; i ++ ){
        cin>>a[i];
    }
    for(int i = 1; i < a[1]; i ++ ){
        ans[1] = i;
        mp[i] = 1;
        for(int j = 2; j <= n; j ++ ){
            ans[j] = a[j-1] - ans[j-1];
            mp[ans[j]] = 1;
        }
        bool flag = 1;
        for(int j = 1; j <= n; j ++ ){
            if(!mp[j]){
                flag = 0;
                break;
            }
        }
        if(flag){
            for(int j = 1; j <= n; j ++ ){
                cout<<ans[j]<<" ";
            }
            return 0;
        }
        for(int j = 1; j <= n; j ++ ){
            mp[j] = 0;
        }
    }
}