概述
题目
原题链接:aaa好难啊
思路
显然对于一个位置p,我们有映射关系(由于字符串是形成递推关系的)
比如:
s=abcd,查找6
abcd dabc
d在后半串对应的前半串最后一个位置
a在后半串对应的前半串的第2位置
我们发现,6其实就是前半串的第1个位置,所以输出s[1]='a'。
我们通过不断缩小范围来确定初始时的位置,这属于分治算法。
代码
#include <bits/stdc++.h>
#define int long long
using namespace std;
string s;
int m,k,siz,p,mid;
signed main()
{
cin>>s>>m;
k = m;
siz = s.size();
p = siz;
while(p <= m) p *= 2;//是先找到第一个>m的2的次幂 p
while(p > siz)//当p<=siz时结束
{
mid = p / 2;
if(mid < k) k = k - mid - 1;
if(k == 0) k = mid;
p /= 2;
}
cout<<s[k - 1];
return 0;
}
最后
以上就是慈祥白昼为你收集整理的上海月赛乙组2023一月比赛:无限延展题目思路代码的全部内容,希望文章能够帮你解决上海月赛乙组2023一月比赛:无限延展题目思路代码所遇到的程序开发问题。
如果觉得靠谱客网站的内容还不错,欢迎将靠谱客网站推荐给程序员好友。
本图文内容来源于网友提供,作为学习参考使用,或来自网络收集整理,版权属于原作者所有。
发表评论 取消回复