首页 > 其他分享 >题解 CF1739B

题解 CF1739B

时间:2023-02-16 16:58:37浏览次数:46  
标签:CF1739B 非负 int 题解 差分 整数 序列

题目大意:

有一个非负整数序列 \(A\),定义序列 \(D\) 是序列 \(A\) 的绝对值差分序列,问给定序列 \(D\),能否求出唯一的序列 \(A\),若不能,输出 \(-1\),否则输出序列 \(A\)。

题目分析:

因为属于差分序列,所以我们不难得出序列 \(D\) 的前缀和序列 \(S\) 就是序列 \(A\) 的一种。

那么不能得出唯一解得情况就很好想了,如果 \(S_{i-1}+(-D_i) \ge 0\),那么就说明有多个序列 \(A\),理由如下:

因为 \(D_i\) 是 \(A_{i-1}-A_i\) 的绝对值,所以原差分序列中 \(D_i\) 的位置可正可负,如果 \(S_{i-1}+(-D_i) < 0\),则说明了原差分序列上 \(D_i\) 的位置肯定为非负整数(因为序列 \(A\) 是由非负整数构成的),反之则说明原差分序列上 \(D_i\) 的位置的正负性不影响序列 \(A\) 是一个非负整数序列,故此时序列 \(A\) 有多种。

代码实现:

#include <bits/stdc++.h>
using namespace std;
int main() {
    int T;
    cin >> T;

    while (T--) {
        int n;
        int d[200] = {};
        cin >> n;

        for (int i = 1; i <= n; i++)
            cin >> d[i];

        bool inc = 1;
        int a[200] = {};
        a[1] = d[1];

        for (int i = 2; i <= n; i++)
            a[i] = a[i - 1] + d[i];

        for (int i = 2; i <= n; i++) {
            if (a[i - 1] >= d[i] && d[i]) {
                cout << -1 << endl;
                inc = 0;
                break;
            }
        }

        if (!inc)
            continue;

        for (int i = 1; i <= n; i++)
            cout << a[i] << ' ';

        cout << endl;
    }

    return 0;
}

标签:CF1739B,非负,int,题解,差分,整数,序列
From: https://www.cnblogs.com/larry76/p/17127344.html

相关文章

  • 题解 CF1401C
    题目大意:给定一序列\(A\),定义当且仅当\(\gcd(a_i,a_j)=a_{min}\)时,元素\(a_i\)和\(a_j\)可以交换。问当前给定的序列\(A\)能否转化为非严格单调递增的序列。题......
  • 题解 CF1292A
    题目大意:给你\(2\timesn\)的迷宫,初始时没有任何障碍,给定\(q\)次询问,每次询问给予坐标\((x,y)\),问将坐标\((x,y)\)反转状态(即无障碍变有障碍,有障碍变无障碍)后,该迷......
  • 题解 CF916C
    题目大意:要求构造一张图,并让该图满足以下条件:有\(n\)个点,\(m\)条边。每条边的边权范围是\([1,10^9]\)。图中从\(1\)到\(n\)的最短路径长度是个质数。最小生......
  • 题解 CF277A
    题目大意:有\(n\)名员工,一共有\(m\)种语言,每名员工都会其中\(k_i\)种语言(\(m\ge\boldsymbol{k_i\ge0}\)),现规定两名员工可以交流的条件如下:两名员工会一种及以......
  • 题解 CF980B
    前言:关于原题目中的“旅馆”这一用词,个人感觉用起来十分不畅,于是下文中将会用“障碍物”一词来代指旅馆。题目大意:有一座\(4\timesn\)的矩阵,然后让你放置障碍物......
  • MASA Stack 1.0 发布会 —— 社区问题解答
    MASAStack1.0圆桌讨论Q1: 全职开源的团队,你们的收入是什么?1.首先感谢我们的金主朗诗德公司,朗诗德是一家大型的净水器研发、生产、销售的公司,我们的产品也在朗诗德公......
  • ABC222H 题解
    很久之前我问joke3579有没有什么水黑,然后他给我了这个题。小推一波。题解看到这种东西首先找找有没有什么性质。简单分析可以得出一棵美丽的\(n\)阶二叉树一定满足如......
  • zfs 之 `label is missing` 问题解决方法.
    具体报错信息status:Oneormoredevicescouldnotbeusedbecausethelabelismissingorinvalid.Sufficientreplicasexistforthepooltocontinue......
  • abc289F 题解
    某人vp时10min口胡了这道题,然后调了两天,第一天卡在WA4,第二天WA7WA10交相辉映,心态快崩了,因此写了这篇题解。\(a=b\)处理有借鉴这篇题解。firstobservation......
  • P7468 愤怒的小N 题解
    P7468愤怒的小N题解首先发现答案等于\[\sum_{i=0}^{n-1}[cnt(i)\&1]\cdotf(i)\\\]其中\(cnt(x)\)为\(x\)在二进制表示下\(1\)的个数。考虑从高到低枚举第一个......