171 t3

· · 题解

因为t1,t2太水所以不发题解了

咳咳，回归正题

T3

做法 1:按照题意模拟，期望得分 30pts .

做法 2:环形字符串(?

维护一个 nxt 数组存放 s_i 的下一个字符是什么。

同理，维护一个 pre 数组存档 s_i 的前一个字符是什么。

然后我们用 pos 来存放顺序输出时第 1 个字符的位置 , 再用 fac 来表示我们用什么顺序来输出。

(说白了就是正序和倒序)

所以我们可以按照题意和我们的思路模拟，每次 O(1).

注意每次 rev 时 pos 的转向都会改变.

时间复杂度 O(n).

Solution

#include<iostream>
#include<algorithm>
#include<cmath>
#define rep(a,b,c) for(int a=b;a<=c;a++)
using namespace std;
typedef long long ll;
string s;
int n;
int p;
string str;
int pre[1000010],nxt[1000010];
int fac,pos;
int k;
void print() {
    int writed=0;
    if(fac==1) {
        int now=pos;
        while((writed++)<p)
            cout<<s[now],now=nxt[now];
    } else {
        int now=pos,top=0;
        char ch[1000100];
        while((writed++)<p)
            ch[++top]=s[now],now=nxt[now];
        for(int i=top; i>=1; i--) cout<<ch[i];
    }
    cout<<endl;
}
int left(int x,int step) {
    int kk=0,q=x,sf=step;
    if(sf>p) {
        ll kp=sf/p;
        sf-=p*kp;
    }
    if(x-sf<0) {
        sf-=x;
        q=p-sf;
    }
    else q-=sf;
    return q;
}
int right(int x,int step) {
    int q = (x+step)%p;
    return q;
}
int main()
{
    cin.tie(0);
    cout.tie(0);
    cin>>s>>n;
    p=s.size();
    rep(i,1,s.size()-1) pre[i]=i-1;
    rep(i,0,s.size()-2) nxt[i]=i+1;
    pre[0]=s.size()-1;
    nxt[s.size()-1]=0;
    fac=1;
    rep(i,1,n) {
        cin>>str;
        if(str!="rev") {
            cin>>k;
            if(str==">") {
                 if(!fac)
                     pos=right(pos,k);
                 else
                     pos=left(pos,k);
                 //cout<<s<<endl;
            } else {
                 if(!fac)
                     pos=left(pos,k);
                 else
                     pos=right(pos,k);
                 //cout<<s<<endl;
            }
        } else {
            if(fac==0) fac=1;
            else fac=0;
        }
    }
    print();
    return 0;
}

欢迎对拍