NOIp2013题解

发表于 更新于

既然NOIp2018有原题,那么CSP-S2019之前做做原题是有帮助的

Day1 T1

题目链接 - LuoguP1965

Solution

根据人类智慧可以得知,答案显然为$(x + m \times 10^k) \mod n$

然后根据模运算对乘法封闭的性质,可以得到$(x \mod n + m \mod n + 10^k \mod n) \mod n$,于是快速幂即可.

Code

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
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
/* Headers */
#include<cstdio>
#include<cstring>
#include<cmath>
#include<cctype>
#include<algorithm>
#include<vector>
#include<queue>
#include<stack>
#include<climits>
#include<iostream>
#include<map>
#define FOR(i,a,b,c) for(int i=(a);i<=(b);i+=(c))
#define ROF(i,a,b,c) for(int i=(a);i>=(b);i-=(c))
#define FORL(i,a,b,c) for(long long i=(a);i<=(b);i+=(c))
#define ROFL(i,a,b,c) for(long long i=(a);i>=(b);i-=(c))
#define FORR(i,a,b,c) for(register int i=(a);i<=(b);i+=(c))
#define ROFR(i,a,b,c) for(register int i=(a);i>=(b);i-=(c))
#define lowbit(x) x&(-x)
#define LeftChild(x) x<<1
#define RightChild(x) (x<<1)+1
#define RevEdge(x) x^1
#define FILE_IN(x) freopen(x,"r",stdin);
#define FILE_OUT(x) freopen(x,"w",stdout);
#define CLOSE_IN() fclose(stdin);
#define CLOSE_OUT() fclose(stdout);
#define IOS(x) std::ios::sync_with_stdio(x)
#define Dividing() printf("-----------------------------------\n");
namespace FastIO{
    const int BUFSIZE = 1 << 20;
    char ibuf[BUFSIZE],*is = ibuf,*its = ibuf;
    char obuf[BUFSIZE],*os = obuf,*ot = obuf + BUFSIZE;
    inline char getch(){
        if(is == its)
            its = (is = ibuf)+fread(ibuf,1,BUFSIZE,stdin);
        return (is == its)?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]);
    }
    inline void space(bool x){
    	if(!x) putch('\n');
    	else putch(' ');
    }
}
inline void read(int &x){
    int rt = FastIO::getint();
    x = rt;
}
inline void print(int x,bool enter){
    FastIO::putint(x);
    FastIO::flush();
    FastIO::space(enter);
}
/* definitions */
int n,m,k,x,mod;
/* functions */
inline int quick_power(int a,int b,int p) {
	int res = 1, base = a;
	while(b) {
		if(b & 1) res = res * base % p;
		b >>= 1; base = base * base % p;
	}
	return res;
}
int main(int argc,char *argv[]){
	scanf("%d%d%d%d",&n,&m,&k,&x); mod = n;
	int ans = (x % mod + m % mod * quick_power(10,k,mod)) % mod;
	printf("%d\n",ans);
	return 0;
}

Day1 T2

题目链接 - LuoguP1966

Solution

这题和T1难度差距有点大啊……….

题意让我们最小化这个式子:

$$\sum_{i=1}^n (a_i - b_i) ^2$$

显然$a_i,b_i$均为正整数,那么只需要最小化$a_i - b_i$即可.

也就是说,两个序列的第$k$大值所处的位置必须相同($1 \leq k \leq n$)

考虑对两个序列进行离散化,那么问题转化为离散化后的$B$序列如何通过最少的交换次数变成$A$序列.

设$bet_{a_i} = b_i$,即以$A$序列为关键字对$B$序列排序.

那么当两序列相等时,满足$bet_{a_i} = a_i$,即$bet_i = i$

那么问题转化为交换几次能使的$bet$数组满足升序排列,树状数组求逆序对即可.

