ZJNU 1900 Secret Cow Code 想法题 倒推

Secret Cow Code

Time Limit: 3000MS Memory Limit: 3000K
Total Submissions: 65 Accepted: 18
Description

The cows are experimenting with secret codes, and have devised a method for creating an infinite-length string to be used as part of one of their codes.

Given a string s, let F(s) be s followed by s “rotated” one character to the right (in a right rotation, the last character of s rotates around and becomes the new first character). Given an initial string s, the cows build their infinite-length code string by repeatedly applying F; each step therefore doubles the length of the current string.

Given the initial string and an index N, please help the cows compute the character at the Nth position within the infinite code string.

Input

The input consists of a single line containing a string followed by NN. The string consists of at most 30 uppercase characters, and N≤ 1018 .

Note that N may be too large to fit into a standard 32-bit integer, so you may want to use a 64-bit integer type (e.g., a “long long” in C/C++).

Output

Please output the Nth character of the infinite code built from the initial string. The first character is N=1.

Sample Input

COW 8
Sample Output

C
Hint

In this example, the initial string COW expands as follows:

COW -> COWWCO -> COWWCOOCOWWC

题目链接

题意：给你一个字符串，这个字符串每次都会增加，增加的方法为从最后一个开始正向读，读完整个字符串并且增加到原来字符串的后面，问你增加后的第n个字符是什么。

解题思路：对于一个在字符串s的x位置(x!=strlen(s)即不为最后一个)上的字符，增加一次后，他的位置将会变成x+strlen(s)+1，若为最后一个则为strlen(s)+1，因此我们可以进行倒推，根据正推公式我们可以得出，在n位置上的字符，上一个位置应该为n-strlen(st)-1，st为增加多次后比n小的最长的字符串，当然如果为0，即为那次中读的第一个，因此若为0，将其改为strlen(st)即可，最后当n小于等于strlen(s)的时候，我们即可得出答案。

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
const ll mm=1e18;
char s[35];
ll n,a[100],pl;
int main(){
    scanf("%s%lld",s,&n);
    ll l=strlen(s);
    a[1]=l;
    for(ll i=2;;i++){
        a[i]=a[i-1]*2;
        if(a[i]>n){
            pl=i;
            break;
        }
    }
    while(1){
        if(n<=l){
            break;
        }
        ll p=lower_bound(a,a+pl,n)-a-1;
        n=n-a[p]-1;
        if(n==0)    n=a[p];
    }
    printf("%c\n",s[n-1]);
    return 0;
}