AquaRio 的博客

AquaRio 的博客

题解 P3095 【[USACO13DEC]贝西洗牌The Bessie Shuffle】

posted on 2019-09-30 22:33:48 | under 题解 |

食用效果更佳:我的博客

既然没有正解,那我就来写一发把。

思路:

我们对问题仔细研究,很快就会发现,问题就是给定一个位置 $x$ ,问它经过若干轮置换后会到达哪个位置。

值得注意的是我们需要对置换做出一些调整,因为每次都会删除头部的元素,所以真实的置换是 $p[i]-1$ 。

举个栗子:

$[1, 2, 3, 4, 5] -> [2, 3, 1, 4, 5] -> [3,1,4,5]$

在这里面, $p[1]=3$ ,但是 $1$ 在置换到 $3$ 号位置的时候, $2$ 被弹了出来,所以 $1$ 实际上换到的位置是 $p[1]-1=2$ 。

我们瞄一眼数据范围, $1e5$ 好吓人,我们必须找出一种带有 $\log$ 的方法来求出每一个询问的数置换的最终位置。

灵机一动,倍增

我们设 $a[i][j]$ 表示 $j\ (1 \leq j \leq m) $ 在置换 $2^{i}$ 次后的位置。

于是我们就可以找到最终位置辣 (>_<)

但是要注意当中途走到 $0$ 时,说明离开了队列,应及时终止。

代码:

/*
    Name: P3095 [USACO13DEC]贝西洗牌The Bessie Shuffle
    Author: AquaRio
    Date: 30/09/19 22:01
    State: Accepted
    Anti_Copy: Enabled 
*/

#include<bits/stdc++.h>
using namespace std;

const int N=100005,M=30;

int n,m,q;
int a[M][N];

inline int read(){
    int x=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9') {if(ch=='-'){f=-1;}ch=getchar();}
    while(ch>='0'&&ch<='9') {x=x*10+ch-'0';ch=getchar();}
    return x*f;
}

int main(){
//  freopen("testdata.in","r",stdin); 
    n=read();m=read();q=read();
    for(int i=m;i;i--){
        int x=read();
        a[0][m-x+1]=i-1;//注意置换是P[i]-1 
    }
    for(int i=1;i<M;i++)
        for(int j=1;j<=m;j++)
            a[i][j]=a[i-1][a[i-1][j]];//倍增预处理
    int x,r,len;
    while(q--){
        x=read();
        if(x<m) r=m;
        else r=x,x=m;
        len=n-r+1;  
        for(int i=M-1;~i;i--)
            if((1<<i)<=len && a[i][x]) 
                x=a[i][x],len-=1<<i,r+=1<<i;//倍增查找最终位置 
        if(len) x=a[0][x],r++;//注意弹出去
        cout<<n-r+m-x+1<<endl; 
    } 
    return 0;
}