P3612 [USACO17JAN]Secret Cow Code S——分治

[洛谷 P3612 USACO17JAN]Secret Cow Code S

思路：分治

设原串长度为 (len)，要查询的位置为 (pos)，考虑如何一步步分治令 (pos) 变为小于等于 (len) 的数 (pos′)，且 (s_{pos}=s_{pos′})。

先定义一个 (n) 记录何时字符串的长度大于 (pos)，然后根据题意，很容易得出如果某个字符 (pos) 在长度为 (n) 的字符串的后半段，那么第

(pos−1−n/2) 一定与第 (pos) 个字符相同。

但是当 (n/2+1=pos) 时，(pos) 的值应该等于 (pos−1)，即 (n/2)，所以这种情况要特判，由此写出以下代码

 while (n != len) {
    n = n / 2;
    if (pos <= n) continue;
    n + 1 == pos ? pos = n : pos -= 1 + n;
  }

总代码

#include<bits/stdc++.h>
using namespace std;
const int N=200000;
int ch[N];
int n,pos;
int main()
{
	scanf("%s",ch+1);
	cin>>pos;
	int len=strlen(ch+1);
	n=len;
	while(n<pos)
	{
		n*=2;
	}
	while(n!=len)
	{
		n/=2;
		if(pos<=n)continue;
		pos==n+1?pos=n:pos=pos-1-n;	
	}
	cout<<ch[pos]<<endl;
	return 0;	
}