首页 > 试题广场 >

子段和

[编程题]子段和
  • 热度指数:1349 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 256M,其他语言512M
  • 算法知识视频讲解
给定一个序列,问你有没有可能重新排列这个序列使得所有长度小于等于 2 的子区间和不等于 0

输入描述:
第一行一个 n 表示序列长度,接下来一行 n 个数,第 i 个为 a_i,表示序列中的第 i 个数。




输出描述:
一行一个字符串。"YES"表示可能重新排列这个序列使得所有长度小于等于 2 的子区间和不等于 0,反之则输出“NO”。输出不含引号。
示例1

输入

6
34 1345 -3542 -1423 4213 1

输出

YES

说明

不变即可。
示例2

输入

4
1 1 -1 1

输出

NO

说明

无论怎样排列,-1 总和至少 11 相邻,所以总存在一个和为 0 的长度为 2 的子段。
示例3

输入

5
1 5 -1 -5 0

输出

NO

说明

0 的存在使得总有一个长度为 1 的子段和为 0
这道题其实挺简单的喵!
注意长度小于等于 2 的子区间和不等于 0
我们就可以知道相反数不能相邻喵!
这就非常简单了喵!
假如数组里有0的话,一定NO喵!
因为相同的数分散开是不利于满足题意的!所以我们可以把相同数放在一起,看作一个数喵!其实就是去重喵!

假设去重后数字大于2的话,就一定是YES!因为有多组相反数可以交叉排列。
比如:-1,1,-2,2可以排列为:-1,-2,1,2。而只有一组相反数的话也可以拿其他数把它隔开。
所以说猫猫的代码中不是完全去重,而是保证大于2就可以了喵!

假设去重后数字等于2的话,必须是相反数才能NO哦。其他都是YES喵!
看代码!
#include <bits/stdc++.h>
using namespace std;
using ll=long long;

