题解 P3612 【[USACO17JAN]Secret Cow Code S】

issue_is_fw · 2020-03-09 16:02:57 · 题解

前言:在这道题目卡了很久，所以我想把自己的理解说出来，希望能帮到你们。管理大大让我过吧，(●ˇ∀ˇ●)自认为表达地比一些题解要好。

先看样例

我们把这三个字符串编号为1,2,3

现在我们要求第8位，假如我们已经知道在3串，能否逆推出在第2串中的位置呢?如果能，似乎问题就迎刃而解了,因为2逆推到1也是一个相同的子问题。

题目的古怪要求复制要先复制最后一个字符，再复制前缀，我们姑且先直接复制前缀.

现在求3串的8位置，3串长L,逆推回2串即为8-L/2位置

但我们复制的时候是先复制最后一个字符,所以要多减一为8-1-L/2

特别的,如果求的n刚好是先复制原串的那个位置,特殊处理，具体看代码

#include <bits/stdc++.h>
using namespace std;
string s;
long long n,num,i;
int main()
{
    //代码部分借鉴1楼 
    cin>>s>>n;
    num=s.length(); 
    while(num<n)
    {
        i=num;
        while(n>i)  i*=2;//求出当前刚好包括n位置的串长 
        i=i/2;//得到当前串的一半长 
    //  if(n==i+1)  n=i;特殊处理，假如这里n位置是i+1
    //那么经过下面这步操作后，变成了0，那我们下面对0特判 
        n-=(i+1); 
        if(n==0)    n=i;
    }
    cout<<s[n-1];
}