Code

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
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
/* Headers */
#include<cstdio>
#include<cstring>
#include<cmath>
#include<cctype>
#include<algorithm>
#include<vector>
#include<queue>
#include<stack>
#include<climits>
#include<iostream>
#include<map>
#define FOR(i,a,b,c) for(int i=(a);i<=(b);i+=(c))
#define ROF(i,a,b,c) for(int i=(a);i>=(b);i-=(c))
#define FORL(i,a,b,c) for(long long i=(a);i<=(b);i+=(c))
#define ROFL(i,a,b,c) for(long long i=(a);i>=(b);i-=(c))
#define FORR(i,a,b,c) for(register int i=(a);i<=(b);i+=(c))
#define ROFR(i,a,b,c) for(register int i=(a);i>=(b);i-=(c))
#define lowbit(x) x&(-x)
#define LeftChild(x) x<<1
#define RightChild(x) (x<<1)+1
#define RevEdge(x) x^1
#define FILE_IN(x) freopen(x,"r",stdin);
#define FILE_OUT(x) freopen(x,"w",stdout);
#define CLOSE_IN() fclose(stdin);
#define CLOSE_OUT() fclose(stdout);
#define IOS(x) std::ios::sync_with_stdio(x)
#define Dividing() printf("-----------------------------------\n");
namespace FastIO{
    const int BUFSIZE = 1 << 20;
    char ibuf[BUFSIZE],*is = ibuf,*its = ibuf;
    char obuf[BUFSIZE],*os = obuf,*ot = obuf + BUFSIZE;
    inline char getch(){
        if(is == its)
            its = (is = ibuf)+fread(ibuf,1,BUFSIZE,stdin);
        return (is == its)?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]);
    }
    inline void space(bool x){
    	if(!x) putch('\n');
    	else putch(' ');
    }
}
inline void read(int &x){
    int rt = FastIO::getint();
    x = rt;
}
inline void print(int x,bool enter){
    FastIO::putint(x);
    FastIO::flush();
    FastIO::space(enter);
}
/* definitions */
const int MAXN = 1e6 + 10;
const int mod = 99999997, inf = INT_MAX;
int n,ans,a[MAXN],b[MAXN],c[MAXN],d[MAXN],bet[MAXN];
struct BIT{
	int Tree[MAXN];
	inline void Modify(int x,int val) {
		while(x <= n) {Tree[x] += val; x += lowbit(x);}
	}
	inline int Query(int x) {
		int ans = 0;
		while(x) {ans += Tree[x]; x -= lowbit(x);}
		return ans;
	}
}T;
/* functions */
inline bool cmp1(int x,int y) {return a[x] < a[y];}
inline bool cmp2(int x,int y) {return b[x] < b[y];}
inline void solve() {
	ROF(i,n,1,1) {
		ans += T.Query(bet[i] - 1);
		T.Modify(bet[i],1);
		if(ans >= mod) ans -= mod;
	}
	printf("%d\n", ans);
}
int main(int argc,char *argv[]){
	scanf("%d",&n);
	FOR(i,1,n,1) {scanf("%d",&a[i]); c[i] = i;}
	FOR(i,1,n,1) {scanf("%d",&a[i]); d[i] = i;}
	std::sort(c + 1, c + n + 1, cmp1);
	std::sort(d + 1, d + n + 1, cmp2);
	FOR(i,1,n,1) bet[c[i]] = d[i]; solve();
	return 0;
}

Day1 T3

题目链接 - LuoguP1967

Solution

首先看完题我们就能想到Floyd最长路的算法,时间复杂度$O(n^3)$

我们设一个$w$数组来表示最大载重,状态转移方程式也不难推出，为:
$$w_{i,j} = max(w_{i,j},min(w_{i,k},w_{k,j}))$$

开始考虑优化：

我们可以发现，很多权值较小的边绝对不在我们的考虑范围内，所以我们可以将它们去掉。

因为我们要求走过的边权尽可能大，所以我们可以构建一棵最大生成树。

现在有了这样一棵最大生成树，我们就要考虑如何求出两个节点之间的最小边权的最大值。

因为树上的两个节点之间只有唯一的一条路径，所以我们就可以求出这两个点的最近公共祖先(这里我们用树上倍增实现)

此题代码实现难度和思考难度均较大（对于Herself32这种菜鸡来说），是一道不错的图论进阶题目。

Code

