LINK：Perfect Triples
初看这道题 一脸懵逼..
完全没有思路 最多就只是发现一点小规律 即。
a<b<c. 且b的最大的二进制位一定严格大于a b的最大二进制位一定等于c.
但是这对解题没有任何用处。
考虑打个表看看有什么规律没有.
通过这道题 我承认 打表找规律也是一个技术活.
虽然能看出来到了第二排 a的数值是递增的 考虑特判前面几个我们就能快速找到a了.
但是b 和 c还是难找。那继续观察后面几项的规律。
我的败笔也是出自这里 规律一般也是符合较小的数据的 没道理不符合1~15这些数值。
我找了10min 失败 虽然勉强看出来4个为一组 但是还是难以找到b,c的规律。无法快速定位。
但是这不是考试 可以不用自闭了。
翻了一篇题解 那篇题解上给了一个比较猛的规律.
这个是一个以三个数字为节点的四叉树。
考虑把这个四叉树画出来 可以惊奇的发现 儿子和父亲有很大的联系。
仔细观察第一个节点(1,2,3) 和第一个儿子(4,8,12).
简单的得到 前者二进制位左移两位得到后者。
考虑第一个节点的第二个儿子 显然由第一个儿子加上(1,2,3)得到。第三个儿子由第一个儿子加上(2,3,1)得到。第四个儿子由第一个儿子加上(3,1,2)得到。
至此 我们直接从根节点一路下来定位即可 由于是四叉树 所以每次查询是log4(n)的复杂度。
这道题告诉我 规律要从小的地方开始找 且一般都符合较小的数字集。这样容易看出来。
实际上 输出也很难搞 我想了20min yy出来一个方法。
由父亲定位过于困难 定位父亲较为简单。
可以发现这是一个层数前缀和的形式 先定位层数。这个可以利用前缀和搞。
然后就可以定位到父亲的位置了 然后把自己的位置变成父亲的第几个儿子。
这样再从上往下做就很容易了。注意直接定位父亲的做法是错误的 因为这是一个前缀的形式很可能定位错误。
const ll MAXN=100010;
ll n,T,top;
ll s[MAXN],a,b,c;
ll p[MAXN],maxx,sum[MAXN];
int main()
{
freopen("1.in","r",stdin);
get(T);p[0]=1;maxx=27;sum[0]=1;
rep(1,maxx,i)p[i]=p[i-1]*4,sum[i]+=sum[i-1]+p[i];
//putl(sum[maxx]);
while(T--)
{
get(n);top=0;
ll ww=(n-1)/3+1;
ll cc=n%3==0?3:n%3;
ll w1=0;
while(sum[w1]<ww)++w1;
ww=ww-(w1==0?0:sum[w1-1]);
while(w1)
{
ll p1=(ww-1)/4+1;
s[++top]=ww-(p1-1)*4;
ww=p1;--w1;
}
a=1;b=2;c=3;
while(top)
{
a=a<<2;b=b<<2;c=c<<2;
if(s[top]==2)a+=1,b+=2,c+=3;
if(s[top]==3)a+=2,b+=3,c+=1;
if(s[top]==4)a+=3,b+=1,c+=2;
--top;
}
if(cc==1)putl(a);
if(cc==2)putl(b);
if(cc==3)putl(c);
}
return 0;
}