HPOJ1010题解

发表于 | 更新于 | 评论数： | 阅读次数：

ZROI #549原题，但考场上我还是没做出来。

come ON HPOJ

原题链接

分析

我们开一个桶记录一下有哪些数是结尾。

然后$O(n)$扫一遍数组，如果满足$B_i=B_{i+1}+1$的条件，就把它接上。

最后输出合法的序列数量即可。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
/* Headers */ 
#include<cstdio>
#include<cstring>
#include<cmath>
#include<cctype>
using namespace std;
namespace FastIO{
    const int BUFSIZE=1<<20;
    char ibuf[BUFSIZE],*is=ibuf,*it=ibuf;
    char obuf[BUFSIZE],*os=obuf,*ot=obuf+BUFSIZE;
    inline char getch(){
        if(is==it)
            it=(is=ibuf)+fread(ibuf,1,BUFSIZE,stdin);
        return (is==it)?EOF:*is++;
    }
    inline int getint(){
        int res=0,neg=0,ch=getch();
        while(!(isdigit(ch)||ch=='-')&&ch!=EOF)
            ch=getch();
        if(ch=='-'){
            neg=1;ch=getch();
        }
        while(isdigit(ch)){
            res=(res<<3)+(res<<1)+(ch-'0');
            ch=getch();
        }
        return neg?-res:res;
    }
    inline void flush(){
        fwrite(obuf,1,os-obuf,stdout);
        os=obuf;
    }
    inline void putch(char ch){
        *os++=ch;
        if(os==ot)	flush();
    }
    inline void putint(int res){
        static char q[10];
        if(res==0)	putch('0');
        else if(res<0){
            putch('-');
            res=-res;
        } 
        int top=0;
        while(res){
            q[top++]=res%10+'0';
            res/=10;
        }
        while(top--)	putch(q[top]);
    }
} 
using namespace FastIO;
/* definitions */
const int MAXN = 1e6+10;
int n,ans,num[MAXN];
int Buck[MAXN];
/* functions */
inline void init(){
	scanf("%d",&n);
	ans=n;
	for(int i=1;i<=n;i++)scanf("%d",&num[i]);
}
inline void Bucket(){
	init();
	Buck[num[n]]=1;
	for(int i=n-1;i>=1;i--){
		if(num[i]-1!=0){
			if(Buck[num[i]-1]){
				Buck[num[i]-1]--;
				ans--;
			}
		}
		Buck[num[i]]++;
	}
	printf("%d\n",ans);
}
int main(int argc,char *argv[]){
	//freopen("part4.in","r",stdin);
	//freopen("part4.out","w",stdout);
	Bucket();
	return 0;
}

THE END