哥几个这题有解吗

小冰果

2026-08-27 11:20:24

发布于：北京

9阅读

0回复

0点赞

A1292.[COCI-2006_2007-contest3]#2 LISTA
就这个全几把是英文看不懂的说
感觉数据有问题每次都是那几个测试点wa了

#include<bits/stdc++.h>
using namespace std;

const int MAXN = 500010;

int pre[MAXN], nxt[MAXN];

void del(int x) {
    int L = pre[x], R = nxt[x];
    nxt[L] = R;
    pre[R] = L;
}


void ins_before(int x, int y) {
    del(x);
    int L = pre[y];
    nxt[L] = x;
    pre[x] = L;
    nxt[x] = y;
    pre[y] = x;
}


void ins_after(int x, int y) {
    del(x);
    int R = nxt[y];
    nxt[y] = x;
    pre[x] = y;
    nxt[x] = R;
    pre[R] = x;
}

struct Op {
    char typ;
    int x, y;
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N, M;
    cin >> N >> M;

    for (int i = 0; i <= N+1; ++i) {
        pre[i] = i-1;
        nxt[i] = i+1;
    }
    nxt[0] = 1;
    pre[N+1] = N;

    for (int i = 0; i < M; ++i) {
        char c;
        int X, Y;
        cin >> c >> X >> Y;
        if (c == 'A') {
            ins_before(X, Y);
        } else {
            ins_after(X, Y);
        }
    }

    int cur = nxt[0];
    int t = 0;
    while (cur <= N) {
        if (cur == t+1) {
            t++;
        }
        cur = nxt[cur];
    }

    vector<Op> ans;
    for (int i = t+1; i <= N; ++i) {
        ans.push_back({'B', i, i-1});
    }

    cout << ans.size() << '\n';
    for (auto &o : ans) {
        cout << o.typ << ' ' << o.x << ' ' << o.y << '\n';
    }

    return 0;
}

有帮助，赞一个

去预览

0/2000

这里空空如也

热门讨论