UVA 12657/COJ 1329 HN第九届省赛链表模拟

因为最近学了Splay，刚看到这个题目总共四种操作，把某个数移到另一个数的左边或者右边交换两个数翻转整个序列，马上想到用Splay，因为总点数和总操作数都为10^5,如果用Splay把操作优化到logN级别，应该是可以再1sec过得。

于是我就好心急的在那里敲Splay，敲着敲着就发现不对劲了，题目要求的把x移到y的左边或者右边或者交换x和y的值，不是指序列的第x位和y位，而是就直接指数值为x和y的那两个数。所以Splay根本就不适用

所以还是回到链表来，其实用链表也挺简单的，一开始我还想复杂了，每个x和y就固定对应自己的节点x，y，进行4个操作的时候，前三个，只要把节点x和节点y连起来或者交换即可，当然要处理好彼此的前缀和后继。然后最后一个翻转整个序列操作，其实就是把每个点的前缀变后继后继变前缀即可。所以一开始不要固定前缀和后继，用个ch[2],再设置个p变量，初始设为0，这样 ch[p]代表前缀，ch[!p]代表后缀。当出现翻转操作，把p变一下，就直接实现了前变后后变前的作用。

还要注意添加 0点和 n+1点来预防越界操作，而且0点和n+1还可以作为整个序列的头部，因为对这两个点是不会有操作的，所以最后遍历链表的时候，看p的值选择0或者n+1点作为序列头部，至此，完美解决此题。

#include <iostream>

#include <cstdio>

#include <cstring>

#include <algorithm>

#define N 100010

using namespace std;

int n,m,p;

struct node

{

    int ch[];

} num[N];

void link(int a,int b)

{

    num[b].ch[p]=a;

    num[a].ch[!p]=b;

}

int main()

{

    int kase=,x,y,d;

    while (scanf("%d%d",&n,&m)!=EOF)

    {

        p=;

        for (int i=;i<=n;i++)

        {

            link(i,i+);

        }

        for (int i=;i<m;i++)

        {

            scanf("%d",&d);

            if (d==)

            {

                p^=;

                continue;

            }

            scanf("%d%d",&x,&y);

            if (d==)

            {

                if (num[y].ch[p]==x)

                    continue;

                else

                {

                    link(num[x].ch[p],num[x].ch[!p]);

                    int tmp=num[y].ch[p];

                    link(tmp,x);

                    link(x,y);

                }

            }

            if (d==)

            {

                if (num[y].ch[!p]==x)

                    continue;

                link(num[x].ch[p],num[x].ch[!p]);

                int tmp=num[y].ch[!p];

                link(y,x);

                link(x,tmp);

            }

            if (d==)

            {

                if (num[x].ch[p]==y)

                {

                    int tmp=num[x].ch[!p];

                    link(num[y].ch[p],x);

                    link(x,y);

                    link(y,tmp);

                    continue;

                }

                if (num[x].ch[!p]==y)

                {

                    int tmp=num[x].ch[p];

                    link(x,num[y].ch[!p]);

                    link(y,x);

                    link(tmp,y);

                    continue;

                }

                int tmp1=num[y].ch[p];

                int tmp2=num[y].ch[!p];

                link(num[x].ch[p],y);

                link(y,num[x].ch[!p]);

                link(tmp1,x);

                link(x,tmp2);

            }

        }

        int sta;

        if (p) sta=n+;

        else sta=;

        int cur=;

        p^=;

        long long ans=;//结果可能超过int，所以用64位来表示

        for (int i=sta;;)

        {

            i=num[i].ch[p];

            cur++;

            if (cur>n) break;

            if (cur&)

            {

                ans+=(long long)i;

            }

        }

        printf("Case %d: %lld\n",++kase,ans);

    }

    return ;

}

巴特西

UVA 12657/COJ 1329 HN第九届省赛链表模拟

最新文章

热门文章

巴特西

UVA 12657/COJ 1329 HN第九届省赛 链表模拟

最新文章

热门文章

UVA 12657/COJ 1329 HN第九届省赛链表模拟