非官方题解|巅峰赛#27部分题解

复仇者_澜（不处不加团队）

2025-11-12 20:22:50

发布于：广东

19阅读

0回复

0点赞

本题解将会在本人写出其他题后持续更新

T1

题目大意：

你可以将一个数组最左边的数移到末尾，问你移多少次可以使得这个数组非降序。

？我的解法好神秘

起因是一直过不了样例和自己的hack数据，于是便误以为这是一道黄题。

首先我的想法是如果逆序对的个数 $>1$ 那肯定不行，因为不管怎么换位都有一个逆序对。

然后写完了代码发现过不了样例 $2$ 里面的这组数据

6
1 3 2 4 5 6

实际应该是-1，但我输出的2。

然后就发现了这个本质上应该是一个环形的数组，所以 $a(1)<a(n)$ 也是一个逆序对。

我还发现了这题数据有着两个很大的问题

我的过不了样例2的代码90分（多加点 $a(1)<a(n)$ 的数据）
$\sum n\le 2\times 10^6,$ 我数组开的 $10^5$ 过了。

#include<bits/stdc++.h>
using namespace std;
int n,a[2000009];
void solve(){
    cin>>n;
    for(int i = 1;i<=n;++i){
        cin>>a[i];
    }
    if(n == 1){
        cout<<0;
        return ;
    }
    if(a[1]<a[n]){
        for(int i = 1;i<n;++i){
            if(a[i]>a[i+1]){
                cout<<-1;
                return ;
            }
        }
        cout<<0;
        return ;
    }
    int id = 0;
    for(int i = 1;i<n;++i){
        if(a[i]>a[i+1]){
            if(id!=0){
                cout<<-1;
                return ;
            }
            id = i;
        }
    }
    cout<<id;
}
int main(){
	int t;
    cin>>t;
    while(t--){
        solve();
        putchar('\n');
    }
}

时间复杂度： $O(n)$

T2

赛时思路：打表小数据，发现输入的 $n$ 是 1,4 或者质数的时候是 YES，否则是NO。

赛后：

被出题人题解吓哭了，看不懂出题人的思路

#include<bits/stdc++.h>
using namespace std;
const int N = 1000009;
bool vis[N];
void sieve(int n){
    vis[0] = vis[1] = true;
    for(int i = 2;i<=n/i;i++){
        if(!vis[i]){
            for(int j = i*i;j<=n;j+=i){
                vis[j] = true;
            }
        }
    }
}
int main(){
    int t;
    cin>>t;
    sieve(1000000);
    while(t--){
        int n;
        cin>>n;
        if(n == 1||n == 4){
            cout<<"YES\n";
        }else if(vis[n] == 0) cout<<"YES\n";
        else cout<<"NO\n";
    }
}

时间复杂度： $O(T+n log log n)$

T5

题目大意：

一个长度为 $n$ 的数组 $a$ ，你可以将 $a$ 中一个长度不超过 $L$ 的连续子数组取相反数（最多这样干一次，可以不干），最后截取 $a$ 中一段连续子数组的和作为答案，要求子数组的和尽可能大。

一张图片就概括了我写这道题目的精神状态。

先把 $L=0$ 判了。

暴力太劣了，好像至少是 $O(n^2L)$ 的，那我们直接正解。

注意到答案可以分成三段，翻转段前，翻转段，翻转段后。

定义 $le(i),ri(i)$ 分别表示从左到右和从右到左长度为 $i$ 的最大子段和， $d(i)$ 前缀和，随后我们枚举翻转段的右端点，拿一个单调队列来维护区间最大值，用区间最大值来更新答案，类似于一个单调队列板题：区间滑动窗口最值问题。

答案对上述以及不翻转的情况求最大值即可

大坑：memset开0x3f3f3f3f也是不够的，直接手动赋值-1e18

#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,l;
int a[200009],d[200009],le[200009],ri[200009];
int ans = -1e18;
deque<int> q;
void solve(){
    int dp[200009];
    for(int i = 1;i<=n;++i) dp[i] = -1e18;
    for(int i = 1;i<=n;++i){
        dp[i] = max(dp[i-1]+a[i],a[i]);
    	ans = max(ans,dp[i]);
    }
    cout<<ans;
}
signed main(){
    cin>>n>>l;
    for(int i = 1;i<=n;++i){
        cin>>a[i];
        d[i] = d[i-1]-a[i];
    }
    if(l == 0){
        solve();return 0;
    }
    int dp = 0;
    for(int i = 1;i<=n;++i){
        dp = max(a[i],a[i]+dp);
        ans = max(ans,dp);
        le[i] = max(dp,le[i]);
    }
    dp = 0;
    le[0] = d[0] = 0;
    for(int i = n;i>=1;i--){
        dp = max(a[i],a[i]+dp);
        ri[i] = max(ri[i],dp);
    }
    for(int i = 1;i<=n;++i){
        while(q.size()&&le[i-1]-d[i-1]>=le[q.back()]-d[q.back()]) q.pop_back();
        q.push_back(i-1);
        if(q.front()<i-l) q.pop_front();
        if(q.size()) ans = max(ans,le[q.front()]-d[q.front()]+d[i]+ri[i+1]);
    }
    cout<<ans;
}