题解：P14405 [JOISC 2015] 复制粘贴 2 / Copy and Paste 2

· · 题解

\textup{P14405 [JOISC 2015] 复制粘贴 2}

\textup{Link} | 更好体验 | \textup{Tag: }模拟，不明白为啥标签是动规。

模拟赛 T1。

\textup{Description}

给定字符串和操作，每个操作会复制一段串中文本并插入到给定的位置。

要求输出前 K 个操作过后的字符。

\textup{Solution}

暴力对正解几乎没有贡献，所以不赘述了。

:::error[\textup{10 pts.}]

int K, M, N, l, r, x;
string s;
void slove(){
    cin >> K >> M >> s >> N;
    for( int i = 1; i <= N; i ++ ){
        cin >> l >> r >> x;
        string k, t;
        for( int i = l; i < min( M, r ); i ++ ){
            k += s[i];
        }
        for( int i = 0; i < min( M, x ); i ++ ){
            t += s[i];
        }
        t += k;
        for( int i = x; i < min( M, (int)s.size() ); i ++ ){
            t += s[i];
        }
        s = t;
    }
    for( int i = 0; i < K; i ++ ) cout << s[i];
}

:::

考虑到 K \le 200 非常突兀，于是从这里入手。

最后我们只需要知道前面 K 个，于是我们逐个去寻找它们的来时路。

自然而然可以想到实现，我们对于每个位置 p \le K，反着从每一个操作，逆推上一次来的位置。

假设当前在第 i 个操作，考虑对于每个区间的影响：

这个是顺推的操作，我们把它逆过来就得到了：

按照意思模拟就行啦，复杂度 O(NK)。

\textup{Code}

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int MAXN = 2e5 + 10;
const int inf = 0x3f3f3f3f3f3f3f3f;
const int MOD = 1e9 + 7;
int K, M, N, l[MAXN], r[MAXN], x[MAXN];
string s;
void slove(){
    cin >> K >> M >> s >> N;
    for( int i = 1; i <= N; i ++ ){
        cin >> l[i] >> r[i] >> x[i];
    }
    for( int j = 0; j < K; j ++ ){
        int p = j;//在当前这一步之后在串里面的下标
        for( int i = N; i >= 1; i -- ){//反过来一遍一遍推
            int len = r[i] - l[i];
            if( p >= x[i] )
                p = ( p < x[i] + len ) ? l[i] + ( p- x[i] ) : p - len;
        }
        cout << s[p];
    }
}

signed main(){
    ios::sync_with_stdio( 0 );
    cin.tie( 0 ), cout.tie( 0 );
    // freopen( "copy.in", "r", stdin );
    // freopen( "copy.out", "w", stdout );
    int T = 1;
    // cin >> T;
    while( T -- )
        slove();
    return 0;
}

\textup{Last}

审核管理员辛苦了，如果您有所疑惑或我有所错漏，请您在评论区指出或找我，我会一定解答并且修改本题解。

如果您觉得本文写的还不错，那可以留个赞吗？

谢谢你看到这里~