互联网网站建设门户网,网站横条广告,企业所得税缴纳标准,公众号注册平台传送门
题意#xff1a;有一序列SSS由下列方式生成#xff1a;
找到字典序最小的正整数(a,b,c)(a,b,c)(a,b,c)#xff0c;满足a,b,ca,b,ca,b,c不在SSS中且a⊕b⊕c0a\oplus b\oplus c0a⊕b⊕c0,其中⊕\oplus⊕为异或将a,b,ca,b,ca,b,c加入SSS重复第一步 TTT组数据#xff…传送门
题意有一序列SSS由下列方式生成
找到字典序最小的正整数(a,b,c)(a,b,c)(a,b,c)满足a,b,ca,b,ca,b,c不在SSS中且a⊕b⊕c0a\oplus b\oplus c0a⊕b⊕c0,其中⊕\oplus⊕为异或将a,b,ca,b,ca,b,c加入SSS重复第一步
TTT组数据求SSS的第nnn项。
T≤105,n≤1016T\leq 10^5,n\leq10^{16}T≤105,n≤1016
通过观察样例和理性猜想可以假设前4k−14^k-14k−1项恰好填完了1∼4k−11\sim4^k-11∼4k−1显然这是整数个三元组。采用归纳法构造4k∼4k1−14^k\sim 4^{k1}-14k∼4k1−1
将每个序列中的数按二进制位两个为一组拆分以下称拆成的两个二进制位为位当前的数(已构造的和此步将构造的)有2(k1)2(k1)2(k1)位
之前填的4k−14^k-14k−1项可以看成最高位为00\texttt{00}00我们要构造的是最高位为01,10,11\texttt{01,10,11}01,10,11后面kkk位分别遍历0∼4k−10\sim 4^k-10∼4k−1
对于每一个(a,b,c)(a,b,c)(a,b,c)显然有abcabcabc
构造aaa最高位为01\texttt{01}01,容易得到b,cb,cb,c最高位为10,11\texttt{10,11}10,11。这是最理想的结果下面将证明这种构造是可行的。
现在已经满足了abcabcabc那么a,b,ca,b,ca,b,c的后kkk位是互不影响的。下面讨论的都是这后kkk位。
现在考虑如何最小化字典序
对于一个已经确定的aaa我们都需要找到最小的bbb(废话)
对于aaa上的每一位都找到一个最小的对应的bbb的位即可似乎还是废话但似乎就是想不到
设新构造的三元组为(ai,bi,ci)(0≤i≤2k−1)(a_i,b_i,c_i)(0\leq i\leq2^k-1)(ai,bi,ci)(0≤i≤2k−1)显然所有的aiia_iiaii
根据以上信息可以构造出(a,b,c)(a,b,c)(a,b,c)每一位字典序最小的对照表
盗用官方题解的图 随便推一下就可以了
复杂度O(Tlogn)O(T\log n)O(Tlogn)
