Atcoder 题解

Atcoder Beginner Contest 258 problem C 题解

题目大意

给定一个由小写字母构成的字符串$S$，有以下两种操作,每个操作输入两个数$w,x$：

• 若$w=1$，则把$S$中的最后一个字符删去，并加到$S$的开头，重复$x$次；
• 若$w=2$，则输出当前$S$中的第$x$个字符。

样例输入1

3 3
abc
2 2
1 1
2 2

样例输出1

b
a

样例解释1

• 对于第一个操作，$S$中第$2$个字符为$b$；
• 对于第二个操作，进行一次$1$操作，$S$变为$cab$
• 对于第三个操作，$S$中第$2$个字符为$a$。

样例输入2

10 8
dsuccxulnl
2 4
2 7
1 2
2 7
1 1
1 2
1 3
2 5

样例输出2

c
u
c
u

数据范围

• $2 \leq N \leq 5 \times 10^5$
• $1 \leq Q \leq 5 \times 10^5$
• $1 \leq x \leq N$
• $|S| = N$
• $S$中的字符均为小写字母
• 至少会有一个操作$2$
• $N,Q,x$都为整型数

解析

对于这个题，我们可以来了解一些string的函数：

• $S.sunstr(pos,len)$表示提取出$S$中从$pos$位置开始长度为$len$的字符串；
• $S.erase(pos,len)$表示删除$S$中从$pos$位置开始长度为$len$的字符串；

用这两个函数，我们可以写出这道题。不过这两个函数复杂度为$O(len)$的，也就是说，总的时间复杂度近似于$O(Q \times N)$，自然是不可接受的。(不过本人还是写了，放在下面。)

#include<bits/stdc++.h>
using namespace std;
int n,q;
string s;
int main()
{
    cin>>n>>q;
    cin>>s;
    while(q--){
        int ops,x;
        cin>>ops>>x;
        if(ops==1){
            string ss=s.substr(n-x,x);//取出后x个字符
            s.erase(n-x,x);//删去后x个字符
            ss+=s;//将这x个字符加到串首
            s=ss;//原串
        }
        else cout<<s[x-1]<<endl;//输出
    } 
}

(亲测可过$6$个点)

因此，我们要来想一些其他的办法。

不难发现，如果之前没有过删除添加操作的话，那么输出的字符就是从字符串的第一个字符开始数$x$个字符。

但是如果进行过删除添加操作，我们可以将字符串看作不动，而把数字符的起点向左移动(若移出了字符串左端则从右端开始继续移)，具体见下图：

因此，本题的时间复杂度便降到了$O(Q)$，完美解决。

代码实现

#include<bits/stdc++.h>
using namespace std;
int n,q;
string s;
int main()
{
    cin>>n>>q;
    cin>>s;
    int f=0; //数字符的起点
    while(q--){
        int ops,x;
        cin>>ops>>x;
        if(ops==1){
            f-=x; 
            f=(f+n)%n; //向左移x个字符，若超出左端则从右端开始继续移
        }
        else {
            int t=f+x; //从f开始数x个
            if(t>n) t-=n; //若超出右端，则从左端开始继续数
            //注意：千万不能写 t%=n，因为如果t恰好等于n，那么模出来t=0，输出的就会是s[-1]，会WA
            cout<<s[t-1]<<endl;
        }
    } 
    return 0;
}

完结撒花~