UVA12657题解

Grisses · 2022-01-08 08:25:41 · 题解

题面

一道链表的简单题。

我们设 nxt_i 表示链表中编号为 i 的元素的下一个元素的编号，per_i 表示链表中编号为 i 的元素的上一个元素的编号。

• 对于所有 1 操作，我们可以先删去 x 节点，在将其插入 y 的左边。

• 对于所有 2 操作，我们可以将其转化为将 x 插入 nxt_y 的左边。

• 对于所有 3 操作，我们可以先定义 l=nxt_x，然后将 x 插入 y 的左边，y 插入 l 的左边。

• 对于所有 4 操作，我们将其存储下来，有奇数次时将 1 操作作为 2 操作，2 操作作为 1 操作，3 操作不变。

代码

  #include<bits/stdc++.h>
  #define int long long
  #define swap(x,y) x^=y^=x^=y
  using namespace std;
  int l,r,x,cnt,n,m,ans,f,nxt[100005],per[100005];
  void Ereser(int x){//删除
      per[nxt[x]]=per[x];
      nxt[per[x]]=nxt[x];
  }
  void Insert(int l,int r){
      if(nxt[l]==r)return;
      if(l==r)return;
      Ereser(l);//插入
      nxt[per[r]]=l;
      per[l]=per[r];
      per[r]=l;
      nxt[l]=r;
  }
  void Swap(int l,int r){
      int k=nxt[l];//反转
      Insert(l,nxt[r]);
      Insert(r,k);
  }
  signed main()
  {
      while(scanf("%lld%lld",&n,&m)!=EOF){
          cnt++;ans=0;
          for(int i=1;i<=n;i++)nxt[i]=i+1,per[i]=i-1;
          nxt[0]=1,per[n+1]=n;
          f=1;
          for(int i=1;i<=m;i++){
              scanf("%lld",&x);
              if(x==1){
                  scanf("%lld%lld",&l,&r);
                  if(f)Insert(l,r);
                  else Insert(l,nxt[r]);
              }
              else if(x==2){
                  scanf("%lld%lld",&l,&r);
                  if(f)Insert(l,nxt[r]);
                  else Insert(l,r);
              }
              else if(x==3){
                  scanf("%lld%lld",&l,&r);
                  Swap(l,r);
              }
              else f^=1;//同题解
          }
          if(!f){
              swap(per[n+1],nxt[0]);
              for(int i=1;i<=n;i++)swap(per[i],nxt[i]);
          }
          f=1;
          for(int i=nxt[0];i!=n+1&&i!=0;i=nxt[i]){
              ans+=f*i;
              f^=1;
          }
          printf("Case %lld: %lld\n",cnt,ans);
      }
      return 0;
  }