2

問題は：

  • 長さ n の文字列と m のクエリを指定します。

  • 各クエリは、次の 2 つのケースのいずれかです。

    • i 番目の文字を逆に変更する
    • u 番目の文字から v 番目の文字までの部分文字列が正しいかっこ式であるかどうかを確認します。はいの場合は 1 を出力し、そうでない場合は 0 を出力します。

制限時間：0.2秒

これらの場合、正しいブラケット式が定義されます。

  • 長さが 0 の文字列

  • '(' と ')' のみを含む文字列

  • A が正しいブラケット式の場合、(A) も正しいブラケット式です

  • A と B が正しい括弧式の場合、AB も正しい括弧式です

私の主なアイデアは、CodeForces の問題380Cに似ています。 http://codeforces.com/blog/entry/10363

次に、指定された範囲内の最長のサブシーケンスが範囲の長さと等しいかどうかを確認して、答えを取得します。しかし、時間制限エラーが発生しました。

私は一日中インターネットでこれを探していましたが、答えがありませんでした。あなたが私を助けてくれれば、私は感謝します。:)

これが私のコードです: https://github.com/hoangvanthien/GH_CppFiles/blob/master/SPOJ/NKBRACKE.cpp

4

1 に答える 1

1

有効なブラケット シーケンスの条件は次のとおりです。

  • 部分文字列の長さは偶数です。

  • 開き括弧と閉じ括弧の数は同じです。

  • シーケンスのどの時点でも、右括弧の数が左括弧の数より多い点はありません。

したがって、開き括弧と閉じ括弧の元の文字列から、それを一連の数値に変換できます。各数値は、シーケンスの先頭からの開き括弧と閉じ括弧の違いを表します。各開き括弧には、プラス 1 とマイナス 1 を閉じます。

たとえば、((()))))-> のシーケンスは { 1, 2 , 3, 2 , 1, 0, -1, -2 } です。

したがって、部分文字列 (2, 5) などの部分文字列が有効かどうかをテストするには()))、任意の時点で、open と close の差が負であるかどうかを確認する必要があります。上記のシーケンスから、{3, 2, 1, 0} があり、部分文字列にはない文字列の先頭からこれらのブラケットを削除する必要があるため、各要素に対して 2 を引く必要があります。-> {1, 0, -1, -2} がある -> したがって、部分文字列は無効です。

上記のアイデアを理解した後、問題の解決策を得ることができます。

  • 必要なのは、範囲をすばやく更新できるデータ構造です。たとえば、インデックス 3 で から(に変更した場合、インデックス 3 以降のすべての要素)をマイナスする必要があります。-2

  • また、範囲の最小値をすばやく返すデータ構造が必要です (最小値のみを気にする必要があります)。

そして、そのすべての要件から、O(log n) の更新と O(log n) の取得を提供するセグメント ツリーを使用できます。

疑似コード

SegmentTree tree;

Initialize the tree with original sequence

for each query in the tree
   if( query type is update)
      if(change from ) to ()
         increase all value by 2 from range index to n
      else if(change from ( to ) )
         decrease all value by 2 from range index to n
   else
      int min = tree.getMinimumValueInRange(u, v)
      int notInSubstring = tree.getMinimumValueInRange(u - 1, u - 1)
      if(min - notInSubstring < 0)
          print Invalid 
      else if( length of substring is not even)
          print Invalid
      else if( tree.getMinimumValueInRange(v, v) != notInSubstring)//Number of open and close brackets are not equaled.
          print Invalid
于 2015-12-16T05:29:27.143 に答える