---

D. Prefix Permutation Sums

原创 于 2023-09-14 13:40:45 发布 · 粉丝可见 · 214 阅读 · 0 · 0 · 本内容遵循CC 4.0 BY-SA版权协议 版权声明：本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。 GEO检测 · 编辑
文章链接：https://blog.csdn.net/hacker_51/article/details/132790615

题目：

样例：

cobol<br/>12<br/>5<br/>6 8 12 15<br/>5<br/>1 6 8 15<br/>4<br/>1 2 100<br/>4<br/>1 3 6<br/>2<br/>2<br/>3<br/>1 2<br/>4<br/>3 7 10<br/>5<br/>5 44 46 50<br/>4<br/>1 9 10<br/>5<br/>13 21 36 42<br/>5<br/>1 2 3 1000000000000000000<br/>9<br/>9 11 12 20 25 28 30 33<br/>

YES YES NO YES YES NO YES NO NO NO NO NO

思路：

数学问题，根据前缀和与 排列1 ~ n 之间的关系来推导。

代码详解如下：

#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
#include <set>
#include <unordered_map>
#define endl '\n'
#define int long long
#define YES puts("YES")
#define NO puts("NO")
#define umap unordered_map
#pragma GCC optimize(3,"Ofast","inline")
#define ___G std::ios::sync_with_stdio(false),cin.tie(0), cout.tie(0)
using namespace std;
const int N = 2e6 + 10;

inline void solve()
{
	int n;
	cin >> n;
	
	int s = (1 + n)*n / 2;	// 排列 1 ~ n 的前n项和
	
	// 去重操作，由于我们的排列是1 ~ n 不会有多余的元素
	set<int>b;
	
	int x,r = 0;	// 这里的 x 是输入的当前前缀和元素，r 是记录上一个元素
	for(int i = 1;i < n;++i)
	{
		cin >> x;
		
		// 当前的前缀和减去上一个的前缀和，
		// 得到可能的 原来 数组 元素a 
		// 存储好所得的结果
		if(x - r <= n)
		{
			b.insert(x - r);
		}
		
		r = x;	// 更新上一个元素
	}
	
	// 由于我们是知道 n - 1 个前缀和元素，
	// 所以当我们还原 a 元素，就会得到 n - 2 个可能的 a 元素
	// 所以 b.size() == n - 2 又因为倘若我们最后的前缀和元素 x != s
	// 那么排列一定有可能推出来，因为前面肯定会丢失，
	// 当我们丢失的，只要是有一个它们的相隔超过 n 于是得到的是 (n - 1) - 2 
	// 然后当我们 x != s 的时候 n - 1 + 1 - 2 == n - 2
	if(b.size() == n - 2 + (x != s)) YES;
	else NO;
}


signed main()
{
//	freopen("a.txt", "r", stdin);
	___G;
	int _t = 1;
	cin >> _t;
	while (_t--)
	{
		solve();
	}

	return 0;
}

最后提交：