6

サイズが「10,000」にもなる文字列があります。9 で割り切れるサブシーケンスを数えなければなりません。

サブシーケンス: サブシーケンスは、指定された文字列の文字の順序が維持される配置です。例: 指定された文字列が 10292 の場合、そのサブシーケンスの一部は 1、102、10、19、12、12 (2 が 2 回来るので 12 は 2 回)、129、029、09、092 などです。指定された文字列のサブシーケンスは、201 (2 と 0 は 1 の前に来ることはできません)、921、0291 などです。

ビットシフトを使用して、指定された文字列のすべてのサブシーケンス (パワーセット) を生成しようとしました。各文字列が 9 で割り切れるかどうかを確認します。ただし、文字列の長さが 10 以下である限り、これは正常に機能します。その後、適切なサブシーケンスを取得できません (一部のサブシーケンスは負の数で表示されます)。

以下は私のコードです：

    scanf("%s", &str); //input string 

    int n=strlen(str); //find length of string

    //loop to generate subsequences
    for(i=1;i<(1<<n);++i){

        string subseq;

        for(j=0;j<n;++j){

            if(i&(1<<j)){

                subseq+=str[j]; // generate subsequence
            }
        }

        //convert generated subseq to int; number is 'long' tpye
        number=atol(subseq.c_str());printf("%ld\n", number); 

        //ignore 0 and check if number divisible by 9
        if(number!=0&&number%9==0)count++;
    }

        printf("%ld\n", count);
4

4 に答える 4

4

アイデアがありました！

部分文字列を数えるだけでよいので、それらが実際に何であるかは気にしません。したがって、代わりに、可能な合計のカウントを保存することができます。

次に、2つの部分文字列セットのカウントテーブルを組み合わせて、それらの組み合わせのカウントを提供できる関数がある場合はどうでしょうか。

そして、それは恐ろしい説明だったと知っているので、例を挙げましょう。番号が与えられたとしましょう：

2493

それを半分に分割し、個々の数字が得られるまで分割を続けます。

   2493
   /  \
 24    93
 /\    /\
2  4  9  3

何2に合計できますか？簡単： 2。そして4、合計することができるのは4。各値に合計される部分文字列の数のテーブルを作成できます（mod 9）。

   0 1 2 3 4 5 6 7 8
2: 0 0 1 0 0 0 0 0 0
4: 0 0 0 0 1 0 0 0 0
9: 1 0 0 0 0 0 0 0 0
3: 0 0 0 1 0 0 0 0 0

2つのテーブルを組み合わせるのは簡単です。最初のテーブル、2番目のテーブル、および2つのmod 9のすべての組み合わせを追加します（最初の組み合わせの場合、これは、、、および;と同等2です4。224番目の、、、、9および3）93：

    0 1 2 3 4 5 6 7 8
24: 0 0 1 0 1 0 1 0 0
93: 1 0 0 2 0 0 0 0 0

その後、もう一度やり直してください。

      0 1 2 3 4 5 6 7 8
2493: 3 0 2 2 2 2 2 2 0

そして、あなたの答えがあります、そこに0コラムに座っています： 3。これは、部分文字列、、、およびに対応243し2493ます9。しかし、あなたはそれを知りません。なぜなら、あなたはカウントだけを保存したからです-そして幸いなことに、あなたは気にしません！

実装すると、O(n)パフォーマンスが向上します。でテーブルを組み合わせる方法を正確に理解する必要がありますO(1)。でもねえ-宿題だよね？幸運を！

于 2012-08-03T18:19:26.287 に答える
4

数字の合計が 9 で割り切れる場合にのみ、数値が 9 で割り切れるため、O(n)再帰アルゴリズムを使用してこの問題を回避できます。

アイデアは次のとおりです。各ステップで、サブシーケンスを 2 つに分割し、数字の合計が であるシーケンスの数を (再帰的に) 決定します。i % 9ここで、i範囲は から0です8。次に、次の方法で 2 つのテーブルを「マージ」することにより、範囲全体に対してこのまったく同じテーブルを作成しO(1)ます。L左の分割と右の分割のテーブルがあり、範囲全体Rのテーブルを作成する必要があるとしましょう。F

