HDU 6121 Build a tree

本文由 Ocrosoft 于 2017-08-16 16:43:37 发表

Build a tree

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 524288/524288 K (Java/Others)
Total Submission(s): 796    Accepted Submission(s): 292

Problem Description
HazelFan wants to build a rooted tree. The tree has n nodes labeled 0 to n−1, and the father of the node labeled i is the node labeled ⌊i−1k⌋. 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(1≤T≤5), denoting the number of test cases.
For each test case:
A single line contains two positive integers n,k(1≤n,k≤1018).
 

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
 

Solution
2017 Multi-University Training Contest – Team 7
详见注释

#define C11
#include <set>
#include <map>
#include <stack>
#include <string>
#include <cstdio>
#include <queue>
#include <vector>
#include <cmath>
#include <climits>
#include <cstring>
#include <cctype>
#include <iostream>
#include <algorithm>
#include <functional>
#ifdef C11
#include <tuple>
#include <regex>
#include <random>
#include <complex>
#endif
using namespace std;
/** const var def */
const double eps = 1e-8;
const int maxn = 1e7 + 10;
const int MAXN = maxn * 4;
const int MOD = 1000000007;
const double PI = 4 * atan(1.0);
/** type def */
typedef long long LL;
typedef pair<int, int> Pii;
typedef pair<LL, LL> Pll;
typedef vector<int> Vi;
typedef pair<double, double> Vec2;
#ifdef C11
using Vec3 = tuple<double, double, double>;
using Tp3 = tuple<int, int, int>;
#endif
/** easy def */
#define _link(x) x&&x
#define ms(a) memset(a,0,sizeof(a))
#define msr(a) memset(a,-1,sizeof(a))
/* first, second, position */
#define _f first
#define _s second
#define _p(_tp,_pos) get<_pos>(_tp)
/* operator */
Pii operator +(const Pii &x, const Pii &y) { return Pii(x.first + y.first, x.second + y.second); }
Pii operator -(const Pii &x) { return Pii(-x.first, -x.second); }
Pii operator -(const Pii &x, const Pii &y) { return x + (-y); }
Pii operator +=(Pii &x, const Pii &y) { return x = x + y; }
Pii operator -=(Pii &x, const Pii &y) { return x = x - y; }
#pragma region input&output
template<class T>inline T read(T &num)
{
	char CH; bool F = false;
	for (CH = getchar(); CH<'0' || CH>'9'; F = CH == '-', CH = getchar());
	for (num = 0; CH >= '0'&&CH <= '9'; num = num * 10 + CH - '0', CH = getchar());
	F && (num = -num);
	return num;
}
template<class T>inline T read()
{
	T num;
	return read(num);
}
#ifdef C11
template<class T, class... Args>inline int read(T &t, Args &...args)
{
	read(t);
	read(args...);
	return t;
}
#endif
template<class T> inline void print(T p, char ed = '\n')
{
	int stk[70], tp = 0;
	if (p < 0) { putchar('-'); p = -p; }
	if (!p) { putchar('0'); if (ed != '\0')putchar(ed); return; }
	while (p) stk[++tp] = p % 10, p /= 10;
	while (tp) putchar(stk[tp--] + '0');
	if (ed != '\0')putchar(ed);
}
#ifdef C11
template<class T, class... Args>inline void print(T t, Args ...args)
{
	print(t, '\0');
	if (sizeof...(args))putchar(' ');
	else putchar('\n');
	print(args...);
}
#endif
#pragma endregion

int main()
{
	int N; read(N);
	while (N--)
	{
		LL n, k;
		read(n, k);
		if (k == 1) // k==1 时特判
		{
			print(vector<LL>{ n, 1, n + 1, 0 }[n % 4]);
			continue;
		}
		vector<LL> nodeCnt(2, 1);
		LL ans = n, cnt;
		LL depth = 1, pos = (n - 1 - 1) / k;
		for (LL t = 1; *(end(nodeCnt) - 1) < n; nodeCnt.push_back((t *= k) + *(end(nodeCnt) - 1)), depth++); // 到某层时的节点数量和
		if (n - nodeCnt[--depth] & 1)ans ^= 1;
		for (LL cur = 2; depth > 1; depth--, cur++, pos = (pos - 1) / k)
		{
			LL left = nodeCnt[depth - 1], right = nodeCnt[depth] - 1; // 当前(depth)层左侧节点标号,右侧节点标号(从0开始)
			LL fullCur = nodeCnt[cur], fullCurU = nodeCnt[cur - 1]; // 当前层左侧节点子树是满k叉树时子树大小,右侧子树是满k叉树时子树大小
			if (pos - left & 1)ans ^= fullCur; // 左侧满k叉树节点数量是奇数
			if (right - pos & 1)ans ^= fullCurU; // 右侧满k叉树节点数量是奇数
			for (cnt = pos; cnt <= (n - 2) / k; cnt = cnt*k + 1); // 非满k叉树的子树大小
			ans ^= fullCurU + n - cnt;
		}
		print(ans);
	}
	return 0;
}

 

欢迎转载,请保留出处与链接。Ocrosoft » HDU 6121 Build a tree

点赞 (1)or拍砖 (0)

评论 抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址