【牛客OJ】牛牛的猜球游戏(广义前缀和)

 

 解题思路：

先看题目，给了10个球，放在初始位置，然后再给一串 *** 作序列，要求的是在经历某个区间内所有 *** 作后各个位置的球的编号。乍看之下貌似和前缀和有点像，前缀和是给几个数字，然后求给定区间内的数字的和，这里的 *** 作序列就是加法。所以可以利用(广义)前缀和的思想进行处理。

前缀和的灵魂就是预处理 *** 作序列(在狭义前缀和中就是求区间 (0,r] 中数字的和)以及抵消前置 *** 作(在狭义前缀和中就是 sum[r]-sum[l-1] *** 作，因为sum[r]和sum[l]中有相同的部分，进行相减 *** 作就能把前置相加 *** 作给抵消)

这道题的预处理 *** 作序列就是根据题意进行球的交换，代码如下：

    for(int i=1;i<=n;i++){
        memcpy(ball[i],ball[i-1],sizeof(ball[i-1]));
        int x,y;
        cin>>x>>y;
        swap(ball[i][x], ball[i][y]);
    }

然后就到了这道题的难点：抵消前置 *** 作。

先假定刚开始有4个球，编号分别为1，2，3，4，对应位置的球的编号分别为1，2，3，4。

ball[1]=1,ball[2]=2,ball[3]=3,ball[4]=4

然后在经历一系列 *** 作后，对应位置的球的编号分别位3，4，2，1。

ball[1]=3,ball[2]=4,ball[3]=2,ball[4]=1

抵消前置 *** 作，还原为初始状态的 *** 作就是：

ball[i]=i

相关代码为：

for(int i=0;i<=9;i++){
        temp[ball[l-1][i]]=i;
    }

然后是对还原后的状态进行 *** 作，可以把区间的 *** 作定义为一个映射，因为要进行的 *** 作和球的位置没有关系，不管球的编号是什么，某个位置的球一定会移动到对应的另一个位置，所以可以利用映射将要进行的 *** 作保存下来。

相关代码为：

for(int i=0;i<=9;i++){
        ans[i]=temp[ball[r][i]];
    }

可以这样理解：位置l-1的对应位置的球都带上了一个货物，即对应位置的初始球，然后这些初始球跟着l-1的球通过映射到达指定位置，最后把初始球给拿出来，这样就实现了对初始球进行对应区间内的 *** 作的目标。

到这里问题就顺利解决了。

完整代码如下:

#include 
using namespace std;

int n,m;
int ball[200000][10];
int ans[10];

int main(){
    cin>>n>>m;
    for(int i=0;i<=9;i++){
        ball[0][i]=i;
    }
    for(int i=1;i<=n;i++){
        memcpy(ball[i],ball[i-1],sizeof(ball[i-1]));
        int x,y;
        cin>>x>>y;
        swap(ball[i][x], ball[i][y]);
    }
    while(m--){
        int l,r;
        cin>>l>>r;
        int temp[20];
        for(int i=0;i<=9;i++){
            temp[ball[l-1][i]]=i;
        }
        for(int i=0;i<=9;i++){
            ans[i]=temp[ball[r][i]];
        }
        for(int i=0;i<=9;i++){
            printf("%d%c",ans[i],i!=9?' ':'\n');
        }
    }
    return 0;
}