半年前的毒瘤码风请见谅/kel

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
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
/* Headers */
#include<cstdio>
#include<cstring>
#include<cmath>
#include<cctype>
#include<algorithm>
#include<vector>
#include<queue>
#include<stack>
#include<climits>
#include<iostream>
#include<map>
#define FOR(i,a,b,c) for(int i=(a);i<=(b);i+=(c))
#define ROF(i,a,b,c) for(int i=(a);i>=(b);i-=(c))
#define FORL(i,a,b,c) for(long long i=(a);i<=(b);i+=(c))
#define ROFL(i,a,b,c) for(long long i=(a);i>=(b);i-=(c))
#define FORR(i,a,b,c) for(register int i=(a);i<=(b);i+=(c))
#define ROFR(i,a,b,c) for(register int i=(a);i>=(b);i-=(c))
#define lowbit(x) x&(-x)
#define LeftChild(x) x<<1
#define RightChild(x) (x<<1)+1
#define RevEdge(x) x^1
#define FILE_IN(x) freopen(x,"r",stdin);
#define FILE_OUT(x) freopen(x,"w",stdout);
#define CLOSE_IN() fclose(stdin);
#define CLOSE_OUT() fclose(stdout);
#define IOS(x) std::ios::sync_with_stdio(x)
#define Dividing() printf("-----------------------------------\n");
namespace FastIO{
    const int BUFSIZE = 1 << 20;
    char ibuf[BUFSIZE],*is = ibuf,*its = ibuf;
    char obuf[BUFSIZE],*os = obuf,*ot = obuf + BUFSIZE;
    inline char getch(){
        if(is == its)
            its = (is = ibuf)+fread(ibuf,1,BUFSIZE,stdin);
        return (is == its)?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]);
    }
    inline void space(bool x){
    	if(!x) putch('\n');
    	else putch(' ');
    }
}
inline void read(int &x){
    int rt = FastIO::getint();
    x = rt;
}
inline void print(int x,bool enter){
    FastIO::putint(x);
    FastIO::flush();
    FastIO::space(enter);
}
/* definitions */
const int MAXN = 5e4 + 1;
const int MAXB = 20 + 1;
int n,m;
struct Edge{int from,to,val;}graph[MAXN];
struct Tree{int next,to,dis;}Graph[MAXN];
int head[MAXN],cnt,depth[MAXN],UFS[MAXN];
int doubly[MAXN][MAXB],weight[MAXN][MAXB];
bool visited[MAXN];
/* functions */
inline void Add_Edge(int from,int to,int cost){
	Graph[++cnt].next = head[from];
	Graph[cnt].to = to;
	Graph[cnt].dis = cost;
	head[from] = cnt;
}
inline void Ori_Add_Edge(int from,int to,int cost,int place){
	graph[place].from = from;
	graph[place].to = to;
	graph[place].val = cost;
}
inline bool cmp(Edge x,Edge y){
	return x.val > y.val;
}
inline int Find(int x){
	if(UFS[x] == x)return x;
	return UFS[x]=Find(UFS[x]);
}
inline void unionx(int x,int y,int cost){
	int findx = Find(x);
	int findy = Find(y);
	if(findx != findy){
		UFS[findx] = findy;
		Add_Edge(x,y,cost);
		Add_Edge(y,x,cost);
	}
}
inline void kruskal(){
	std::sort(graph+1,graph+m+1,cmp);
	FOR(i,1,n,1)UFS[i] = i;
	FOR(i,1,m,1)unionx(graph[i].from,graph[i].to,graph[i].val);
	return;
}
inline void DFS(int now){
	visited[now] = true;
	for(int i=head[now];i;i=Graph[i].next){
		if(visited[Graph[i].to])continue;
		depth[Graph[i].to] = depth[now] + 1;
		doubly[Graph[i].to][0] = now;
		weight[Graph[i].to][0] = Graph[i].dis;
		DFS(Graph[i].to);
	}
}
inline void LCAinit(){
	FOR(i,1,20,1){
		FOR(j,1,n,1){
			doubly[j][i] = doubly[doubly[j][i-1]][i-1];
			weight[j][i] = std::min(weight[j][i-1],weight[doubly[j][i-1]][i-1]);
		}
	}
}
inline int LCA(int x,int y){
	if(Find(x) != Find(y))return -1;
	int ans = INT_MAX;
	if(depth[x] > depth[y])std::swap(x,y);
	ROF(i,20,0,1){
		if(depth[doubly[y][i]] >= depth[x]){
			ans = std::min(ans,weight[y][i]);
			y = doubly[y][i];
		}
	}
	if(x == y)return ans;
	ROF(i,20,0,1){
		if(doubly[x][i] != doubly[y][i]){
			ans = std::min(ans,std::min(weight[x][i],weight[y][i]));
			x = doubly[x][i];
			y = doubly[y][i];
		}
	}
	ans = std::min(ans,std::min(weight[x][0],weight[y][0]));
	return ans;
}
int main(int argc,char *argv[]){
	scanf("%d%d",&n,&m);
	FOR(i,1,m,1){
		int x,y,z;
		scanf("%d%d%d",&x,&y,&z);
		Ori_Add_Edge(x,y,z,i);
	}
	kruskal();
	FOR(i,1,n,1){
		if(!visited[i]){
			depth[i] = 1; DFS(i);
			doubly[i][0] = i;
			weight[i][0] = INT_MAX;
		}
	}
	LCAinit();
	int q;
	scanf("%d",&q);
	FOR(i,1,q,1){
		int l,r;
		scanf("%d%d",&l,&r);
		int ans = LCA(l,r);
		print(ans);
	}
	return 0;
}

