题目链接:https://ac.nowcoder.com/acm/contest/19483/F
简要题意:给出一个长为10的数组,其中仅含0-9且每个数恰好出现一次。给出一个操作集,每次操作可以调换两个数。现在仅针对集合中[l,r]的一小段进行操作,求操作结果
这里采用的是广义前缀和的思想,当连续的操作产生某个叠加影响时,这种影响可以通过某种反向操作进行撤销。
我们假设第i次操作后状态为a[i],初状态为a[0],经过一系列操作后变成状态B,再经一系列操作后变状态A。
如下图,a[0]={1,2,3}经转换先变成B={3,1,2},再变成A={x,y,z}。
下面考虑的问题就是,如何在A中抵消掉从a[0]走到B的所有操作?
观察可知,如果B要转回a[0],第1位的数字3需要放回第3位,第2位的数字1需要放回第1位,第3位的数字2需要放回第2位。
也就是说,对于任何一种状态A,只需把第1位的数字放回第3位,第2位的数字放回第1位,第3位的数字放回第2位,即变成{y,z,x},就能抵消掉a[0]到B的交换作用
所以,我们可以用tmp数组记录B的每个位置需要放回的位置,如本例就是tmp[1]=3,tmp[2]=1,tmp[3]=2.这样的话,tmp就完成了从状态B到a[0]的位置映射。
接下来只需要把tmp的映射作用于A,就能得到结果啦。
代码如下:
#include <bits/stdc++.h> using namespace std; #define _for(i,a,b) for(int i=(a);i<=(b);i++) int a[100010][10]; int tmp[10]; int ans[10]; int main(){ int n,m; scanf("%d %d",&n,&m); _for(i,0,9) a[0][i]=i;//初始化 _for(i,1,n){ memcpy(a[i],a[i-1],sizeof(a[i-1]));//复制上一次的结果 int x,y; scanf("%d %d",&x,&y); swap(a[i][x],a[i][y]); } while(m--){ int x,y; scanf("%d %d",&x,&y); _for(i,0,9) tmp[a[x-1][i]]=i;//得到从状态x-1回到初状态的映射函数 _for(i,0,9) ans[i]=tmp[a[y][i]];//将映射函数作用于状态y _for(i,0,9) printf("%d%c",ans[i]," \n"[i==9]); } return 0; }