hdu 6121---Build a tree(深搜+思维)

2018-06-17 22:01:49来源:未知 阅读 ()

新老客户大回馈,云服务器低至5折

题目链接

 

Problem Description
HazelFan wants to build a rooted tree. The tree has n nodes labeled 0 to n1, and the father of the node labeled i is the node labeled i1k. HazelFan wonders the size of every subtree, and you just need to tell him the XOR value of these answers.
 

 

Input
The first line contains a positive integer T(1T5), denoting the number of test cases.
For each test case:
A single line contains two positive integers n,k(1n,k1018).
 

 

Output
For each test case:
A single line contains a nonnegative integer, denoting the answer.
 

 

Sample Input
2
5 2
5 3
 
Sample Output
7
6
 
 
题意:有一颗树,节点编号0~n-1 ,节点 i 的父亲节点编号 ⌊i1k⌋ ,求所有子树大小相异或值?
 
思路:可以发现这是一棵完全 k 叉树 ,那么所有叶子节点高度差最多为1,且所有最高层叶子都靠左。那么我们从上向下找最高最靠右的叶子,然后回溯时计算:这时当前节点子树的大小特殊,其左边的所有同层次节点子树大小相同,其右边的所有同层次节点子树大小相同,所以对于每一层只需要考虑三种不同的节点子树。
 
         官方题解:
       
 
 

代码如下:(唉,比赛时代码没调出来,赛后才调完,有点可惜~)

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <cmath>
using namespace std;
typedef  long long LL;
const LL N=1e18+5;
LL cnt[70];
LL pw[70];
LL n,k,m;
int deep;
LL ans=0;
LL L,R,mid;

void dfs(int x)
{
    if(x>deep) return ;
    dfs(x+1);
    LL pos=(cnt[x]-1)%k; ///left brother;

    int f=(cnt[x]-1)&1;
    if(f) ans^=L;

    LL cR=pw[x]-cnt[x];
    f=cR&1;
    if(f) ans^=R;

    ans^=mid;

    mid=pos*L+mid+1+(k-pos-1)*R;
    L=L*k+1;
    R=R*k+1;
}

int main()
{
    int T; cin>>T;
    while(T--)
    {
       scanf("%lld%lld",&n,&k);
       if(k == 1){
            if(n%4 == 0) ans = n;
            else if(n%4 == 1) ans = 1;
            else if(n%4 == 2) ans = n+1;
            else if(n%4 == 3) ans = 0;
            printf("%lld\n",ans);
            continue;
       }
       LL tmp=1;
       m=n-1; pw[0]=1;
       for(int i=1;i<70;i++)
       {
           tmp=tmp*k; pw[i]=tmp;
           if(m<tmp || tmp<0 ) {  pw[i]=N; deep=i; break; }
           m-=tmp;
       }
       cnt[deep]=m;
       if(m==0) { deep--; cnt[deep]=pw[deep]; m=cnt[deep]; }
       for(int i=deep-1;i>=0;i--)
       {
           cnt[i]=(m+k-1)/k;
           m=cnt[i];
       }
       L=1; mid=1; R=0;
       ans=0;
       dfs(0);
       printf("%lld\n",ans);
    }
    return 0;
}

 

标签:

版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有

上一篇:P3389 【模板】高斯消元法

下一篇:C/C++ &amp;与&amp;&amp; |与|| 的区别