题解：CF1926E Vlad and an Odd Ordering

• Codeforces
• Luogu

多么美丽的一道找规律啊！

ps：鄙人太烂了，所以只能写这种入门题的题解。

---

思路

这道题面非常诈骗，因为只有在奇数的 $2$ 的幂倍时才会有牌被铺开，简易证明如下（十分简单会的可以跳过）：

设 $k=2^n×(2m+1)$ ，因此 $x=k×(2y +1)$，其中 $n,m,y∈ \mathbb {N}$ 。

当且仅当 $m=0$ 时，$k=2^n$，否则 $k>2^n$ 且 $k$ 不为2的幂。

所以

$$x=k×(2y+1)$$ $$=2^n×[(2m+1)×(2y +1)]$$ $$=2^n×(2z+1)(z∈ \mathbb {N})$$

又因为当$m≠0$时，$k>2^n$，所以$x$一定已经被铺开过了，该次操作无效。

所以当且仅当在奇数的 $2$ 的幂倍时才会有牌被铺开。

我们不妨来模拟一下：

设共有7张牌：$[1,2,3,4,5,6,7]$

第一次铺开奇数（即 $2^0×$ 奇数）得到 $[1,3,5,7]$，剩下$[2,4,6]$ ；

第二次铺开 $2^1×$ 奇数 得到 $[2,6]$，剩下$[4]$ ；

第三次铺开 $2^2×$ 奇数 得到 $[4]$，没有剩下。

显而易见，第$n$次会铺开$2^{(n-1)}+2^n×m$，其中 $m∈ \mathbb {N}$，$m+1$表示铺开的是这轮操作里的第$m+1$张牌。

而每一次都会铺开剩余牌数的一半向上取整张牌。

因此就搓出了一个短小的解法。

代码

#include<bits/stdc++.h>

#define mian main() 

using namespace std;
 
int t;
long long n,k;
 
int mian
{
	cin>>t;
	while(t--)
	{
		cin>>n>>k;

		int cnt=0; //cnt 表示这是2的cnt次幂
		while(1)
		{
			long long a=(n+1)/2; //a 表示本次会铺开的牌数
			if(a>=k)
			{
				long long ans=(k-1)*(pow(2,cnt+1))+pow(2,cnt);
				cout<<ans<<"\n";
				break;
			}
			cnt++;
			n-=a;
			k-=a; 
		}
	}
 
	return 0;
}