int main() 
{
    cin.tie(0)->sync_with_stdio(0);
    ll n;cin >> n;
    ll qc=n;//不严谨的去重
    ll mi=2e9+1,ma=-2e9-1;
    for(ll i=0;i<n;i++)
    {
        ll num;cin >> num;
        if(num==0)//有0就不可以
        {
            cout << "NO";
            return 0;
        }
        if(num==mi||num==ma) qc--;//去重
        if(num>ma)
        {
            ma=num;
        }
        if(num<mi)
        {
            mi=num;
        }
    }
    if(qc==2&&ma+mi==0)//如果只有两个数且为相反数
    {
        cout << "NO";
    }
    else cout << "YES";
}
/*
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣀⣤⣤⡀⣀⣠⣤⣄⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣀⣀⡀⢀⣴⣾⣷⣶⣾⣿⣿⣿⣿⣿⣿⣿⣿⣷⣾⣿⣷⣦⡀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣠⣾⣿⣿⣿⣿⣿⣿⣿⠿⠛⠛⠉⠉⠉⠉⠉⠉⠛⠻⠿⣿⣿⣿⣿⣿⣶⣤⡀⠀⠀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⢠⣾⣿⣿⣿⡿⠿⠛⠉⠉⠉⠉⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠈⠙⠿⣿⣿⣿⣷⣄⡀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⣀⣿⣿⣿⠟⠁⠀⠀⠀⠀⠀⠀⠀⣰⡆⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠙⠿⣿⣿⣿⡄⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⣠⣾⣿⣿⠟⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣿⣶⣄⠀⠀⠀⠀⠀⢀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠈⣻⣿⣿⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⢹⣿⡿⠁⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢰⣿⠁⠈⢢⡀⠀⠀⠀⢸⡇⢀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠈⠻⣿⡟⠒⢦⡀⠀⠀⠀
⠀⠀⣠⣤⣤⣼⡟⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠸⡇⠀⠀⠀⠉⢢⣄⠀⠀⢿⠊⠳⡄⠀⠀⠀⠀⠀⠀⠀⠀⠀⠙⣷⡄⠀⢷⠀⠀⠀
⠀⢰⠇⠀⣰⡟⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⡇⠀⠀⠀⠀⡌⣹⠗⠦⣬⣇⠀⠉⢢⡀⠀⠀⠀⠀⠀⠀⠀⠀⠘⣿⡀⢸⡄⠀⠀
⠀⡟⠀⣼⣯⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢰⣆⢹⡀⠀⠀⠀⠉⠁⠀⠀⢀⣀⡁⠀⠀⠉⠳⢴⡆⠀⠀⠀⠀⠀⠀⢹⣧⠈⡇⠀⠀
⠀⡇⠀⠀⢻⣦⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣀⣾⠻⠉⠛⠂⠀⠀⠀⠀⠀⠀⠻⠿⣿⣿⣿⣶⣦⡀⠛⣇⠀⠀⠀⠀⠀⣈⣿⠀⡇⠀⠀
⢸⡇⠀⠀⢠⣿⣷⣦⣀⡸⣷⣦⣶⡂⠉⠉⠉⢁⣤⣶⡶⠀⠀⠀⣀⣀⡴⠀⠀⠀⠀⠀⠀⠈⠉⠉⠁⠀⡟⢀⣴⣟⣰⣾⣿⣏⣠⠇⠀⠀
⠈⡇⠀⠀⢸⣿⠁⠉⣿⠛⠛⠃⡇⠀⠀⢠⣶⣿⡿⠛⠁⠀⠀⠉⠁⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠼⢿⠟⠿⢿⡏⠀⠘⣿⡀⠀⠀⠀
⠀⢷⣀⣀⣿⠇⠀⠀⢿⡇⠀⢀⢱⡀⠀⠛⠛⠉⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣼⠀⠀⢸⠇⠀⠀⢹⣿⣄⠀⠀
⠀⠀⣉⣿⡏⠀⠀⠀⠀⠀⠀⢸⣇⣳⡄⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⡰⣿⠃⠀⠀⠀⠀⠀⠀⣿⠈⢧⠀
⠀⠘⣿⣿⠁⠀⠀⠀⠀⠀⠀⠘⣿⡛⣶⠀⠀⣠⠔⠒⠛⠒⠦⡀⠀⠀⠀⠀⣠⡤⠶⠤⢤⣀⠀⠀⠀⢀⣏⡄⠀⠀⠀⠀⠀⡀⣿⡆⠈⣧
⣠⡾⠛⣿⣿⣧⠀⠀⠀⠀⢸⣿⠾⢿⡿⠀⣰⠃⠀⠀⠀⠀⠀⢹⡄⠀⠀⡼⠁⠀⠀⠀⠀⠈⠙⣦⠀⢸⣿⡇⣾⣣⡀⠀⢰⣿⣿⣿⣤⠾
⡟⠀⠀⠻⣿⡟⢷⡄⣤⡀⠈⣿⡀⣸⠇⠀⠏⠀⠀⠀⠀⠀⠀⠀⡇⠀⠀⡇⢀⡀⠀⠀⠀⠀⢀⡟⠀⠀⠋⣿⣿⣿⡇⣠⣿⠿⠛⢷⡀⠀
⠀⠀⠀⠀⣿⣇⣨⣿⣿⣿⣦⣽⣷⡟⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠁⠀⠀⠃⠀⠙⠢⠤⠤⠴⢾⠀⠀⠀⠀⢸⣷⣿⣿⠟⠁⠀⠀⠈⣧⠀
⠀⠀⠀⠀⠈⠉⠉⠁⠈⠉⠈⢉⣿⡁⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠈⠀⠀⠀⠀⢸⡇⠀⠀⠀⠀⠀⠀⠀⣿⠀
*/


发表于 2026-03-03 09:26:56 回复(0)
试着想一下不难发现只有两种情况会NO,一种是本身就含有0,另一种是这个序列全是某个数和其相反数,紧接着我们写出代码
#include <iostream>
#include<bits/stdc++.h>
#include <vector>
using namespace std;
#define int long long
//1 -1 -1
signed main(){
    int n;cin>>n;
    vector<int> a(n+1);
    map<int,int> mp;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        mp[a[i]]++;
        if(a[i]==0){
            cout<<"NO";
            return 0;
        }
    }
    for(int i=1;i<=n;i++){
        if(mp[a[i]]+mp[-a[i]]==n&&mp[a[i]]&&mp[-a[i]]){
            cout<<"NO";
            return 0;
        }
    }
    cout<<"YES";
    return 0;
}

