Codeforces 792D

题意：给定一棵拥有n个节点的满二叉树（即n==2^x-1），q个查询，每次给出一个节点的编号，再给出一个由L，R，U组成的字符串序列，依次表示向左子节点、右子节点、父节点移动，如果移动不合法，则忽略。问字符串序列结束后所在节点的编号。具体编号可看：http://codeforces.com/problemset/problem/792/D

解题思路：

　　随意的画了一下树的编号，发现了一定的规律，如最左边的一定是2的幂，同高度的节点与之构成一个等差序列等，但这仍不足以帮助我们解决问题，最主要的比如判断当前节点是其父节点的左子节点还是右子节点、判断当前节点的高度等，然后不小心看到了题目的标签bitmask，画了一下各编号的二进制形式，规律就一目了然了：

　　最底层数字，其二进制形式，从右数起的第一个非零位的位置必为最右；倒数第二层，倒数第二右；以此类推——于是高度判断解决。

　　每一个节点，如果它为其父节点的左子节点，那么第一个非零位置左边的位置必为0，否则必为1。

　　从父节点到子节点，首先是非零位置向右移一位，同时根据是左还是右来决定原非零位置为0或是为1。

　　看起来很莫名但其实与最开始发现的那个“规律”是一一对应的，比如同一层的节点中，之前已发现其为等差序列，且差为2^高度，因此该二进制位必然是1和0交替出现；左子节点和右子节点的差别，则是因为最开始（2的幂）是0，而后是1，再是0，再是1……

　　找到规律之后，代码就很简单了，几行位运算而已。

　　这题主要启发了我这种树的编号、等差、二进制形式间可能存在的关系。

　　代码如下：

#include<iostream>

#include<cstdio>

#include<algorithm>

#include<cstring>

using namespace std;

typedef long long ll;

#define sqr(x) ((x)*(x))

const int N=1e5+,mod=1e9+;

ll n,u;

int q,mx;

char s[N];

int main(){

    //freopen("in.txt","r",stdin);

    while(~scanf("%I64d%d",&n,&q)){

        mx=;

        while(1LL<<mx!=n+) mx++;

        while(q--){

            scanf("%I64d%s",&u,s);

            int len=strlen(s);

            int pos=;

            while(!(u&(1LL<<pos))) pos++;

            for(int i=;i<len;i++){

                if(s[i]=='L'){

                    if(!pos) continue;

                    u^=(1LL<<pos);

                    pos--;

                    u^=(1LL<<pos);

                }else if(s[i]=='R'){

                    if(!pos) continue;

                    pos--;

                    u^=(1LL<<pos);

                }else{

                    if(pos+==mx) continue;

                    u^=(1LL<<pos);

                    pos++;

                    if(!(u&(1LL<<pos)))

                        u^=(1LL<<pos);

                }

            }

            printf("%I64d\n",u);

        }

    }

    return ;

}

巴特西

Codeforces 792D

最新文章

热门文章