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

Question

如何解决问题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;
}

//感谢和问候

Answer 1

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

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​​