gpt4 book ai didi

algorithm - 动态规划,第 n 个字符串

转载 作者:塔克拉玛干 更新时间:2023-11-03 04:53:29 25 4
gpt4 key购买 nike

如何解决问题https://www.hackerearth.com/problem/algorithm/special-numbers-39d71325/ .

数字序列中的第一个数字是 1。序列中每个后续的第 i 个数字都是通过对第 (i-1) 个数字应用以下操作来构造的:

  • 用 114 代替 1
  • 用 1 代替 4

因此,顺序如下:

1, 114, 1141141, 11411411141141114, ...

编写一个程序,找出这个数列中第 i 个数字的第 j 个数字。如果第 i 个数字少于 j 个数字,则打印 -1。

输入格式

  • 第一行:T(测试用例数)
  • 每个测试用例的第一行:两个空格分隔的整数 i 和 j

输出格式

对于每个测试用例,打印一个数字,它是该序列中第 i 个数字的第 j 个数字。如果第 i 个数字少于 j 个数字,则打印 -1。

约束

1<=T<=10000(10的4次方)

1<=i<=1000000(10的6次方)

1<=j<=1000000000000(10的12次方)


Sample input                            Sample output
4
2 2 1
2 3 4
3 6 4
3 7 1

解释

第一个测试用例:序列中的第二个数字是 114,第二个数字是 1。

第二个测试用例:序列中的第二个数字是 114,第三个数字是 4。

第三个测试用例:序列中的第 3 个数字是 1141141,第 6 个数字是 4。

第 4 个测试用例:序列中的第 3 个数字是 1141141,第 7 个(最后)数字是 1。


将所有字符串(最多第 i 个字符串)存储在 vector 中将花费大量时间。问题的标签是记忆化(动态规划)。我想要使​​用记忆化(动态规划)的代码/策略。


我不认为我的以下方法更接近实际/正确的解决方案。


请参阅 vector<string> v(15); 行后的注释


如果这是提出此类问题的错误平台,请告诉我在哪里提出此类问题。

#include<iostream>
#include<string>
#include<vector>
#include<cstring>
#include<climits>
//#define tr(v,it) for(typeof(v.begin()) it=v.begin();it!=v.end();it++)
using namespace std;

int main() {
vector<string> v(15);//v(14) runs under 1 sec even v(15) gives tle. So think how much time v(1000000) will take.
v[0]="1";
vector<string>::iterator it;
int n,h,i,j,tc;
string s,s1;


char ch='a';
for(it=v.begin()+1;it!=v.end();it++) {//set value
s=*(it-1); s1="";
for(unsigned int i=0;i<s.length();i++) {
char ch=s[i];
if(ch=='1') {
s1=s1+"114";
}
else {
s1=s1+'1';
}
}
*it=s1;
}
/*for(it=v.begin();it!=v.end();it++) {//print value
cout<<*it<<endl;
}
cin>>tc;
while(tc--) {
cin>>i>>j;
cout<<v[i-1][j-1];

}*/
return 0;
}

//感谢和问候

最佳答案

让我们看一下序列和它的长度;

114
3
114 114 1
7
114 114 1 114 114 1 114
7 7 3
773 773 7
773 773 7 773 773 7 773
...

每个长度都是前一个序列与之前序列连接的两倍,也就是:

length(i) =
2 * length(i - 1) + length(i - 2)

给定最终字符串中的一个位置,因为我们知道前面的序列长度,我们可以确定它在 (1) 前一倍的第一个,(2) 前一倍的第二个,或 (3)附加,倒数第二个序列。

通过跟踪它的位置,我们不断将它的位置转换为先前序列之一中的位置,直到我们到达第一个序列。

例如:

    7         7      3
114 114 1 114 114 1 114
^

我们知道前两个序列的长度是 7 和 3,所以我们可以确定我们在第二个 7 长度序列的第 7 个索引上。现在我们继续:

114 114 1
^

前两个序列长度分别为 3 和 1,因此我们位于倒数第二个序列(长度为 1 的序列)的第一个索引处。

结果:1​​

关于algorithm - 动态规划,第 n 个字符串,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/52936068/

25 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com