自动搬运

查看原文

来自洛谷，原作者为

	bh1234666 这蒟蒻很烂，什么都没有留下

搬运于2025-08-24 22:39:30，当前版本为作者最后更新于2022-08-20 23:17:42，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

看到这题第一反应可能是贪心，二分时每次使区间最小，但是这样做是不正确的。因为直接贪心时靠前的操作权值$^*$小，靠后的操作权值大，靠前的决策会影响靠后的决策，即权值小的决策影响权值大的决策，显然不正确。

$^*$ 此处权值定义较复杂，可以简单理解为对后续长度产生影响（缩短 $1$）的概率。

例如对于 $n=13$，查询序列的第 $5$ 个（下标为 $4$，接下来的位置均指下标）。直接贪心过程为：

$$[0,12] \stackrel{w=1}{\longrightarrow} [0,5] \stackrel{w=0}{\longrightarrow} [3,5] \stackrel{w=1}{\longrightarrow} [4,5] \stackrel{w=0}{\longrightarrow} [4,4] $$

但实际上有更优解法：

$$[0,12] \stackrel{w=0}{\longrightarrow} [0,6]\stackrel{w=0}{\longrightarrow}[4,6] \stackrel{w=1}{\longrightarrow} [4,4] $$

第一步贪心看似比最优解短了 $1$ ,贪心的下一步使得查找的值出现在了中部，导致 $[3,5] \stackrel{w=1}{\longrightarrow} [4,5]$ 这一步无法使得长度折半。而贪心前面短的那一步最优解在下一步除二时除掉了，而在更靠后的 $[4,6] \stackrel{w=1}{\longrightarrow} [4,4]$ 比贪心短了 $1$。

对于 $\text{sub2}$ ，发现每次 $w$ 的值不会影响答案，直接输出 $\log_2 n$ 即可。

发现询问次数只有 $100$ 次，直接暴力。为便于实现，可以采用递归实现的二分，每次递归时分两类递归取最小即可。

由于递归层数为 $\log_2 n$ 层，每层分两种情况，最终复杂度为 $O(nq)$，可以通过此题。

核心代码：

int find(int k,int f,int l)
{
	if(f==l) return 0;
	int mid=(f+l)>>1,ret=32;
	if(mid<k) ret=find(k,mid+1,l);
	else ret=find(k,f,mid);
	mid=(f+l+1)>>1;
	if(mid<=k) ret=min(ret,find(k,mid,l));
	else ret=min(ret,find(k,f,mid-1));
	return ret+1;
}
int main()
{
	int i,n,q,k;
	scanf("%d",&n);
	for(i=0;i<n;i++)
		scanf("%d",num+i); 
	scanf("%d",&q);
	while(q--)
	{
		scanf("%d",&k);
		for(i=0;i<n;i++)
			if(num[i]==k) break;
		printf("%d\n",find(i,0,n-1));
	}
	return 0;
}

extra:

对于给定的 $n$，考虑查找第 $0\sim n-1$ 下标时所需要的次数。

显然次数只能为 $\lfloor \log n\rfloor\sim \lfloor \log n\rfloor +1$。

写出 $n$ 的二进制，设高位连续的 $1$ 的数量为 $t$，低位连续的 $0$ 的数量为 $k$。

当 $n$ 为偶数时 $w$ 不会影响二分下一步的情况，因此显然存在 $2^k$ 个循环节。

考虑每次操作对区间长度 $len$ 的影响，每次操作的实质是：

当 $len_i$ 为偶数时，$len_{i+1}=\lfloor \dfrac{len_i}{2}\rfloor$。

当 $len_i$ 为奇数时，若查找的数不在序列正中间，则可以选择 $len_{i+1}=\lfloor \dfrac{len_i}{2}\rfloor$ 或者 $\lfloor \dfrac{len_i}{2}\rfloor+1$，若查找的数在正中间则 $len_{i+1}=\lfloor \dfrac{len_i}{2}\rfloor+1$。

显然要被查找的数不会连续两次出现在正中间，因此必然可以通过某种操作使得所处位最高的 $0$(指 $len$ 在二进制下，下同) 不产生进位。也就是说单个循环节内的答案只与开头连续的 $1$ 有关，显然对于连续的 $1$，会间隔出现不进位和进位的情况。

注意，虽然最高位的 $0$ 可以使得处理到 $1$ 时长度一定，但是查询的数在序列中的相对位置会受到低位的影响，因此循环节不会被高位的 $0$ 消除掉。

即循环节内部对称且中间部分为 $\lfloor \log n\rfloor$，开头结尾受到 $t$ 的影响会出现 $\lfloor \log n\rfloor$ 与 $\lfloor \log n\rfloor+1$ 相间的情况，长度为 $2^t-2$。

预处理循环节长度，得到询问在某个循环节的位置，判断是否在受到 $t$ 影响的区间及奇偶性（在 $\lfloor \log n\rfloor$ 与 $\lfloor \log n\rfloor+1$ 相间区间时）即可得到答案。

以上说明纯属扯淡，这个结论是我输出了 n 为 90 到 128 的结果以后观察得出的。

时间复杂度 $O(q)$。

核心代码:

int get_ans(int x)
{
	if(n==1) return lgt;//lgt为[log n]
	else
	{
		x%=len;//len为循环节长度，即n/2^k
		if(x>len/2) x=len-x-1;
		if(x>(1<<n)-2) return lgt;//此处的n为t
		else if(x&1) return lgt+1;
		else return lgt;
	}
}

注意到会进行大量的取模运算，可以采用 barrett 约减优化取模，其原理是通过成本较低的乘法运算和位运算替换取模（整除）运算。

预处理 $brt=\lfloor 2^{r}/len\rfloor$，可以通过 $brt\times x /2^r$ 得到 $\lfloor x/len \rfloor$ 的近似值，当 $r$ 足够大时，得到的近似值与精确值至多差 $1$。

我们可以通过 $x-brt\times x /2^r$ 来得到 $x\bmod len$ 的近似值，若得到的值大于 $len$ 则减 $len$ 即可。

于是我们就通过两次减法一次乘法一次位运算（除二的幂次）和一次条件判断（上述运算的成本均远小于取模）替换掉了一次取模运算。

barrett 部分核心代码：

brt=((__uint128_t)1<<brtcnt)/len;//brt初始化

x=x-len*(unsigned long long)(brt*x>>brtcnt);
if(x>=len) x-=len;//等价于x%=len