https://codeforces.com/contest/1647
E. Madoka and the Sixth-graders
题意:房间里有 n n n 个座位,第 i i i 个座位上的人的编号为 b i ∈ { 1 , 2 , ⋯ , n } b_i\in\{1,2,\cdots,n\} b i ∈ { 1 , 2 , ⋯ , n } ,每一轮座位 i i i 上的人移动到座位 p i ∈ { 1 , 2 , ⋯ , n } p_i\in \{1, 2,\cdots,n\} p i ∈ { 1 , 2 , ⋯ , n } ,若多个人移到同一个座位,则编号最小的人留下,其他人永远离开游戏。房间外有无限多的人,编号为 n + 1 , n + 2 , ⋯ n+1,n+2,\cdots n + 1 , n + 2 , ⋯ ,每一轮移动后必定空出座位,房间外的人按编号顺序坐到空座位上。经过若干轮后,最终座位 i i i 上的人的编号为 a i a_i a i 。给定 a i , p i a_i,p_i a i , p i ,问初始排列 b i b_i b i ,保证有解,输出字典序最小的解。
倍增
把 p p p 建成图,入度为 0 0 0 的就是空座位,且每轮都一样。通过空座位上的人的编号可以知道游戏进行了几轮,记为 C C C 。
倍增得到 C C C 轮后初始每个座位上的人会移动到哪个座位(如果中间没死的话)。
假设 { x 1 , x 2 , x 3 } \{x_1, x_2, x_3\} { x 1 , x 2 , x 3 } 最终能够移动到座位 i i i ,最终活下来的 a [ i ] a[i] a [ i ] ,一定是 { b [ x 1 ] , b [ x 2 ] , b [ x 3 ] } \{b[x_1],b[x_2],b[x_3]\} { b [ x 1 ] , b [ x 2 ] , b [ x 3 ]} 中编号最小的人,由于题目要求字典序最小的解,所以要把这个人放在第 min { x 1 , x 2 , x 3 } \min\{x_1, x_2, x_3\} min { x 1 , x 2 , x 3 } 个座位上,其他人的编号无所谓,但是一定要小于 a [ i ] a[i] a [ i ] 。
把入度不为 0 0 0 的座位分配好之后,其他人从小到大分配,但是一定要保证被分配到坐到第 i i i 个座位上的人的编号小于第 i i i 个座位上的人最终移动到的座位上的人的编号。
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 #include <bits/stdc++.h> using namespace std;#define ll long long const int INF = 0x3f3f3f3f ;const ll inf = 0x3f3f3f3f3f3f3f3f ;const ll mod = 998244353 ;const int N = 2e5 + 10 ;typedef pair<int , int > pii;int n;int p[N], a[N], b[N], fa[N][40 ], d[N], dst[N];set<int >st; priority_queue<int , vector<int >, greater<int > >q[N]; int main () { scanf ("%d" , &n); for (int i = 1 ; i <= n; i++)scanf ("%d" , &p[i]), d[p[i]]++; for (int i = 1 ; i <= n; i++)scanf ("%d" , &a[i]); for (int i = 1 ; i <= n; i++)fa[i][0 ] = p[i]; for (int i = 1 ; i < 40 ; i++){ for (int j = 1 ; j <= n; j++){ fa[j][i] = fa[fa[j][i - 1 ]][i - 1 ]; } } int cnt = 0 , fs = 0 ; for (int i = 1 ; i <= n; i++){ if (d[i] == 0 )cnt++; if (fs == 0 && d[i] == 0 )fs = i; } int c; if (a[fs] <= n)c = 0 ; else c = (a[fs] - n - 1 ) / cnt + 1 ; for (int i = 1 ; i <= n; i++){ int tmp = c, u = i; for (int j = 0 ; j < 40 ; j++){ if (tmp & 1 )u = fa[u][j]; tmp >>= 1 ; } dst[i] = u; q[u].push (i); } for (int i = 1 ; i <= n; i++)st.insert (i); for (int i = 1 ; i <= n; i++){ if (!q[i].empty ()){ b[q[i].top ()] = a[i]; st.erase (a[i]); } } for (int i = 1 ; i <= n; i++){ if (!b[i]){ auto pp = st.upper_bound (a[dst[i]]); b[i] = *pp; st.erase (pp); } } for (int i = 1 ; i <= n; i++)printf ("%d%c" , b[i], " \n" [i == n]); return 0 ; }