Secret Cow code(USACO)

题目描述：zxyer为了防止他的标程被别人抄走，他在计算机中的rar文件上设置了一个密码，其中每一个密码都有一个初始字符串，字符串由大写字母组成，且长度不超过30位，每一个密码还有一个询问，询问为一个整数n，表示询问当前第n位的字符为哪个字母。

字符串的加密过程如下：假设原字符串有n位，将原始字符串的第n位拿出，将该字母变成新的字符串的第一个字母，然后再将原始字符串的前n-1位放在新字符串的第2~n位，最后再将旧字符串与新字符串合并（即把新字符串放在旧字符串后面），加密过程可进行无限次。

很不巧的是，zxyer忘记了自己设置的密码，无奈的他只好请你来帮忙求出密码。

输入：一个不多于30位的由大写字母组成的字符串，表示密码的初始字符串，接下来是一个整数N，表示询问第N位的字母是什么。

输出：一个大写字母，表示第N位的字母。

样例输入：

COW 8

样例输出：

样例解释：

COW -> COWWCO -> COWWCOOCOWWC

————————————————我是分割线————————————————

很显然的DP题啊，自己找规律，发现只要每次找到长度*2^n（n为2^n*长度不超过N的最大整数）然后把N-（2^n+1）即可，如果N=0则+原始长度

#include<cstdio>

#include<cstring>

#define MN 30

using namespace std;

char ch[MN];

long long n;

long long i;

int num;

int main(){

    freopen("code.in","r",stdin);

    freopen("code.out","w",stdout);

    scanf("%s",ch);

    scanf("%lld",&n);

    num=strlen(ch);

    while(n>num){

        i=num;

        while(n>(i<<))i<<=;

        n-=(i+);

        if(n==)n=i;

    }

    printf("%c\n",ch[n-]);

    fclose(stdin);

    fclose(stdout);

}

巴特西

Secret Cow code(USACO)

最新文章

热门文章