CSU 2018年12月月赛 B 2214: Sequence Magic

偏执的太偏执、 2021-09-30 13:52 229阅读 0赞

## Description ##

有一个1到N的自然数序列1,2,3,...,N-1,N。

我们对它进行M次操作，每次操作将其中连续的一段区间 \[Ai,Bi\]\[Ai,Bi\] (即第Ai个元素到第Bi个元素之间的一段)取出，然后插入到剩下的第Ci个元素的后面，如果Ci=0，表示插入到最左端。

现在，M次操作完后，有K个询问，每个询问Pi表示询问最终第Pi个元素是几。你的任务是写一个程序，依次回答这K个询问。

## Input ##

第一行三个数，N，M，K。

接下来M行，每行三个整数Ai,Bi,Ci。

接下来K行，每行一个正整数Pi。

1<=N<=109，1<=M<=104，1<=K<=1000，1<=Ai<=Bi<=N，0<=Ci<=N-(Bi-Ai+1)，1<=Pi<=N；

## Output ##

输出共K行，为每次询问的答案。

## Sample Input ##

13 3 13 
    6 12 1 
    2 9 0 
    10 13 8 
    1 
    2 
    3 
    4 
    5 
    6 
    7 
    8 
    9 
    10 
    11 
    12 
    13

## Sample Output ##

6 
    7 
    8 
    9 
    10 
    11 
    12
    2 
    3 
    4 
    5 
    13 
    1 
    
    题解：经典思路，先离线下来，然后倒推。

#include <iostream> #include <cstring> #include <cstdio> #include <algorithm> #include <math.h> #include <set>
    using namespace std; const int maxn=10005; int n,m,k,x; //map<int,int>ma;
    int a[maxn],b[maxn],c[maxn]; int main() { scanf("%d %d %d",&n,&m,&k); // for(int i=1;i<=n;i++) // ma[i]=i;
        for(int i=1;i<=m;i++) scanf("%d %d %d",&a[i],&b[i],&c[i]); while(k--) { scanf("%d",&x); for(int i=m;i>0;i--) { int t=b[i]-a[i]+1; if(x>=(min(c[i]+1,a[i]))&&x<=(max(c[i]+t,b[i]))) { if(x<=c[i]) x+=t; else if(x>c[i]+t) x-=t; else x+=(a[i]-c[i]-1); } } printf("%d\n",x); } return 0; } /********************************************************************** Problem: 2214 User: therang Language: C++ Result: AC Time:180 ms Memory:2140 kb **********************************************************************/

转载于:https://www.cnblogs.com/jkzr/p/10163596.html