P10885 【MX-S3-T1】「FeOI Round 1」野心

题目背景

原题链接：https://oier.team/problems/S3A。

---

题目描述

给出一个 $1\sim n$ 的排列 $p$，询问存在多少个数 $i$（$1\le i<n$）满足 $[p_1,p_2,\cdots ,p_i]$ 和 $[p_{i+1},p_{i+2},\cdots ,p_n]$ 排序后都是等差数列。

输入格式

本题单个测试点内包含多组数据。

第一行一个整数 $T$ 表示数据组数。

接下来，对于每组数据，格式如下：

第一行一个数 $n$ 表示排列长度。

接下来一行 $n$ 个数表示排列 $p$。

输出格式

对于每组测试数据，输出一行一个数表示询问的答案。

输入输出样例 #1

输入 #1

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

输出 #1

3
3

输入输出样例 #2

输入 #2

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

输出 #2

2
5
2
0

输入输出样例 #3

输入 #3

6
2
1 2
20
16 2 10 18 4 6 8 20 14 12 3 9 17 13 1 15 7 11 19 5
9
3 4 1 5 2 6 7 8 9
10
1 3 2 4 7 6 5 8 10 9
13
5 7 3 11 1 9 13 6 10 4 2 8 12
5
1 2 3 4 5

输出 #3

1
1
4
5
1
4

说明/提示

【样例解释 #1】

第一组：三种拆分为 $[1,3,2][4]$，$[1,3][2,4]$，$[1][3,2,4]$。

第二组：三种拆分为 $[1][5,3,2,4]$，$[1,5][3,2,4]$，$[1,5,3][2,4]$。

【样例解释 #2】

第一组：两种拆分为 $[2,1][4,3,6,5]$，$[2,1,4,3][6,5]$。

第二组：每种拆分都是合法的。

第三组：每种拆分都是合法的。

第四组：不存在拆分方案，故没有方案合法。

【数据范围】

本题开启捆绑测试。

设 $\sum n$ 为单个测试点内所有的 $n$ 之和。

对于 $100\%$ 的数据，$1\le T\le 10^5$，$1\le n\le 10^6$，$1\le \sum n\le 2\times 10^6$，保证 $p$ 是排列且 $1\le p_i\le n$。

子任务编号	$n $	$\sum n $	分数
$1$	$\le 10^3$	$\le 5\times 10^3$	$30$
$2$	$\le 10^5$	$\le 5\times 10^5$	$30$
$3$	$\le 10^6$	$\le 2\times 10^6$	$40$

请使用较快的输入输出方式。

新增子任务 4 为 hack 数据，分值为 $0$。

C++实现

#include <bits/stdc++.h>
using namespace std;
int T,n,v,s,da,o,i,j,dan,ou;
int a[1000001],b[1000001],f[1000001],c[1000001],d[1000001];
int main(){
	cin>>T;
	while(T--){
		cin>>n;v=0;
		for(i=1;i<=n;i++) cin>>a[i];
		for(i=1;i<n;i++){
			int fl=0,k,j;
			for(j=1;j<=i;j++)
				b[j]=a[j];
			sort(b+1,b+i+1);
			if(i!=1){
				s=b[2]-b[1];
				for(j=2;j<i;j++)
					if(b[j+1]-b[j]!=s){
						fl=1;
						break;
					}
			}
			if(fl==1) continue;
			for(j=i+1,k=1;j<=n;j++,k++)
				b[k]=a[j];
			k--;
			sort(b+1,b+k+1);
			if(k!=1){
				s=b[2]-b[1];
				for(int j=2;j<k;j++)
					if(b[j+1]-b[j]!=s){
						fl=1;
						break;
					}
			}
			if(fl==1) continue;
			v++;
		}
		cout<<v<<"\n";
	}
}

后续

接下来我会不断用C++来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现，记录日常的编程生活、比赛心得，感兴趣的请关注，我后续将继续分享相关内容