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