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

原文：https://www.cnblogs.com/mch5201314/p/10572627.html