首页 > 代码库 > A Game with Colored Balls

A Game with Colored Balls

2024-07-16 22:00:34   220人阅读

题目链接

  • 题意：
    给一个长度为n的字符串，每次删除字母相同切连续的串，如果有多个，删除最左边的、最长的串。每次删除输出串的字母，每个字母的下标（1-n）
    N (1 ≤ N ≤ 106)，串只包括red (‘R’), green (‘G’) or blue (‘B’) 
  • 分析：
    题目比较麻烦，分析一下需要的任务：
    1、每次找到最长串——优先队列
    2、删除最长串后，需要合并两侧的串（如果字母相同）——加Hash的链表，set（超时）
    3、每次删除需要知道这一个区间的下标都是谁——加Hash的链表，set（超时）
C++通过，G++超时……
const int MAXN = 1100000;

struct Node
{
    int pos, len;
    char val;
    Node *nxt, *pre;
    Node (int p = 0, int n = 0, char v = 0) : pos(p), len(n), val(v) {}
    bool operator< (const Node& rhs) const
    {
        return pos < rhs.pos;
    }
    void erase()
    {
        pre->nxt = nxt;
        nxt->pre = pre;
    }
} nd[MAXN], pt, fst, lst;
int tot;

struct HeapNode
{
    int val, pos;
    HeapNode (int v = 0, int p = 0) : val(v), pos(p) {}
    bool operator< (const HeapNode& rhs) const
    {
        if (val != rhs.val)
            return val < rhs.val;
        return pos > rhs.pos;
    }
} vt;

priority_queue<HeapNode> q;
char ipt[MAXN];
bool vis[MAXN];
Node* to[MAXN], *pit, *pl, *pr;
int nxt[MAXN], pre[MAXN];

void init(int n)
{
    REP(i, n)
    {
        nxt[i] = i + 1;
        if (i)
            pre[i] = i - 1;
    }
}
void erase(int l, int r)
{
    int p = pre[l], n = nxt[r];
    nxt[p] = n;
    pre[n] = p;
}

int main()
{
    while (~RS(ipt))
    {
        fst.val = -1; fst.nxt = &lst; fst.pre = NULL;
        lst.val = -2; lst.pre = &fst; lst.nxt = NULL;
        CLR(vis, false);
        while (!q.empty())
            q.pop();
        tot = 0;
        int len = strlen(ipt);
        init(len + 2);

        nd[tot++] = Node(1, 1, ipt[0]);
        FF(i, 1, len)
        {
            if (ipt[i] == nd[tot - 1].val)
                nd[tot - 1].len++;
            else
            {
                nd[tot].pos = i + 1;
                nd[tot].len = 1;
                nd[tot].val = ipt[i];
                tot++;
            }
        }
        fst.nxt = &nd[0]; nd[0].pre = &fst;
        lst.pre = &nd[tot - 1]; nd[tot - 1].nxt = &lst;
        REP(i, tot)
        {
            if (i != 0)
                nd[i].pre = &nd[i - 1];
            if (i != tot - 1)
                nd[i].nxt = &nd[i + 1];
            to[nd[i].pos] = &nd[i];
            q.push(HeapNode(nd[i].len, nd[i].pos));
        }
        while (!q.empty())
        {
            vt = q.top();
            q.pop();
            if (vt.val == 1)
                break;
            if (vis[vt.pos])
                continue;
            pt.pos = vt.pos;
            pit = to[vt.pos];

            int idx = vt.pos;
            printf("%c", ipt[vt.pos - 1]);
            REP(i, vt.val)
            {
                printf(" %d", idx);
                erase(idx, idx);
                idx = nxt[pre[idx]];
            }
            puts("");

            pl = pit->pre; pr = pit->nxt;
            if (pl->val == pr->val)
            {
                pl->len += pr->len;

                vis[pr->pos] = true;
                pr->erase();

                q.push(HeapNode(pl->len, pl->pos));
            }
            vis[vt.pos] = true;
            pit->erase();
        }
    }
    return 0;
}


联系
我们