ここに問題の私のコードがあります。コードは Code::blocks では問題なく実行されますが、spoj サイトと ideone.com では実行されません。実行時エラーが発生します。spoj サーバーが必要な量のメモリを割り当てることができないと思います。いくつかの提案をしてください。
http://paste.ubuntu.com/1277109/ (マイコード)
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 倍です。
2)前の時間ステップで組み合わせ01に対して連続するゼロのペアが生成されます。
3) パターンの後半は、前半のNOTになります。
次に興味深い部分です。各ステップで生成された連続するゼロ ペアの数を確認します。最初のステップの結果を代入する場合、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 を見てください....
それは、ヤコブスタール シーケンスを形成します。
これが私たちのソリューションです。
1) 入力された数値を調べて、最大値を見つけます。これには O(n) 時間がかかります。
2)最大までのヤコブスタール数のルックアップ テーブル (LUT) を作成します。現在のヤコブスタル数に対して前の 2 つのヤコブスタル数が必要なだけなので、これには O(n) 時間以上かかりません。それはヤコブスタール数の性質から明らかです。
3) 入力番号を再度トラバースし、今度は対応するシーケンス番号を LUT から出力します。テーブル ルックアップには O(1) 時間がかかり、n 個の数値の合計時間は O(n) になります。
4) 問題全体の時間計算量は O(n) です。
この方法の利点の 1 つは、大きな文字列を処理する必要がないことです。
于 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 に答える