当前位置：首页 > news >正文

打卡信奥刷题（2956）用C++实现信奥题 P5923 [IOI 2004] empodia 障碍段

news 2026/4/6 23:20:14

P5923 [IOI 2004] empodia 障碍段

题目背景

古数学及哲学家毕氏相信自然之本质为数学。

现代生物学家研究生物数列。

题目描述

生物数列为满足下列条件的MMM个整数所成的数列：

包含0,1,⋯ ,M−10, 1, \cdots, M-10,1,⋯,M−1中的所有数字。
起始数字为000，最后一个数字为M−1M - 1M−1。
数列中E+1E+1E+1不可以紧接在EEE之后。

生物数列的连续子数列称为数段。如果一个数段的：

起点为该数段最小的数字。
终点为该数段最大的数字且与起点不是同一个数字。
且介于这两个数字之间所有的整数都出现在这个数段中。

则称这个数段为框段。

如果框段中并不包含更短的框段，则称之为障碍段。

以(0,3,5,4,6,2,1,7)这个生物数列为例。

整个生物数列是一个框段，可是它包含了另外一框段(3,5,4,6)，因此该生物数列不是障碍段。而框段(3,5,4,6)并不包含任何更短的框段，所以它是一个障碍段，而且是此生物数列中唯一的障碍段。请写一个程序，在输入生物数列后，输出所有的障碍段。

输入格式

第一行为单一整数MMM，代表生物数列的长度。

生物数列中的数字依序出现在接下来的MMM行，每一行有一个整数。

输出格式

第一行为一整数HHH，代表该生物数列中的障碍段的个数。

接下来的HHH行，将每一个障碍段，依照起点在原输入生物数列中出现的顺序，依序输出。

每行以222个整数AAA与BBB代表一个障碍段并以一个空格分开。

原输入生物数列第AAA个元素为该障碍段的起点，而第BBB个元素为该障碍段的终点。

输入输出样例 #1

输入 #1

8 0 3 5 4 6 2 1 7

输出 #1

1 2 5

说明/提示

对于100%100\%100%的数据，M≤1100000M\le1100000M≤1100000。

C++实现

#include<bits/stdc++.h>usingnamespacestd;constintN=1200000;intn,a[N];vector<pair<int,int>>ans;intmain(){scanf("%d",&n);for(inti=1;i<=n;i++){scanf("%d",&a[i]);}inted=n;for(intl=n;l>=1;l--){intmx=a[l];for(intr=l+1;r<=ed;r++){if(a[r]<a[l]){break;}if(a[r]>mx&&a[r]-a[l]==r-l){ed=l;ans.push_back(make_pair(l,r));}mx=max(mx,a[r]);}}printf("%d\n",(int)ans.size());for(autov:ans){printf("%d %d\n",v.first,v.second);}return0;}