列表

详情

NC21525. 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:


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).

示例1

输入: 

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

输出: 

Yes
Yes
No

原站题解

import java.util.Scanner;
public class Main {
public static void main(String[] arg) {
Scanner scanner = new Scanner(System.in);
// todo
}
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

C++14(g++5.4) 解法, 执行用时: 273ms, 内存消耗: 16268K, 提交时间: 2018-12-03 19:36:20 

#include<bits/stdc++.h>

using namespace std;

const int MAXN=1e6+10;

int n,a[MAXN],p[MAXN],top,S[MAXN],g[MAXN];

bool ok(int x){

    for(int i=1;i<=n;i++) g[i]=0;

    for(int i=x;i+1<=n;i+=2){

        int l=p[i],r=p[i+1]; if(l>r)swap(l,r);

        g[l]=r; g[r]=-r;

    }

    top=0;

     for(int i=1;i<=n;i++) {

        if(g[i]>0)S[++top]=g[i];

        else if(g[i]<0){

            if(S[top]!=-g[i])return false;

            top--;

        }

    }

    return true;

}

 

int main(){

    int T;scanf("%d",&T);

    while(T--){

        scanf("%d",&n);

         for(int i=1;i<=n;i++) scanf("%d",&a[i]),p[a[i]]=i;

        if(ok(2)&&ok(1)) puts("Yes");

        else puts("No");

    }

}

C++11(clang++ 3.9) 解法, 执行用时: 277ms, 内存消耗: 9700K, 提交时间: 2020-03-15 21:43:56 

#include<iostream>

using namespace std;

const int maxn=1e6+50;

int s[maxn],a,g[maxn],zb[maxn];

int top,n;

bool solve(int x)

{

    top=0;

    for(int i=0;i<=n;++i) g[i]=0;

    for(int i=x;i<n;i+=2)

    {

        int l=zb[i],r=zb[i+1];

        if(l>r) swap(l,r);

        g[l]=r;

        g[r]=-r;

    }

    for(int i=1;i<=n;++i)

    {

        if(g[i]>0) s[++top]=g[i];

        else if(g[i]<0)

        {

            if(s[top]!=-g[i]) return false;

            top--;

        }

    }

    return true;

}

int main()

{

    int T;

    cin>>T;

    while(T--)

    {

        cin>>n;

        for(int i=1;i<=n;++i) scanf("%d",&a),zb[a]=i;

        if(solve(1)&&solve(2)) cout<<"Yes\n";

        else cout<<"No\n";

    }

}

上一题

© 2025 nowcoder.com