Day2 T1

题目链接 - LuoguP1969

同时也是NOIp2018 Day1T1

Solution

考虑贪心.

首先把第一位读入进来,存入答案.

然后枚举整个数列,每次用下一个数与当前数比较:

  • 若下一位大于这一位,就说明已经放的积木不够,答案加上当前数与上一个数的差
  • 若下一位小于或等于这一位,说明已经放的积木够了,不需要更新答案.

Code

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
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
/* Headers */
#include<cstdio>
#include<cstring>
#include<cmath>
#include<cctype>
#include<algorithm>
#include<vector>
#include<queue>
#include<stack>
#include<climits>
#include<iostream>
#include<map>
#define FOR(i,a,b,c) for(int i=(a);i<=(b);i+=(c))
#define ROF(i,a,b,c) for(int i=(a);i>=(b);i-=(c))
#define FORL(i,a,b,c) for(long long i=(a);i<=(b);i+=(c))
#define ROFL(i,a,b,c) for(long long i=(a);i>=(b);i-=(c))
#define FORR(i,a,b,c) for(register int i=(a);i<=(b);i+=(c))
#define ROFR(i,a,b,c) for(register int i=(a);i>=(b);i-=(c))
#define lowbit(x) x&(-x)
#define LeftChild(x) x<<1
#define RightChild(x) (x<<1)+1
#define RevEdge(x) x^1
#define FILE_IN(x) freopen(x,"r",stdin);
#define FILE_OUT(x) freopen(x,"w",stdout);
#define CLOSE_IN() fclose(stdin);
#define CLOSE_OUT() fclose(stdout);
#define IOS(x) std::ios::sync_with_stdio(x)
#define Dividing() printf("-----------------------------------\n");
namespace FastIO{
    const int BUFSIZE = 1 << 20;
    char ibuf[BUFSIZE],*is = ibuf,*its = ibuf;
    char obuf[BUFSIZE],*os = obuf,*ot = obuf + BUFSIZE;
    inline char getch(){
        if(is == its)
            its = (is = ibuf)+fread(ibuf,1,BUFSIZE,stdin);
        return (is == its)?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]);
    }
    inline void space(bool x){
    	if(!x) putch('\n');
    	else putch(' ');
    }
}
inline void read(int &x){
    int rt = FastIO::getint();
    x = rt;
}
inline void print(int x,bool enter){
    FastIO::putint(x);
    FastIO::flush();
    FastIO::space(enter);
}
/* definitions */
int n,ans;
/* functions */
int main(int argc,char *argv[]){
	scanf("%d",&n); scanf("%d",&ans);
	int last = ans;
	FOR(i,2,n,1) {
		int x; scanf("%d",&x);
		if(x > last) ans += (x - last);
		last = x;
	}
	printf("%d\n",ans);
	return 0;
}

