题解 UVA12657 【移动盒子 Boxes in a Line】

· · 题解

首先如果用数组来保存盒子，肯定会超时。

解决办法是采用链表，把每个盒子编号存起来。

可是普通的链表无法满足此题的要求。

解决方法是采用双向链表：用 l_i 和 r_i 分别表示编号为 i 的盒子左边和右边的盒子编号（如果是0，表示不存在）。

下面的过程可以让两个结点相互连接：

void link(int L,int R)
{
    r[L]=R;
    l[R]=L;
}

这样就可以先记录好操作之前 X 和 Y 两边的结点，然后用link函数按照某种顺序把它们连起来。

由于操作四如果直接进行操作，就会不可避免地 TLE .

可以增加一个标记 flag 表示有没有执行过操作4（如果flag=1 时再执行一次操作4，则 flag 变为0）。这样，当 o (o为操作) 为1和2且 flag=1 时，只需把 o 变成 3-o （注意操作3不受 flag 影响）即可。最终输出时要根据 flag 的值进行不同处理。

示例代码：

#include <bits/stdc++.h>
using namespace std;
int n,m;
int l[100005],r[100005];
void link(int L,int R)  //连接
{
    r[L]=R;
    l[R]=L;
}
int main()
{
    int Case=0;
    while(cin>>n>>m)
    {
        for(int i=1;i<=n;i++)   //初始化链表 
        {
            l[i]=i-1;
            r[i]=(i+1)%(n+1);   //注意此处处理
        }
        r[0]=1;
        l[0]=n; //首尾连接
        int o,x,y,flag=0;
        while(m--)
        {
            cin>>o; //输入运算符
            if(o==4)    //操作四，对 flag操作
            {
                flag=!flag;
            }
            else
            {
                cin>>x>>y;
                if(o==3&&r[y]==x)   //此处是为了方便后面统一处理
                {
                    swap(x,y);
                }
                if(o!=3&&flag)  //更改操作
                {
                    o=3-o;
                }
                if(o==1&&x==l[y])   //已经是了
                {
                    continue;
                }
                if(o==2&&x==r[y])   //同上
                {
                    continue;
                }
                int lx=l[x],rx=r[x],ly=l[y],ry=r[y];    //定义一些后面所需的变量
                if(o==1)    //这些连接具体操作可以试着在纸上画一画清晰思路    
                {
                    link(lx,rx);    
                    link(ly,x); 
                    link(x,y);
                }
                else if(o==2)
                {
                    link(lx,rx); 
                    link(y,x); 
                    link(x,ry);
                }
                else if(o==3)
                {
                    if(r[x]==y)     //统一处理相邻
                    { 
                        link(lx,y); 
                        link(y,x); 
                        link(x,ry); 
                    } 
                    else 
                    { 
                        link(lx,y); 
                        link(y,rx); 
                        link(ly,x); 
                        link(x,ry); 
                    }
                }
            }
        }
        int t=0;
        long long ans=0;
        for(int i=1;i<=n;i++)
        {
            t=r[t];
            if(i%2==1)  //这里统计奇数位置编号和
            {
                ans+=t;
            }
            // cout<<ans<<endl;
        }
        if(flag&&n%2==0)    //如果被反转了并且 n 是偶数（具体为什么也可在纸上试着画画）
        {
            ans=(long long)(1+n)*n/2-ans;   //答案应为另一部分（注意前面为等差数列求和公式）
        }
        // cout<<ans<<endl;
        cout<<"Case "<<++Case<<": "<<ans<<endl;
    }
    return 0;
}