C. Polycarp Restores Permutation

链接

[https://codeforces.com/contest/1141/problem/C]

题意

qi=pi+1−pi.给你qi让你恢复pi

每个pi都不一样

分析

就是数学吧

a1 +(a2-a1) +(a3-a1) +(a4-a1) +(a5-a1) +(a6-a1) +…+(an-a1)=a1+a2+....+an-(n-1)a1;

=n(n+1)/2-(n-1)*a1=a1+(a2-a1) +(a3-a1) +(a4-a1) +(a5-a1) +(a6-a1) +…+(an-a1)

(a2-a1) +(a3-a1) +(a4-a1) +(a5-a1) +(a6-a1) +…+(an-a1)可以用一个前缀和统计

a1=a1=( n × (n+1) / 2 -sum[n-1])/n;

在判断是否有重复的和超出范围的

看代码吧

代码

#include<bits/stdc++.h>

using namespace std;

#define ll long long

const int N=2e5+10;

ll p[N],sum[N];

bool vis[N];

ll n;

int main(){

	ios::sync_with_stdio(false);

	cin.tie(0);

	cout.tie(0);

	//freopen("in.txt","r",stdin);

	cout<<int('a')<<endl;

	while(cin>>n){

		sum[0]=0;

	for(int i=1;i<n;i++)

	{

		cin>>p[i];

		sum[i]=sum[i-1]+p[i];

	 } 

	 for(int i=1;i<n;i++)

	 sum[i]+=sum[i-1];

	 ll a1=(n*(n+1)/2-sum[n-1])/n;

	 //cout<<a1<<endl;

	if(a1<1||a1>n) cout<<-1<<endl;

	else{

		bool flag=0;

		ll last=a1;

		memset(vis,0,sizeof(vis));

		vis[last]=1;

		vector<ll> ve;

		ve.push_back(last);

		for(int i=2;i<=n;i++)

		if(last+p[i-1]>=1&&last+p[i-1]<=n&&!vis[last+p[i-1]]){

			last=last+p[i-1];

			vis[last]=1;

			ve.push_back(last);

		}

		else{

			flag=1; break;

		}

		if(flag) cout<<-1;

		else for(int i=0;i<n;i++) cout<<ve[i]<<' ';

		cout<<endl;

	}

}

	return 0;

}

巴特西

C. Polycarp Restores Permutation

链接

题意

分析

代码

最新文章

热门文章