CF#637 C. Nastya and Strange Generator

C. Nastya and Strange Generator

题意

有一个随机全排列生成器，给出你一个全排列，让判断是否可以通过这个生成器产生。

生成器工作方式：

第i步为数字i寻找位置pos。

首先pos是一个空位置，定义每个空位置的价值为左边连续有数字的位置数，会为数字i在价值最大的一个或者多个位置中选择一个位置。

比如上图，第三个位置的值是2，第4个位置的值是0，这时4就选择了第3个位置。

思路

写一下就会发现，这个生成器生成的全排列是有规律的。

n的全排列

x+y+1 x+y+2.....n x+1 x+2... x+y 1 2 3 4.......x

可以知道如果当前位小于后一位，一定是小1。如果有不是小1的，就说明不能通过生成器生成

代码

#include<bits/stdc++.h>

#define pb push_back

using namespace std;

typedef long long ll;

const int N=2e5+10;

const int mod=1e9+7;

const int inf=0x3f3f3f3f;

int arr[N],vis[N];

int main()

{

    int T;

    scanf("%d",&T);

    while(T--)

    {

        int n;

        scanf("%d",&n);

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

            scanf("%d",&arr[i]);

        int flag=0;

        for(int i=n;i>1;i--)

        {

            if(arr[i]>arr[i-1])

            {

                if(arr[i]-arr[i-1]!=1)

                {

                    flag=1;

                    break;

                }

            }

        }

        if(flag) printf("No\n");

        else printf("Yes\n");

    }

    return 0;

}

巴特西

CF#637 C. Nastya and Strange Generator

C. Nastya and Strange Generator

题意

思路

代码

最新文章

热门文章