[20200728 NOIP 향상 그룹 시 뮬 레이 션 T1] 복사

제목 의 대의:
문자열 을 드 립 니 다. 그래서 $n $회 동작 이 있 습 니 다. 매번 동작 할 때마다 세 개의 변 수 를 드 립 니 다. $a, b, c $, $(a, b) $의 문 자 를 $(c, c + b - a) $의 문 자 를 삽입 합 니 다. 그 후에 검색 이 있 습 니 다. 출력 작업 후 $[1, k] $의 문 자 를 입력 하 십시오.
solution:
  k 가 비교적 작 기 때문에 우 리 는 dp 를 진행 할 수 있 습 니 다. 뒤에서 밀어 서 $[1, k] $작업 전의 위 치 를 일일이 매 거 하면 됩 니 다. $pos [i] $를 설정 하여 마지막 $i $의 문 자 를 표시 할 수 있 습 니 다. 그러면 다음 과 같은 세 가지 상황 이 있 습 니 다. 하나, $pos [i] < = c $, 그러면 이동 할 필요 가 없습니다. 둘, $pos [i] \ in (c, c + b - a] $, 그러면 $(a, b] $의 원래 위치 로 이동 합 니 다. 셋, $pos [i] > c + b - a $, 그러면 앞으로 이동 하면 됩 니 다.
code:
#include
#include
#include
#include
#include
#include
#include
#define R register
#define next kdjadskfj
#define debug pust("mlg")
using namespace std;
typedef int ll;
typedef long double ld;
typedef unsigned long long ull;
inline ll read();
inline void write(ll x);
inline void writeln(ll x);
inline void writesp(ll x);
ll k,m,n;
ll pos[250];
char wn[1010000];
ll h;
ll a[1010000],b[1010000],c[1010000];
int main(){
    freopen("copypaste.in","r",stdin);
    freopen("copypaste.out","w",stdout);
    k=read();m=read();
    char C=getchar();
    while(C<'a'||C>'z') C=getchar();
    while(C>='a'&&C<='z') wn[++h]=C,C=getchar();
    n=read();
    for(R ll i=1;i<=k;i++) pos[i]=i;
    for(R ll i=1;i<=n;i++) a[i]=read(),b[i]=read(),c[i]=read();
    for(;n;n--){
        for(R ll i=1;i<=k;i++){
            if(pos[i]<=c[n]) continue;
            if(pos[i]>c[n]+b[n]-a[n]){pos[i]-=(b[n]-a[n]);continue;}
            pos[i]=a[n]+pos[i]-c[n];
        }
    }
    for(R ll i=1;i<=k;i++) putchar(wn[pos[i]]);
}
inline ll read(){ll x=0,t=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-') t=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}return x*t;}
inline void write(ll x){if(x<0){putchar('-');x=-x;}if(x<=9){putchar(x+'0');return;}write(x/10);putchar(x%10+'0');}
inline void writesp(ll x){write(x);putchar(' ');}
inline void writeln(ll x){write(x);putchar('
');}

좋은 웹페이지 즐겨찾기