uva12657 移动盒子 左右节点链表

 

 TLE--待我去消化佳爷代码,改了一下过了，90MS，好像没比佳爷慢很多的样子，时间差不多--

#include <cstdio>
int inv;
const int maxd = 100003;
int r[maxd],l[maxd];
//int a[maxd];
int n, m;
int cmd[3];
void link(int l_node, int r_node)
{
 r[l_node] = r_node;
 l[r_node] = l_node;
}
void fun()
{
 int x = cmd[1], y = cmd[2];
 switch (cmd[0])
 {
 case 4:
  if (inv == 0)inv = 1;
  else inv = 0;
  break;
 case 1://将x移动到y左边
  if ((r[x] == y && inv == 0) || (r[y] == x && inv == 1))break;
  if (inv == 0)
  {
   link(l[x], r[x]);
   link(l[y],x);
   link(x, y);
  }
  else {//inv==1的时候，1 x y和（inv == 0）2 x y操作相同，下面可以类推
   link(l[x], r[x]);
   link(x, r[y]);
   link(y, x);
  }
  break;
 case 2://将x移动到y右边
  if ((inv == 0 && r[y] == x) || (inv == 1 && l[y] == x))break;
  if (inv == 0)
  {
   link(l[x], r[x]);
   link(x, r[y]);
   link(y, x);
  }
  else {
   link(l[x], r[x]);
   link(l[y], x);
   link(x, y);
  }
  break;
 case 3://没有考虑x y相邻的特殊情况，却鬼使神差地包括了这种情况
 {

  int xleft = l[x];
  link(l[y], x);
  link(xleft, y);
  int xright = r[x];
  link(x, r[y]);
  link(y, xright);
  break;
 }
 default:
  break;
 }
}
int main(void)
{
 int kase = 0;
 while (scanf("%d%d", &n, &m)==2)//！！！！==2的重要性--
 {
  inv = 0;
  for (int i = 0;i < n;i++)
  {
   //a[i] = i;
   link(i, i + 1);
  }
  link(n, 0);
  //a[n] = n;
  while (m--)
  {
   scanf("%d", cmd);
   if(cmd[0]!=4)
    scanf("%d%d",  cmd + 1, cmd + 2);
   else cmd[1] = cmd[2] = 0;
   fun();
 //  for (int i = r[0];i != 0;i = r[i])
 //   printf("%d ", i);
 //  printf(" ");
  }
  long long sum1 = 0, sum2 = 0;
  for (int i = r[0];i != 0;i = r[i])
  {
   sum1 += i;
   sum2 += r[i];
   if (r[i] == 0)break;
   i = r[i];
  }
  printf("Case %d: ", ++kase);
  if (n % 2 == 1 || inv == 0)printf("%lld ", sum1);
  else printf("%lld ", sum2);
 }
 return 0;
}

#include <cstdio>
#include <algorithm>
using namespace std;
const int maxd = 100003;
int l[maxd], r[maxd];
/*void swap(int &x, int &y)
{
 int t = x;
 x = y;
 y = t;
}*/
void link(int l_node, int r_node)
{
 r[l_node] = r_node;
 l[r_node] = l_node;
}
int main(void)
{
 int n, m;
 int kase = 0;
 while (scanf("%d%d", &n, &m))//！！！！！！！！！！这里加上==2就可以AC
 {
  for (int i = 1;i <= n;i++)
  {
   l[i] = i - 1;
   r[i] = (i + 1) % (n + 1);
  }
  r[0] = 1, l[0] = n;
  int op, inv = 0, x, y;

  while (m--)
  {
   scanf("%d", &op);
   if (op == 4)inv = !inv;
   else {
    scanf("%d%d", &x, &y);
    if (op == 3 && r[y] == x)swap(x, y);
    if (op != 3 && inv)op = 3 - op;
    if (op == 1 && r[x] == y)continue;
    if (op == 2 && r[y] == x)continue;
    int xl = l[x], xr = r[x], yl = l[y], yr = r[y];
    if (op == 1)
    {
     link(xl, xr);
     link(yl, x);
     link(x, y);
    }
    else if (op == 2)
    {
     link(xl, xr);
     link(y, x);
     link(x, yr);
    }
    else if (op == 3 )
    {
     if (r[x] == y)
     {
      link(xl, y);
      link(y, x);
      link(x, yr);
     }
     else
     {
      link(xl, y);
      link(y, xr);
      link(yl, x);
      link(x, yr);
     }
    }
    
   }
  }
  int b = 0;
  long long ans = 0;
  for (int i = 1;i <= n;i++)
  {
   b = r[b];
   if (i % 2 == 1)ans += b;
  }
  if (n % 2 == 0 && inv)ans = (long long)n* (n + 1) / 2 - ans;
  printf("Case %d: %lld ", ++kase, ans);
 }
 return 0;
}