Origami【栈】

字节跳动冬令营网络赛

Chiaki has a very big sheet of paper. This sheet has a form of rectangle with dimensions 1 x n and numbers from 1 to n was written on each small 1 x 1 grid. Chiaki would like to fold the paper using the following operations:

Fold the sheet of paper at position pi to the right. After this query the leftmost part of the paper with dimensions 1 x pi must be above the rightmost part of the paper with dimensions ).
Fold the sheet of paper at position pi to the left. After this query the rightmost part of the paper with dimensions ) must be above the leftmost part of the paper with dimensions 1 x pi.

After performing the above operations several times, the sheet of paper has dimensions 1 x 1. If we write down the number on each grid from top to bottom, we will have a permutation of n.
Now given a permutation of n, Chiaki would like to know whether it is possible to obtain the permutation using the above operations.

输入描述:

There are multiple test cases. The first line of the input contains an integer T, indicating the number of test cases. For each test case:
The first line contains an integer n (1 ≤ n ≤ 106), indicating the length of the paper.
The second line contains n integers a1, a2, …, an, which is a permutation of n, indicating the integers marked in the grids of the resulting sheet of paper from top to bottom.
It’s guaranteed that the sum of n in all test cases will not exceed 106.

输出描述:

For each test case output one line. If it’s possible to obtain the permutation, output ‘‘Yes’’ (without the quotes), otherwise output ‘‘No’’ (without the quotes).

示例

输入
3
4
2 1 4 3
7
2 5 4 3 6 1 7
4
1 3 2 4
输出
Yes
Yes
No

假如一张纸体积为7

1 2 3 4 5 6 7

经过几次折叠后，折成体积为1

从上往下的数字为一个排列，问给一个排列，是否能折出来

解：

从1开始依次连线，每个数字的左右只能连一次
这些线如果交叉则非法

这样对于左边和右边就变成了两组区间，对于一边的所有区间，区间只能包含，不能交叉
如左边的区间有:

(1,4)(2,3)(5,7)(1,4)(2,3)(5,7)

区间直接不能交叉

AC 代码

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
#include<iostream>
#include<algorithm>
#include<stdio.h>
#include<string.h>
#include<stack>
#include<vector>
using namespace std;
int a[1000006];
int pos[1000006];
int b[1000006];
int n;
struct node
{
	int x, y;
	node() {}
	node(int a, int b) { x = min(a, b); y = max(a, b); }
	bool operator<(node n)
	{
		if (x == n.x)
			return y < n.y;
		return x < n.x;
	}
};
vector<node>L, R;
bool check(vector<node>&v)
{
	memset(b, 0,4*(n+2));
	stack<int>st;
	for (int i = 0; i < v.size(); i++)
	{
		b[v[i].x] = i + 1;
		b[v[i].y] = -i - 1;
	}
	for (int i = 1; i <= n; i++)
	{
		if (b[i] > 0)
			st.push(b[i]);
		else if (b[i] < 0)
			if (st.top() + b[i] == 0)
				st.pop();
			else return false;
	}
	return true;
}
int main()
{
	int T;
	while (~scanf("%d", &T))
	{
		while (T--)
		{
			L.clear();
			R.clear();
			scanf("%d", &n);
			for (int i = 1; i <= n; i++)
			{
				scanf("%d", &a[i]);
				pos[a[i]] = i;
			}
			int flag = 0;
			for (int i = 1; i < n; i++)
			{
				node t = node(pos[i], pos[i + 1]);
				if (flag == 0)
					L.push_back(t);
				else
					R.push_back(t);
				flag ^= 1;
			}
			if (check(L) && check(R))
				printf("Yes\n");
			else
				printf("No\n");
		}
	}
}