20162017-acmicpc-south-pacific-regional-contest-sppc-16 B.Ballon Warehouse

题意:给你一个无限长且元素均为\(0\)的排列,每次给你一对\((x,y)\)，表示在所有\(x\)的后面插入一个元素\(y\),最后给你一个区间\((l,r)\),输出\([l,r-1]\)中的所有元素.
题解:我们用一个vector和pair来存储每次输入的\((x,y)\),显然,在\(x\)后插入的最后一个数一定是\(x\)后的第一个数,所以我们将按顺序插入的pair全部倒置一下,然后从\(0\)开始dfs:x表示颜色,pos表示位置

我们知道这个排列其实是一个循环节,记\(col\)数组是循环节的元素,\(cnt\)是循环节的长度,长度最多取到\(r\)就行了.

假如\(x\)后面的数的位置大于当前x的位置,那么就不断dfs的去找,用\(col\)来记录.这里最难的就是这个位置的理解,要自己好好推一推！！！.

姑且可以这么认为:pos大的在前面,pos小的在后面,只有v[x].pos>pos才可以dfs下去

最后按循环节来输出即可.

代码:

#include <iostream>

#include <cstdio>

#include <cstring>

#include <cmath>

#include <algorithm>

#include <stack>

#include <queue>

#include <vector>

#include <map>

#include <set>

#include <unordered_set>

#include <unordered_map>

#define ll long long

#define fi first

#define se second

#define pb push_back

#define me memset

const int N = 1e6 + 10;

const int mod = 1e9 + 7;

using namespace std;

typedef pair<int,int> PII;

typedef pair<long,long> PLL;

int n;

int l,r;

int a,b;

int cnt;

int col[N];

vector<PII> v[N];

void dfs(int x,int pos){

    if(cnt>=r) return;

     col[cnt++]=x;

     for(auto w:v[x]){

         if(w.se>pos){

             printf("%d\n",w.fi);

             dfs(w.fi,w.se);

         }

         else return;

     }

}

int main() {

    ios::sync_with_stdio(false);

    cin>>n>>l>>r;

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

         cin>>a>>b;

         v[a].pb({b,i});

     }

     for(int i=0;i<N;++i){

         if(!v[i].empty()) reverse(v[i].begin(),v[i].end());

     }

     dfs(0,0);

     for(int i=l;i<r;++i){

         printf("%d ",col[i%cnt]);

     }

     puts("");

    return 0;

}

巴特西

20162017-acmicpc-south-pacific-regional-contest-sppc-16 B.Ballon Warehouse

最新文章

热门文章