文档章节

$CF1141C Polycarp Restores Permutation$

o
 osc_fmg49rzg
发布于 2019/03/20 12:43
字数 369
阅读 7
收藏 0

精选30+云产品,助力企业轻松上云!>>>

$problem$

这题的大致意思就是已知数值差值 求1-n的排列

如果能构成排列 则输出这个排列。如果不能则输出-1
排列的值都是 大于1 而小于n的 而且没有相同的数字。

这题最关键的是 怎么输出这个序列 有的是存在负数的。

那么 考虑一下排列都是从1到n的对不对。 取序列的最小值 然后用$1 - Min$即是整个序列应该加上的数值。 首先考虑判重。 用数组 或者用$Map$ $or$ $Set$ 。 都是不错的方法。

#include <bits/stdc++.h>
using namespace std;
typedef long long LL ;
inline LL In() { LL res(0),f(1); register char c ;
    while(isspace(c=getchar())) ; c == '-'? f = -1 , c = getchar() : f = 1 ;
    while(res = (res << 1) + (res << 3) + (c & 15) , isdigit(c=getchar())) ; return res * f ;
}
int n ;
int p[200000+5] ;
int res[200000+5] ;
set<int> s;//判重
signed main(){
    n = In() ;
    for(register int i=1;i<=n-1;i++) p[i] = In() ;
    res[1] = 0 ;
    for(register int i=2;i<=n;i++) res[i] = res[i-1] + p[i-1] ;//计算前缀和
    int Min = 0x7f7f7f7f;
    for(register int i=1;i<=n;i++){
        Min = min(res[i],Min);
        if(s.count(res[i])==0) s.insert(res[i]) ;//插入数值
        else {
            cout << -1 << endl ;//如果存在重复的数值则不可能构成排列。
            return 0 ;
        }
    }
    //cout << Min << endl ;
    int c = 1 - Min ;
    bool f = false;
    for(register int i=1;i<=n;i++) {
        if(res[i] + c > n) {//如果大于n则不能构成 也是输出-1
            cout << -1 << endl ;
            return 0 ;
        }
    }
    
    for(register int i=1;i<=n;i++) {
        cout << res[i] + c << ' ' ;
    }
    return 0 ;
}
o
粉丝 0
博文 500
码字总数 0
作品 0
私信 提问
加载中
请先登录后再评论。
CF 1141C Polycarp Restores Permutation

Description An array of integers p1,p2,…,pnp1,p2,…,pn is called a permutation if it contains each number from 11 to nn exactly once. For example, the following arrays are perm......

osc_8wyy9cyu
2019/03/26
3
0
Codeforces Round #547 (Div. 3)

A. Game 23 Description Polycarp plays "Game 23". Initially he has a number 𝑛n and his goal is to transform it to 𝑚m. In one move, he can multiply 𝑛n by 22 or multiply ?......

osc_fa164jpo
2019/03/21
6
0
C. Polycarp Restores Permutation

链接:https://codeforces.com/contest/1141/problem/C 题意: 给n-1个数, qi=pi+1−pi p为1-n的排列序列 q为给的序列。 根据q求出p, 求不出时为-1。 思路: 另p数组首个为0.求出p数组,再...

osc_fa164jpo
2019/03/21
1
0
Codeforces Round #547 (Div. 3)<!--部分题解-->

[toc] <hr><font size=3 color=red>没有了调试就没办法写程序了...........</font><hr> A - Game 23(简单数学) :smile:<font size=3 color=blue>题目链接:</font>http://codeforces.com/con......

osc_n6euf5h6
2019/03/20
3
0
Codeforces Round #547 (Div. 3) 题解

Codeforces Round #547 (Div. 3) 题目链接:https://codeforces.com/contest/1141 A,B咕咕了... C. Polycarp Restores Permutation 题意: 有一个n的排列,但现在只给出相邻两位的差,问原排...

osc_kfnbvkb9
2019/03/21
3
0

没有更多内容

加载失败,请刷新页面

加载更多

macz技巧分享—macOS高端使用技巧

Macos 的占有量不如 Windows,两者之间当操作方式也有很大的不同,当很多人熱悉 Windows 的操作之后,再接触 macos,觉得难上手,其实是习惯问题。如果你学习一些技巧,会觉得 macos 其实也不...

mac小叮当
19分钟前
11
0
手把手教你如何用黑白显示器显示彩色!

来源:大数据文摘 本文约1000字,建议阅读6分钟。 本文为你介绍如何通过黑白显示器上也能显示出彩色。 原来在黑白显示器上也能显示出彩色啊!通过在监视器上覆盖拜耳滤色镜,并拼接彩色图像,...

osc_jklrr90y
20分钟前
13
0
key-value结构排序:给定一个字符串,统计每个字符出现频率,先按value降序,再按key升序

对于key-value结构的排序 第一种:lambda表达式 第二种:函数 第三种:类对()的重载,仿函数形式 #include <iostream>#include <vector>#include <unordered_map>#include <string>#in......

osc_gwtkg2dc
21分钟前
0
0
BlockChain:2020年7月10日世界人工智能大会WAIC《链智未来 赋能产业区块链主题论坛——2020全球区块链创新50强》

BlockChain:2020年7月10日世界人工智能大会WAIC《链智未来 赋能产业区块链主题论坛——2020全球区块链创新50强》 目录 世界人工智能大会WAIC《链智未来 赋能产业区块链主题论坛——2020全球...

osc_vew1u0h0
22分钟前
0
0
BlockChain:2020年7月10日世界人工智能大会WAIC《链智未来 赋能产业区块链主题论坛》(三)

BlockChain:2020年7月10日世界人工智能大会WAIC《链智未来 赋能产业区块链主题论坛》(三) 目录 2020年7月10日世界人工智能大会WAIC《链智未来 赋能产业区块链主题论坛》 演讲嘉宾 演讲内容 ...

osc_8o71811p
23分钟前
0
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部