Day2 T2

题目链接 - LuoguP1970

Solution

首先,题目要求的数列是在给定数列的基础上,去掉一些数之后,满足每一个数都是相邻三个数中最大的或最小的.

那么我们考虑dp

设$dp_{i,0/1}$表示前$i$个数选择满足条件$1/2$的最大长度.

那么显然目标状态是$\max(dp_{n,0},dp_{n,1})$

考虑如何转移, 这里我们就要考虑当前的数是选择满足条件$1$还是条件$2$了.

我们还是拿第$2 \dots n$个数和前面那个数比较:

若下一位大于这一位

  • 如果让此元素满足条件$1$并选它,那么答案应为令这一位元素满足条件$2$时的最大长度$+1$; 如果不选, 那么答案应直接继承上一位的答案.
  • 如果让此元素满足条件$2$,就只能继承前一个点的答案.

若下一位小于这一位

和上面的推导过程类似,对称考虑即可.

若下一位等于这一位

因为这两个元素完全等价,那么直接继承前一个点的答案即可.

Code

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
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
/* Headers */
#include<cstdio>
#include<cstring>
#include<cmath>
#include<cctype>
#include<algorithm>
#include<vector>
#include<queue>
#include<stack>
#include<climits>
#include<iostream>
#include<map>
#define FOR(i,a,b,c) for(int i=(a);i<=(b);i+=(c))
#define ROF(i,a,b,c) for(int i=(a);i>=(b);i-=(c))
#define FORL(i,a,b,c) for(long long i=(a);i<=(b);i+=(c))
#define ROFL(i,a,b,c) for(long long i=(a);i>=(b);i-=(c))
#define FORR(i,a,b,c) for(register int i=(a);i<=(b);i+=(c))
#define ROFR(i,a,b,c) for(register int i=(a);i>=(b);i-=(c))
#define lowbit(x) x&(-x)
#define LeftChild(x) x<<1
#define RightChild(x) (x<<1)+1
#define RevEdge(x) x^1
#define FILE_IN(x) freopen(x,"r",stdin);
#define FILE_OUT(x) freopen(x,"w",stdout);
#define CLOSE_IN() fclose(stdin);
#define CLOSE_OUT() fclose(stdout);
#define IOS(x) std::ios::sync_with_stdio(x)
#define Dividing() printf("-----------------------------------\n");
namespace FastIO{
    const int BUFSIZE = 1 << 20;
    char ibuf[BUFSIZE],*is = ibuf,*its = ibuf;
    char obuf[BUFSIZE],*os = obuf,*ot = obuf + BUFSIZE;
    inline char getch(){
        if(is == its)
            its = (is = ibuf)+fread(ibuf,1,BUFSIZE,stdin);
        return (is == its)?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]);
    }
    inline void space(bool x){
    	if(!x) putch('\n');
    	else putch(' ');
    }
}
inline void read(int &x){
    int rt = FastIO::getint();
    x = rt;
}
inline void print(int x,bool enter){
    FastIO::putint(x);
    FastIO::flush();
    FastIO::space(enter);
}
/* definitions */
const int MAXN = 1e6 + 10;
int n,dp[MAXN][2],h[MAXN];
/* functions */
int main(int argc,char *argv[]){
	scanf("%d",&n);
	FOR(i,1,n,1) scanf("%d",&h[i]);
	dp[1][0] = dp[1][1] = 1;
	FOR(i,2,n,1) {
		if(h[i] > h[i - 1]) {
			dp[i][0] = std::max(dp[i-1][0],dp[i-1][1] + 1);
			dp[i][1] = dp[i-1][1];
		}
		else if(h[i] < h[i - 1]) {
			dp[i][0] = dp[i-1][0];
			dp[i][1] = std::max(dp[i-1][1],dp[i-1][0] + 1);
		}
		else {
			dp[i][0] = dp[i-1][0];
			dp[i][1] = dp[i-1][1];
		}
	}
	printf("%d\n",std::max(dp[n][0],dp[n][1]));
	return 0;
}

Day2 T3

博主太菜了,这题还没补,暂时先鸽着吧….

THE END