2

这是我的问题代码。代码在我的 Code::blocks 上运行良好，但在 spoj 网站和 ideone.com 上运行良好。我收到运行时错误。我猜 spoj 服务器无法分配所需的内存量。请给一些建议。

http://paste.ubuntu.com/1277109/（我的代码）

4

3 回答 3

5

您的代码声明一个空字符串s，然后分配给它的元素......

...
string s,res;int c=0;
int sum,carry=0;
for(int i=m-1;i>=0;i--)
{
    sum=(a[i]-'0')*2+carry;
    s[c]=sum%10+'0';         // This is undefined behavior, s is empty
    carry=sum/10;
    c++;
}
...
于 2012-10-13T13:39:32.013 回答
1

这是您的问题的可能答案，而不是您的问题。

我猜这个问题具有算法风格，其目的是找到时间复杂度最小的解决方案（也许是线性时间解决方案）。对与最佳时间复杂度相关的问题进行一些预先准备是有帮助的。

所以我计算了几个时间步产生的模式（如下所示）：

step                                             pattern                         no. consecutive zero pairs

  1                                                01                                           0

  2                                               1001                                          1

  3                                             01101001                                        1

  4                                         1001011001101001                                    3

  5                                 01101001100101101001011001101001                            5

  6                 1001011001101001011010011001011001101001100101101001011001101001           11

  7                 0110100110010110100101100110100110010110011010010110100110010110           21
                    1001011001101001011010011001011001101001100101101001011001101001

  8                 1001011001101001011010011001011001101001100101101001011001101001           43
                    0110100110010110100101100110100110010110011010010110100110010110    
                    0110100110010110100101100110100110010110011010010110100110010110
                    1001011001101001011010011001011001101001100101101001011001101001

  9                 0110100110010110100101100110100110010110011010010110100110010110           85
                    1001011001101001011010011001011001101001100101101001011001101001
                    1001011001101001011010011001011001101001100101101001011001101001
                    0110100110010110100101100110100110010110011010010110100110010110
                    1001011001101001011010011001011001101001100101101001011001101001
                    0110100110010110100101100110100110010110011010010110100110010110
                    0110100110010110100101100110100110010110011010010110100110010110
                    1001011001101001011010011001011001101001100101101001011001101001

产生上述模式的代码如下：

#include<iostream>
using namespace std;
main()
{
string s,t=""; 
s="paste pattern produced in a time-step here";
int i,l,n=0;
l=s.length();
cout <<"s.length - "<<l<<endl;
    for(i=0;i<l;i++)
    {
        if(s[i]=='0')
          {t+="10";}
        else
          {t+="01";}
    }
l*=2;
        for(i=0;i<l-1;i++)
        {
            if(t[i]=='0' && t[i+1]=='0')
            {
            n+=1;
            }
        }
cout <<"t - "<<t<<endl;
cout <<"no. of consecutive zero pairs - "<<n<<endl;
}

下面列出了一些重要的观察结果：

1）每个时间步的字符数是上一步的两倍。

2）在前一个时间步中为组合01产生一对连续的零。

3）任何模式的后半部分将是其前半部分的非。

现在是有趣的部分。查看每个步骤产生的连续零对的数量。如果我们分配第一步的结果，假设 n 为零：

对于第 2 步，我们的结果为 n*2 + 1，其中 n 为 0。

对于第 3 步，我们的结果为 n*2 - 1，其中 n 为 1。

第 4 步的结果为 n*2 + 1，其中 n 为 1。

对于第 5 步，我们的结果为 n*2 - 1，其中 n 为 3。

或者通常我们的结果等于 n*2 - 1（对于奇数时间步），结果等于 n*2 + 1（对于偶数时间步）

这不会解决我们的问题，因为 n 是一个变量，我们需要找到一个数学公式，它将初始结果（对于时间步长 1）和任何时间步长的结果（例如 t）联系起来。

但我们有一个简单的出路。

看看数字 0,1,1,3,5,11,21,43,85....

它形成Jacobsthal 序列。

这是我们的解决方案。

1）遍历输入的数字并找出最大值。这需要 O(n) 时间。

2）创建一个雅各布斯塔尔数的查找表（LUT），直到最大值。这花费的时间不会超过 O(n)，因为您只需要前两个 Jacobsthal 数来获取当前 Jacobsthal 数。从 Jacobsthal 数的性质可以看出这一点。

3）这次再次遍历输入的数字，从LUT中输出对应的序列号。查表需要 O(1) 时间，n 个数字的总时间为 O(n)。

4)整个问题的时间复杂度为O(n)。

这种方法的一个优点是我们不必处理大字符串。

于 2012-10-13T23:55:39.610 回答
0

这只是@6502 答案的延伸。

看起来ostringstream很适合你想要的东西。

ostringstream oss;
string s,res;
int c=0;
int sum,carry=0;

for(int i=m-1;i>=0;i--)
{
    sum=(a[i]-'0')*2+carry;
    oss << (sum%10) << '0'; //Were you trying to concatenate a '0' as well?
    carry=sum/10;
}

s = oss.str();
于 2012-10-13T15:17:51.033 回答