题目链接https://www.luogu.com.cn/problem/P1160
很裸的一道队列的题
方法一：没审清题目，
，直接就来写，笨笨得每次都扫描一遍链表导致TLE，最后得分40分
1 #include<bits/stdc++.h> 2 using namespace std; 3 int n, k, p, m, x; 4 struct lb{//链表的结点：当前数值、上一个位置、下一位置 5 int num; 6 int last; 7 int next; 8 }; 9 lb l[100010]; 10 int tail=1;//队尾计数 11 int head=0;//链表头 12 int chazhao(int k){//用于查询链表的下标 13 for(int i=head; i; i=l[i].next) 14 if(l[i].num==k)return i; 15 return 0; 16 } 17 void print(){//测试使用 18 for(int i=1; i<=tail; i++) 19 cout<<i<<":"<<l[i].num<<":"<<l[i].last<<":"<<l[i].next<<endl; 20 } 21 void shuchu(){//输出队列 22 for(int i=head; i; i=l[i].next) 23 cout<<l[i].num<<" "; 24 cout<<endl; 25 } 26 void charu(int i, int t, int p){ 27 l[++tail].num=i;//链表数组末端插入数据 28 if(p==0){//判断左插入 29 l[tail].next=t; 30 l[tail].last=l[t].last; 31 if(l[t].last==-1){ 32 head=tail; 33 } 34 else{ 35 l[l[t].last].next=tail; 36 } 37 l[t].last=tail; 38 } 39 if(p==1){//判断右插入 40 l[tail].next=l[t].next; 41 l[tail].last=t; 42 if(l[t].next!=0){ 43 l[l[t].next].last=tail; 44 } 45 l[t].next=tail; 46 } 47 //print(); 48 } 49 void del(int t){ 50 if(l[t].last==-1){ 51 head=l[t].next; 52 l[l[t].next].last=-1; 53 } 54 else{ 55 l[l[t].last].next=l[t].next; 56 if(l[t].next!=0){ 57 l[l[t].next].last=l[t].last; 58 } 59 } 60 } 61 int main() 62 { 63 64 cin>>n; 65 head=1; 66 l[tail].num=1; l[tail].next=0; l[tail].last=-1; 67 for(int i=2; i<=n; i++){ 68 cin>>k>>p; 69 int t=chazhao(k); 70 //cout<<t<<endl; 71 charu(i, t, p); 72 //shuchu(); 73 } 74 cin>>m; 75 while(m--){ 76 cin>>x; 77 int t=chazhao(x); 78 if(t) 79 del(t); 80 //shuchu(); 81 } 82 shuchu(); 83 return 0; 84 }
方法二：修改之后不再超时，但仍然只有40分，但很还是有细节修改了1天也搞不出来
1 #include<bits/stdc++.h> 2 using namespace std; 3 int n, k, p, m, x; 4 struct lb{//链表的结点：当前数值、上一个位置、下一位置 5 int last; 6 int next; 7 }; 8 lb l[100100]; 9 10 int head;//链表头 11 12 void print(){//测试使用 13 for(int i=1; i<=n; i++) 14 cout<<i<<":"<<l[i].last<<":"<<l[i].next<<endl; 15 } 16 void shuchu(){//输出队列 17 for(int i=head; i!=-2; i=l[i].next) 18 cout<<i<<" "; 19 cout<<endl; 20 } 21 void charu(int i, int t, int p){//在t的左0（右1）插入i 22 if(p==0){//判断左插入 23 l[i].next=t; 24 l[i].last=l[t].last; 25 if(l[t].last==-1){ 26 head=i; 27 } 28 else{ 29 l[l[t].last].next=i; 30 } 31 32 l[t].last=i; 33 } 34 if(p==1){//右插入 35 l[i].next=l[t].next; 36 l[i].last=t; 37 if(l[t].next!=-2){ 38 l[l[t].next].last=i; 39 } 40 l[t].next=i; 41 } 42 //print(); 43 } 44 void del(int t){ 45 if(l[t].last==-1){ 46 head=l[t].next; 47 if(l[t].next!=-2) 48 l[l[t].next].last=-1; 49 } 50 51 else{ 52 l[l[t].last].next=l[t].next; 53 if(l[t].next!=-2){ 54 l[l[t].next].last=l[t].last; 55 } 56 } 57 58 } 59 int main() 60 { 61 62 cin>>n; 63 head=1; 64 l[1].next=-2; l[1].last=-1; 65 for(int i=2; i<=n; i++){ 66 cin>>k>>p; 67 charu(i, k, p); 68 //shuchu(); 69 } 70 cin>>m; 71 while(m--){ 72 cin>>x; 73 del(x); 74 //shuchu(); 75 } 76 shuchu(); 77 return 0; 78 }
上述代码麻烦之处在于对链表头和尾的处理和讨论，所以还是认真的研究了一下别人的题解：