HDU 6121 Build a tree（k叉树的子树大小相异）

佚名 6年前 (2019-05-04) 随笔 961人围观抢沙发百度已收录

http://acm.hdu.edu.cn/showproblem.php?pid=6121

题目大意：

给你一颗 n 个节点的完全 k 叉树，问你这棵树中所有子树结点个数的总异或值。

分析：

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

我们很容易看到于发现对于这样的一颗树，肯定是只有一颗子树不是满k叉树，知道这样后，这就很简单了；

我们可以找到不满的树的编号P , 那左边就要（P-1）棵满树，右边有(n-P)棵少一层的满树，我们在分析，如果左边的树的数量是偶数，那我们可以不用计算，奇数只要计算一颗；右边同样的道理：

还有一个问题就是k==1的情况：需要找到规律

#include<bits/stdc++.h>
using namespace std; #define ll long long ll n,k; ///返回1~x层的满树有多少结点
ll sum(ll x) { if(x<=0) return 0; if(x==1) return 1; ll ans=1; for(ll i=1 ; i<x ; i++) { ans*=k;ans++; } return ans; } ///对于一颗深度为 x 层的满树，返回它的异或值
ll comf(ll x) { if(x<=0) return 0; if(x==1) return 1; ll ans=1; if(k%2==0) { return sum(x); } else { ll temp=1; for(ll i=1 ; i<=x ; i++) { temp*=k; temp++; ans=ans^temp; } } return ans; } ///对于一颗 k 叉树，返回他的异或值
ll F(ll n) { //printf("520");
    if(n==1) return 1; ll temp=n-1;///找到不满的树
 ll L,R; ll x=1;///层数
    while((temp-1)/k>0)///防止爆long long
 { temp=(temp-1)/k; x++; } x++; if(n==sum(x)) return comf(x); L=temp-1;///满k的树有多少棵
    R=k-temp;///缺一层满k的树有多少课
    ll ans=n; if(L%2==1) { ans=ans^comf(x-1); } if(R%2==1) { ans=ans^comf(x-2); } ///不满k树有多少课节点
    n=n-L*sum(x-1)-R*sum(x-2)-1; ans=ans^F(n); return ans; } int main() { int T;scanf("%d",&T); while(T--) { scanf("%lld%lld",&n,&k); if(k==1) printf("%lld\n",n%4==1?1:(n%4==2?n+1:(n%4==3?0:n))); else printf("%lld\n",F(n)); } }