题解 P1188 【PASTE】

囧仙

2020-08-15 16:09:03

Solution

## 题目大意 有 $n$ 个数 $1,2,\cdots n$ 。 $m$ 次操作。每次取出 $[A_i,B_i]$ 段,删除后插入第 $C_i$ 个位置后面。输出操作结束后前 $10$ 个数字。 ## 题解 观察到题目只要我们输出前 $10$ 个数字,所以其他地方是什么数字不需要在意。 考虑到题目给出的操作形式比较难以处理,我们转换成 $(S_i,T_i,L_i)$ ,表示第 $i$ 个操作将 $[S_i,S_i+L_i)$ 移动到了 $[T_i,T_i+L_i)$ 。 观察到,操作 $(S_i,T_i,L_i)$ 是可逆的,其逆操作为 $(T_i,S_i,L_i)$ 。于是,我们可以将 $m$ 个操作倒过来做,反推出第 $i (i\in[1,10])$ 个地方原先是哪个地方的数字。分类讨论每个逆操作对当前位置 $t$ 的影响。 - 如果逆操作移动的区间包含了当前的 $t$ ,则令 $t\gets t+T_j-S_j$ 。 - 如果逆操作在 $t$ 之前,且这段区间移动后到了 $t$ 的后面,则令 $t\gets t-L_j$ 。 - 如果逆操作在 $t$ 之后,且这段区间移动后到了 $t$ 的前面,则令 $t\gets t+L_j$ 。 最后我们就能反推出 $t$ 原先在哪。由题意可得初始时第 $i$ 个位置放了 $i$ 。 ## 参考代码 ```cpp #include<bits/stdc++.h> #define up(l,r,i) for(int i=l;i<=r;i++) #define dn(l,r,i) for(int i=l;i>=r;i--) using namespace std; typedef long long LL; const int INF =2147483647; int qread(){ int w=1,c,ret; while((c=getchar())> '9'||c< '0') w=(c=='-'?-1:1); ret=c-'0'; while((c=getchar())>='0'&&c<='9') ret=ret*10+c-'0'; return ret*w; } const int MAXN =1e3+3; int n,m,S[MAXN],T[MAXN],L[MAXN]; int main(){ n=qread(),m=qread(); up(1,m,i){ int a=qread(),b=qread(),c=qread(); L[i]=b-a+1,S[i]=c+1,T[i]=a; } up(1,10,i){ int t=i; dn(m,1,j){ if(S[j]<=t&&t<=S[j]+L[j]-1) t+=T[j]-S[j]; else if(S[j]> t&&T[j]<=t) t+=L[j]; else if(S[j]< t&&t-L[j]<T[j]) t-=L[j]; } printf("%d\n",t); } return 0; } ``` 复杂度 $\mathcal O(k\times m)$ ,其中 $k$ 为要求我们输出的数字的个数,该题中为 $10$ 。