自动搬运

查看原文

来自洛谷，原作者为

	Luogu_916767 Florr.io

搬运于2025-08-24 22:53:17，当前版本为作者最后更新于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;
		}
	}
}