洛谷【P1885】Moo

我对分治的理解：https://www.cnblogs.com/AKMer/p/9728574.html

题目传送门：https://www.luogu.org/problemnew/show/P1885

这题跟[[洛谷【P3612】USACO17JAN Secret Cow Code秘密奶牛码差不太多，都是分治字符串然后乱搞一波就行了。

时间复杂度：\(O(logn)\)

空间复杂度：\(O(1)\)

代码如下：

#include <cstdio>

using namespace std;

int n;

char s[4]={' ','m','o','o'};

int read() {

	int x=0,f=1;char ch=getchar();

	for(;ch<'0'||ch>'9';ch=getchar())if(ch=='-')f=-1;

	for(;ch>='0'&&ch<='9';ch=getchar())x=x*10+ch-'0';

	return x*f;

}

char find(int id) {

	if(id<4)return s[id];

	int tmp=3,pos=0;

	while(tmp<id)tmp=tmp*2+4+pos,pos++;

	int mid=tmp-pos-3;mid/=2;

	if(id<=mid)return find(mid);

	if(id<=mid+pos+3) {

		if(id!=mid+1)return 'o';

		else return 'm';

	}

	return find(id-(mid+pos+3));

}

int main() {

	n=read();

	printf("%c",find(n));

	return 0;

}

巴特西

洛谷【P1885】Moo

最新文章

热门文章