视频加载失败

峰回路转

619 字
3 分钟
峰回路转

峰回路转,云开雾散

题目描述#

小月是一名黑客。当前终端上有一行长度为 nn 的数据流,从左到右依次为 a1,a2,…,ana_1, a_2, \dots, a_n。

小月拥有一个黑客程序,可以对数据流执行一次如下操作:选择一个位置 kk(1≦k≦n1 \leqq k \leqq n),将数据流前 kk 个元素的顺序完全反转,使数据流变为

ak,ak−1,…,a1,ak+1,…,ana_k, a_{k-1}, \dots, a_1, a_{k+1}, \dots, a_n

设操作后的数组变为 b1,b2,…,bnb_1, b_2, \dots, b_n,为了维持系统的隐匿性,操作后的数据流必须满足 b1≦b2≦⋯≦bnb_1 \leqq b_2 \leqq \dots \leqq b_n。满足条件的 kk 被称为合格参数。

请你帮助小月计算,合格参数 kk 的数量。

输入描述#

每个测试文件均包含多组测试数据。第一行输入一个整数 TT(1≦T≦1041 \leqq T \leqq 10^4),表示测试数据组数。

对于每组测试数据:

  • 第一行输入一个整数 nn(1≦n≦2×1051 \leqq n \leqq 2 \times 10^5),表示数据流长度。
  • 第二行输入 nn 个整数 a1,a2,…,ana_1, a_2, \dots, a_n(−109≦ai≦109-10^9 \leqq a_i \leqq 10^9),表示数据流中的元素。

除此之外,保证单个测试文件中所有测试数据的 nn 之和不超过 2×1052 \times 10^5。

输出描述#

对于每组测试数据,在一行上输出一个整数,表示合格参数的数量。

示例1#

输入#

2
5
4 3 1 5 6
4
1 2 2 3

输出#

1
1

说明#

第一组测试数据中,反转前 33 个元素后,数据流变为 1,3,4,5,61, 3, 4, 5, 6。其他参数均不能使数据流达到稳定状态。

第二组测试数据中,只有 k=1k = 1 合格,反转一个元素后数据流仍为原数据流。

示例2#

输入#

3
3
1 3 2
4
2 2 2 5
1
-1000000000

输出#

0
3
1

说明#

第一组测试数据不存在合格参数;

第二组测试数据的合格参数为 k=1,2,3k = 1, 2, 3;

第三组测试数据仅有 k=1k = 1 合格。

代码:

#include <bits/stdc++.h>
using namespace std;
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int T;
cin >> T;
while(T--){
int n;
cin >> n;
vector<long long> a(n + 2);
for(int i = 1; i <= n; i++) cin >> a[i];
int ans=0;
vector <long long> p(n+1); //前i中共有多少非增
vector <long long> q(n+2); //后i中共有多少非减
a[0]=10e9;
a[n+1]=10e9;
p[0]=1;
q[n+1]=1;
for(int i=1;i<=n;i++)
{
if(p[i-1]==1&&a[i-1]>=a[i]) //差分前缀
{p[i]=1;}
}
for(int i=n;i>=1;i--)
{
if(q[i+1]==1&&a[i]<=a[i+1]) //差分后缀
{q[i]=1;}
}
for(int i=1;i<=n;i++)
{
if(p[i]==1&&q[i]==1&&a[1]<=a[i+1]) //条件判断(三个)
{ans++;}
}
cout << ans << "\n";
}
}

文章分享

如果这篇文章对你有帮助,欢迎分享给更多人!

峰回路转
https://www.xiaobaibai454.top/posts/study-26-10-15/
作者
Xiao_baibai
发布于
2026-10-15
许可协议
CC BY-NC-SA 4.0

评论区

Profile Image of the Author
Xiao_baibai
你是怎么找到这里的???
分类
最新动态
站点统计
文章
25
分类
4
标签
5
总字数
17,871
运行时长
0 天
最后活动
0 天前
站点信息
构建平台
GitHub Actions
博客版本
Firefly v6.16.8
文章许可
CC BY-NC-SA 4.0
文章目录