一行盒子 （湖南省第九届大学生程序设计大赛原题）

#include<stdio.h>#include<string.h>#include<stdlib.h>#include<map> using namespace std; int n,m;long long ans; struct node  //链表节点{    int x;    struct node *first;  //前驱指针    struct node *next;  //后继指针}*head,*are,*p,*q; map<int,node*> addre; void initial()  //创建一个长度为n+2，赋值为1-n的带头结点和尾节点的双向链表{    head=(node *)malloc(sizeof(node));    are=head;    head->first=NULL;    head->next=NULL;    p=head;    for(int i=1;i<=n;i++)    {        q=(node *)malloc(sizeof(node));        p->next=q;        q->first=p;        q->next=NULL;        q->x=i;        addre[i]=q;        p=q;        are=q;    }    q=(node *)malloc(sizeof(node));    p->next=q;    q->first=p;    q->next=NULL;    are=q;} void gotozero()//  清空链表，释放所有节点，以免超内存{    p=are;    while(p!=head)    {        q=p;        p=p->first;        free(q);    }    free(p);    addre.clear();} node* find(int x)  //在链表中查找值为x的节点，返回该节点的指针{    p=head->next;    while(p->x!=x)p=p->next;    return p;}void delet(node* u)  //删除指针u指向的节点{    u->first->next=u->next;    u->next->first=u->first;    free(u);} void insert(node* u,int x)//在指针u指向的节点前面插入一个值为x的节点{    q=(node *)malloc(sizeof(node));    q->x=x;    addre[x]=q;    q->first=u->first;    q->next=u;    u->first->next=q;    u->first=q;} void cul1() //逆向处理{    int num=1;    p=are->first;    while(p!=head)    {        if(num%2==1)ans+=p->x;        p=p->first;        num++;    }} void cul2()//正向处理{    int num=1;    p=head->next;    while(p!=are)    {        if(num%2==1)ans+=p->x;        p=p->next;        num++;    }} void output()  //将链表按中节点的值按顺序输出{    p=head->next;    while(p->next!=NULL)printf("%d ",p->x),p=p->next;    printf("\n");} int main(){    int u,x,y;    int i,j;int r=1;    while(scanf("%d%d",&n,&m)!=EOF)    {        int flag=0;        ans=0;        initial();         while(m--)        {            scanf("%d",&u);            if(u==4)flag++;             else            {                scanf("%d%d",&x,&y);                if(u==1)                {                    delet(addre[x]);                    if(flag%2==0)insert(addre[y],x);                    else insert(addre[y]->next,x);                }                 else if(u==2)                {                    delet(addre[x]);                    if(flag%2==0)insert(addre[y]->next,x);                    else insert(addre[y],x);                }                 else                {                    q=addre[x];                    p=addre[y];                    q->x=y;                    p->x=x;                    addre[x]=p;                    addre[y]=q;                }             }            //output();        }         flag%2?cul1():cul2();         printf("Case %d: %lld\n",r++,ans);         gotozero();     }    return 0;} /**************************************************************    Problem: 1329    User: 20114045007    Language: C++    Result: Accepted    Time:660 ms    Memory:5652 kb****************************************************************/