发表于 2026-03-03 13:23:11 回复(0)
#include <stdio.h>

int main() {
    long int a, b,d,e,f,g,h,i,q;
    long int c[500000];
    
    scanf("%ld",&a);
    d=a;
    for (a=a,b=0; a>0;a--) {
        scanf("%ld",&c[b]);
        b=b+1;
    }
    for (d=d,e=0; d>0;d-- ) {
        for (g=d,f=0; g>0;g-- ) {
            h=c[e];
            i=c[f];
            if (e==f) {break;
            }else if 
            (h+i==0){
                q=1;
                printf("NO");
                break;
            }
            f=f+1;
        }
        if (q==1) {
            break;
        }
        else if (d==1) {printf("YES");
        break;
        }
        e=e+1;
    }
    return 0;
}
请问为什么调试的结果没问题,但是保存提交后却报错没有输出内容
发表于 2026-03-03 21:04:06 回复(0)
其实挺简单的,输入的时候检查一下有没有0,
然后对数组快排,找到第一个大于0的数,看看它与前一个数的和是否为0,
若为0,则将其与最后一个数字调换一下位置看看和是否为0就好了
(有错误请佬们指正,我也不知道我的思路和代码具有健壮性(
#include <bits/stdc++.h>
using namespace std;
#define ll long long

int main ()
{
    int n;
    cin>>n;
    vector <ll> a(n, 0);
    for (int i = 0;i < n;i++) {
        cin>>a[i];
        if (a[i] == 0) {
            cout<<"NO";
            return 0;
        }
    }
    sort (a.begin(), a.end());

    //for (auto num : a) cout<<num<<" ";

    for (int i = 0;i < n;i++) {
        if (a[i] > 0) {
            if (a[i - 1] + a[i] == 0) {
                if (a[i - 1] + a[n - 1] == 0) cout<<"NO";
                else cout<<"YES";
            } else cout<<"YES";
            break;
        }
    }

    return 0;
}

发表于 2026-03-03 22:43:19 回复(0)
只有以下三种情况:
1. 只要有“0”,则一定不符合要求。
2. 全为正数,或者全为负数,则一定符合要求。
3. 既有正数又有负数,把正数放一起,负数放一起
只要能找到一对正数和负数,绝对值不同,放在交界处即可。
这种情况下:所有数的绝对值全同,不符合要求其它情况均符合要求

速读提示:
按照上述结论,我们只关心“正/负/零”以及(剔除负号后)是否完全相同。
所以无需读成数字,直接读首字符判正负,然后按字符串比对即可。
while (*buf++ != '\n') {}
bool positive = false; // 存在正数
bool negative = false; // 存在负数
bool different = false; // (剔除负号)存在不同的值
if (*buf == '0') { // 遇到0直接结束
    puts("NO");
    return 0;
} else if (*buf == '-') {
    negative = true; // 负数
    buf++; // 剔除负号
} else {
    positive = true; // 正数
}
// 从start到end的字符用来比对
char* start = buf;
while (*buf >= '0') buf++;
char* end = buf;
while (*buf++ == ' ') { // 以空格分割,直到换行结束
    if (different) { // 前面已找到不同,无需读取数字
        if (*buf++ == '0') { // 遇到0直接结束
            puts("NO");
            return 0;
        }
        // 从第2个字符起,跳过所有数字
        while (*buf >= '0') buf++;
    } else { // 前面未找到不同,比对数字
        if (*buf == '0') { // 遇到0直接结束
            puts("NO");
            return 0;
        } else if (*buf == '-') {
            negative = true; // 负数
            buf++; // 剔除负号
        } else {
            positive = true; // 正数
        }
        for (char* ch = start; ch != end; ch++) {
            if (*buf < '0') {
                different = true; // 比预期的短
                break;
            } else if (*buf++ != *ch) {
                different = true; // 找到不同字符
                while (*buf >= '0') buf++;
            }
        }
        if (*buf >= '0') {
            different = true; // 比预期的长
            while (*buf >= '0') buf++;
        }
    }
}
// 有正数有负数且绝对值全部相同,则输出NO,否则,输出YES
puts((!different && (positive & negative)) ? "NO" : "YES");
return 0;


发表于 2026-03-03 04:07:57 回复(0)