-7

マジックボードがあります。マジック ボードには N*N セル (N 行 N 列) があります。すべてのセルには 1 つの整数が含まれており、最初は 0 です。行と列に 1 から N までの番号を付けます。

マジック ボードに適用できる操作には、次の 2 種類があります。

•RowSet ix: この操作の後、行 i のセル内のすべての整数が x に変更されたことを意味します。

•ColSet ix: この操作の後、列 i のセルのすべての整数が x に変更されたことを意味します。

そして、あなたの友人は、行または列の整数 0 の総数に興味を持っていることがあります。

•RowQuery i: 行 i の 0 の総数を答えなければならないことを意味します。

•ColQuery i: 列 i の 0 の総数を答えなければならないことを意味します。

入力

入力の最初の行には、スペースで区切られた 2 つの整数 N と Q が含まれます。これらは、マジック ボードのサイズと、フレンドからの操作とクエリの合計数を示します。

次に、次の Q 行のそれぞれに、上記の形式による操作またはクエリが含まれます。

出力

クエリごとに、クエリの回答を出力します。

制約

1 ≤ N、Q ≤ 500000 (5 * 105)

1≦i≦N

x ∈ {0, 1} (つまり、x = 0 または 1)

サンプル入力:

3 6

行クエリ 1

コルセット 1 1

行クエリ 1

コルクエリ 1

行セット 1 0

コルクエリ 1

出力: 3

2

0

1

それについてどうやって行くのですか?時間の制約は 0.6 秒であるため、2D 配列で操作をマークする単純なアルゴリズムは機能しません。

4

1 に答える 1

3

良いアルゴリズムが思いつかない場合は、次の手法を試してください。

  1. 鉛筆と方眼紙を使用して例を実行します。
  2. もう一度例を実行します。今回は、実行する各詳細ステップを書き留めます。
  3. 手順を使用して、例をもう一度実行します。必要に応じて調整してください。
  4. ステップをコードに変換します。

この手法を使用すると、「メモリ/マトリックスの正方形の領域を実装するにはどうすればよいですか?」など、Stackoverflowで検索するためのより適切な質問を思い付くことができます。

または「デバッガを使用するにはどうすればよいですか?」

または「これが私の問題を再現する最小のプログラムです....、私は何を間違っているのですか?」

編集1:(私のSOの評判を高めるために)

要件から、少なくとも2つの関数が必要であるように見えます。行を指定された値に設定するか、列を指定された値に設定します。

4x4マトリックスのような小さなものから始めましょう。そして、次のコマンドを使用します。Set Row 10//行1をすべてゼロに設定します。C ++は、要件のように1からNではなく0からN-1にインデックスを付けるため、行番号から1を引く必要があることに注意してください。board[row][column]ボード上のセルを表すために、表記を使用してみましょう。手で:

  board[0][0] = 0;
  board[0][1] = 0; // Note the incrementing column numbers.
  board[0][2] = 0;
  board[0][3] = 0; // Note the last column index is 3 not 4.

上記のコードを見ると、パターン、つまり列インデックスが毎回1ずつ変化していることがわかります。したがって、これをループに入れることができます。

  Set column to zero.
  While column is less than 4 do:
      board[0][column] = 0;
      column = column + 1;
      end-while

次のステップは、これをいくつかのコードに変換することです。

  unsigned int column;
  unsigned int board[4][4];
  for (column = 0; column < 4; ++column)
  {
       board[0][column] = 0;
  }

このSet Rowコマンドでは可変行インデックスと可変行値が許可されているため、これらの変数を作成してコードに挿入します。

unsigned int row = 0;
unsigned int value = 0;
unsigned int column;
unsigned int board[4][4];
for (column = 1; column < 4; ++column)
{
    board[row][column] = value;
}

関数のシグネチャを提供することで、これを独立した関数にすることができます。

void Set_Row(unsigned int& array[4][4],
             unsigned int  row,
             unsigned int  value)
{
   // Insert above code fragment here.
}

次に、他のコマンドの関数を作成します。コマンドを読み取る関数を
作成します。 プログラムを実行し、実行時に任意のサイズの行列を宣言できるなど、問題がどこにあるかを確認します。 問題を解決するためのコードを追加します。 繰り返す。main


于 2013-02-07T00:06:51.383 に答える