P3612 Secret Cow Code S题解报告

COLINHO · 2024-04-09 10:19:02 · 个人记录

1.题目描述

[USACO17JAN] Secret Cow Code S - 洛谷

2.考点分析

• 递推
• 递归

3.解题思路

• 朴素模拟 40分 其余因为字符串长度太长MLE

利用字符串，每次将当前字符串的最后一个和其余子串拼接成新串再拼接回当前字符串，如果新字符串的长度大于等于n即可。

• 递推 100分

从初始串长度倍增x，直到x>=n，保证此时的串长度包含n，然后利用串长度x和n逆推回去，计算每次x折半时n的位置，直到n小于等于原始串的长度即可输出答案，不需要特判。由题意可知，对任意一次的x和n，x/2是上一次的长度，如果n值刚好为x/2+1，则说明是由上一次的最后一个变换而来，则n=x/2，如果n>x/2+1，则是由上一次的其他位置后移一个变换而来，只需要逆操作：位置-1再取模求上一次位置即可，n=(n-1)%(x/2)

• 递归 100分

递归思路和以上递推思路一致，但实现的时候有很多细节和易错点，详见代码。

4.示例代码

• 递归

#include<bits/stdc++.h>
using namespace std;
string s;
unsigned long long n,x;
int main(){ 
    cin>>s>>n;
    x=s.size();
    while(x<n) x*=2;//倍增找最终长度 
    while(n>s.size()){//只要计算出的下标在字符串长度内即可 
        if(n==x/2+1) n=x/2;
        if(n>x/2+1) n=(n-1)%(x/2);
        x/=2;
    }
    cout<<s[n-1];//下标从0开始 
    return 0;
}

• 递归

  #include<bits/stdc++.h>
  using namespace std;
  string s;
  unsigned long long n,x;
  void dfs(unsigned long long x){//递归实现 
  if(x<n) dfs(x*2);
  if(n<=s.size()){//此处判断必须加在回溯阶段 且必须放在修改全局n的前面：思考执行顺序！ 
  //      cout<<s[n-1];//若放在递归内输出会导致输出多个值 
      return;
  }
  if(n==x/2+1) n=x/2;
  if(n>x/2+1) n=(n-1)%(x/2);
  } 
  int main(){
  //递归思路：参数x不断倍增直到大于n
  //1.回溯过程和递推思路一样计算，但注意判断当n<=s.size()时结束 
  cin>>s>>n;
  if(n>s.size()) dfs(s.size()); 
  cout<<s[n-1];
  return 0;
  }