题解 P3612 【[USACO17JAN]Secret Cow Code秘密奶牛码】

pluszero · 2017-06-14 21:17:50 · 题解

这道题其实很简单，通过观察我们可以发现，每一次增长增长的部分的第一位跟原部分的最后一位相同，增长部分的第二位到最后一位跟原部分的第一位到倒数第二位相同。 以样例为例：COW------->CO W W CO--------->COWWC O O COWWC。 可以发现第二次增长的第一位到第二位与第五位到第六位相同。第三次增长的第一位到第五位与第八位到第十二位相同。所以可以不断的把前面一半不用的删除掉，最后剩下原字符时输出即可。

下面是代码：

#include<iostream>
#include<algorithm>
#include<cmath>
#include<cstdio>
using namespace std;
char a[1000001];

int main()
{
    char ch;
    long long n,num=0;
    while(scanf("%c",&ch),ch!=' ')
        a[++num]=ch;
    scanf("%lld",&n);
    while(num<n)
    {
        long long i=num;
        while(n>i*2) i*=2;
        n-=(i+1);
        if(n==0) n=i;
    }
    printf("%c",a[n]);
    return 0;
}