lists

发表于

链表

我们初始化链表的时候，要根据题目意思处理开头的第一个元素，这很重要！并且，我们把所有的指针都清成-1，这样保证了链表初始绝对合法。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
//初始化
void init()
{
    for(int i=1;i<=n;i++)
        a[i].pre=a[i].nxt=-1;
    a[1].nxt=-1;
    a[1].pre=0;
    a[0].nxt=1;
}
//插入操作
void insert_left(int pos,int k)//把元素k插入到pos元素之前
{
    a[a[pos].pre].nxt=k;
    a[k].pre=a[pos].pre;
    a[pos].pre=k;
    a[k].nxt=pos;
}
void insert_right(int pos,int k)//把元素k插入到pos元素之后
{
    a[a[pos].nxt].pre=k;
    a[k].nxt=a[pos].nxt;
    a[pos].nxt=k;
    a[k].pre=pos;
}
//删除操作
void remove(int x)
{
    if(a[x].pre==-1)
        return;
    a[a[x].pre].nxt=a[x].nxt;
    a[a[x].nxt].pre=a[x].pre;
    a[x].pre=-1;
    a[x].nxt=-1;
}
//遍历
void print()
{
    int start=a[0].nxt;
    while(1)
    {
        printf("%d ",start);
        if(a[start].nxt==-1)
            break;
        start=a[start].nxt;
    }
}

p1160 模板

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
#include<bits/stdc++.h>
#define ll long long
#define yes cout<<"Yes"<<endl
#define no cout<<"No"<<endl
using namespace std;
#define debug(a) cout<<#a<<"="<<a<<endl;
#define rep(i, a, b) for(ll i = (a); i <= (b); i++)
#define per(i, a, b) for(ll i = (a); i >= (b); i--)
const int N=1e5+10;
int n;
struct node
{
    int nxt,pre;
}a[N];

void init(){
    rep(i,1,n){
        a[i].pre=a[i].nxt=-1;
    }
    a[1].nxt=-1;
    a[1].pre=0;
    a[0].nxt=1;
}
void insert_l(int pos,int k){//k insert pos left
    a[a[pos].pre].nxt=k;
    a[k].pre=a[pos].pre;
    a[pos].pre=k;
    a[k].nxt=pos;
}
void insert_r(int pos,int k){//k insert pos right
    a[a[pos].nxt].pre=k;
    a[k].nxt=a[pos].nxt;
    a[pos].nxt=k;
    a[k].pre=pos;
}
void remove(int x){
    if(a[x].pre==-1) return;
    a[a[x].pre].nxt=a[x].nxt;
    a[a[x].nxt].pre=a[x].pre;
    a[x].pre=-1;
    a[x].nxt=-1;
}
void print(){
    int start=a[0].nxt;
    while(1){
        cout<<start<<" ";
        if(a[start].nxt==-1) break;
        start=a[start].nxt;
    }
}
void solve()
{   
    cin>>n;init();
    rep(i,2,n){
        int k,p;cin>>k>>p;
        if(p==0) insert_l(k,i);
        else insert_r(k,i);
    }
    int m;cin>>m;
    rep(i,1,m){
        int x;cin>>x;
        remove(x);
    }
    print();
}
int main() {
    ios::sync_with_stdio(false), std::cin.tie(0), std::cout.tie(0);
    // freopen("test.in", "r", stdin);
    // freopen("test.out", "w", stdout);
    int _ = 1;
    //std::cin >> _;
    while (_--)
    {
        solve();
    }
    return 0;
}