峰回路转
619 字
3 分钟
峰回路转
峰回路转,云开雾散
题目描述
小月是一名黑客。当前终端上有一行长度为 的数据流,从左到右依次为 。
小月拥有一个黑客程序,可以对数据流执行一次如下操作:选择一个位置 (),将数据流前 个元素的顺序完全反转,使数据流变为
设操作后的数组变为 ,为了维持系统的隐匿性,操作后的数据流必须满足 。满足条件的 被称为合格参数。
请你帮助小月计算,合格参数 的数量。
输入描述
每个测试文件均包含多组测试数据。第一行输入一个整数 (),表示测试数据组数。
对于每组测试数据:
- 第一行输入一个整数 (),表示数据流长度。
- 第二行输入 个整数 (),表示数据流中的元素。
除此之外,保证单个测试文件中所有测试数据的 之和不超过 。
输出描述
对于每组测试数据,在一行上输出一个整数,表示合格参数的数量。
示例1
输入
254 3 1 5 641 2 2 3输出
11说明
第一组测试数据中,反转前 个元素后,数据流变为 。其他参数均不能使数据流达到稳定状态。
第二组测试数据中,只有 合格,反转一个元素后数据流仍为原数据流。
示例2
输入
331 3 242 2 2 51-1000000000输出
031说明
第一组测试数据不存在合格参数;
第二组测试数据的合格参数为 ;
第三组测试数据仅有 合格。
代码:
#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";
}}文章分享
如果这篇文章对你有帮助,欢迎分享给更多人!