次に、次のようになります。

for (i = 0; i < 9; i++) {
  F[i] = L[i] + R[i];
  for (j = 0; j < 9; j++) {
    if (j <= i)
      F[i] += L[j] * R[i - j]
    else
      F[i] += L[j] * R[9 + i - j]
  }
}

1 桁のみのサブシーケンスの基本ケースdは明らかです。設定するだけF[d % 9] = 1で、他のすべてのエントリを 0 にします。

完全な C++11 実装:

#include <iostream>
#include <array>
#include <tuple>
#include <string>

typedef std::array<unsigned int, 9> table;

using std::tuple;
using std::string;

table count(string::iterator beg, string::iterator end)
{
    table F;
    std::fill(F.begin(), F.end(), 0);
    if (beg == end)
        return F;
    if (beg + 1 == end) {
        F[(*beg - '0') % 9] = 1;
        return F;
    }
    size_t distance = std::distance(beg, end);
    string::iterator mid = beg + (distance / 2);
    table L = count(beg, mid);
    table R = count(mid, end);

    for (unsigned int i = 0; i < 9; i++) {
        F[i] = L[i] + R[i];
        for(unsigned int j = 0; j < 9; j++) {
            if (j <= i)
                F[i] += L[j] * R[i - j];
            else
                F[i] += L[j] * R[9 + i - j];
        }
    }
    return F;
}

table count(std::string s)
{
    return count(s.begin(), s.end());
}

int main(void)
{
    using std::cout;
    using std::endl;
    cout << count("1234")[0] << endl;
    cout << count("12349")[0] << endl;
    cout << count("9999")[0] << endl;
}
于 2012-08-03T18:00:33.287 に答える
0

Akappa のアルゴリズムに従った C++ コードを次に示します。ただし、このアルゴリズムは、1 つ以上の 0 を含む数値、つまり "10292" と "0189" の場合には失敗しますが、"1292" と "189" については正しい答えを返します。誰かがこれをデバッグして、すべてのケースに答えてくれれば幸いです。

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<string>
#include<cstring>
#include<vector>
#include<stack>
#include<sstream>
#include<algorithm>
#include<cctype>
#include<list>
#include<set>
#include<set>
#include<map>
using namespace std;
typedef vector<int> table;
table count(string::iterator beg, string::iterator end)
{

    table F(9);
    std::fill(F.begin(), F.end(), 0);
    if (beg == end)
        return F;

    if (beg + 1 == end) {
        F[(*beg - '0') % 9] = 1;
        return F;
    }

    size_t distance = std::distance(beg, end);
    string::iterator mid = beg + (distance / 2);
    table L = count(beg, mid);
    table R = count(mid, end);

    for (unsigned int i = 0; i < 9; i++) {
        F[i] = L[i] + R[i];
        for(unsigned int j = 0; j < 9; j++) {
            if (j <= i)
                F[i] += L[j] * R[i - j];
            else
                F[i] += L[j] * R[9 + i - j];
        }
    }
    return F;
}

table count(std::string s)
{

    return count(s.begin(), s.end());
}

int main()
{


     cout << count("1234")[0] << endl;

    cout << count("12349")[0] << endl;

    cout << count("9999")[0] << endl;

    cout << count("1292")[0] << endl;cout << count("189")[0] << endl;
    cout << count("10292")[0] << endl;cout << count("0189")[0] << endl;
    system("pause");


   }
于 2012-08-07T18:04:25.317 に答える
0

intを使用する場合は、左シフトしすぎないようにしてください。その場合、符号ビットを設定します。unsigned intを使用します。またはシフトをあまり左にしないでください。intを主張する場合は、完了したら右シフトできます。

のために

printf("%ld\n", count);

printf では、long-int 型の表示で問題が発生する可能性があります。cout を試しましたか？

于 2012-08-03T17:33:26.943 に答える