【codeforces 239B】Easy Tape Programming

【题目链接】:http://codeforces.com/contest/239/problem/B

【题意】



给你一个长度为n的字符串,只包括‘<”>’以及数字0到9;

给你q个区间(n和q都小于等于100)

然后让你在这q个区间里面做一些操作;

有一个指针int,指向当前操作的位置,还有一个方向的int;

表示这个指针它要移动的方向;

每次对一个位置进行操作;

如果该位置是数字;

则把这个数字输出,然后这个数字递减1;

如果数字小于0了,则把它删掉;

然后把指针往方向int的方向移动一个单位;

如果是’>’或’<’则,把方向改成左或右;

然后往新的方向走,如果走了一步之后还是’<’或’>’

则把前一个’<’或’>’删掉;

问你最后0..9各输出了多少个;

【题解】



每次模拟一步即可;

直到cp指针跳出了区间为止;

可以用数组来模拟链表的删除过程;

对每个区间的操作,都把数组链表初始化一下即可;



【Number Of WA 】



0



【反思】



这种模拟删掉的过程用数组模拟链表的方法都比较方便；



【完整代码】

#include <bits/stdc++.h>

#define rep1(i,x,y) for (int i = x;i <= y;i++)

#define rep2(i,x,y) for (int i = x;i >= y;i--)

using namespace std;

const int N = 100+10;

int n,q,l,r,a[N][2],cp,dp,num;

int tot[10];

string s,s1;

void get_next(){

    int ll = a[cp][0],rr = a[cp][1],tcp = cp;

    if (s1[cp]>='0' && s1[cp]<='9'){

        cp = a[cp][dp];

        num++;

        tot[s1[tcp]-'0']++;

        s1[tcp]--;

        if (s1[tcp]<'0'){

            a[ll][1] = rr;

            a[rr][0] = ll;

        }

    }else{

        if (s1[cp]=='<')

            dp = 0;

        else

            dp = 1;

        cp = a[cp][dp];

        if (cp < l || cp > r) return;

        if (s1[cp]>='0' && s1[cp]<='9') return;

        a[ll][1] = rr,a[rr][0] = ll;

    }

}

int main(){

    //freopen("D:\\rush.txt","r",stdin);

    cin >> n >> q;

    cin >> s;

    s = ' ' + s;

    rep1(i,1,q){

        num = 0;

        s1 = s;

        cin >> l >> r;

        rep1(j,l,r)

            a[j][0] = j-1,a[j][1] = j+1;

        rep1(j,0,9)

            tot[j] = 0;

        cp = l,dp = 1;

        while (1){

            get_next();

            if (cp <l || cp>r) break;

        }

        rep1(j,0,9)

            cout << tot[j] <<' ';

        cout << endl;

    }

    return 0;

}