1

あるサイトのインタビュー通りにある練習用の質問があって、かなりの時間を費やしてしまいました...

次のコードは、8/11 テストケースのみをクロスします。それ以外は制限時間を超えています。いくつかの最適化を提案していただければ幸いです

質問は次のとおりです.....

there are two binary numbers of length n             
there are three kinds of operation     
set_a idx x : it sets A[idx] = x   
set_b idx x : sets B[idx] = x   
get_c idx : Print C[idx], where C=A+B, and 0<=idx

Sample Input
5 5
00000
11111
set_a 0 1
get_c 5
get_c 1
set_b 2 0
get_c 5

Sample Output
100

したがって、get_c 操作を最適化する必要があります

void reverse(char*a, int len)
{
     //this function reverses the string
}

void get_c(int i)
{
     k = i-1;
     f = 0;
     while (k>=0)
     {
           if (a[k] == '1' && b[k] == '1')
           {
              f = 1;
              break;
           }
           else if (a[k] == '0' && b[k] == '0')
                break;
           --k;
     }
     if (f==0)
        cout<<(a[i] == b[i]?0:1);
     else if (f==1)
          cout<<(a[i] == b[i]?1:0);
}

int main()
{
    scanf("%d %d", &n, &q); // n = number of bits in number, q = number of operations
    // enter the strings a and b
    reverse(a, n);
    reverse(b, n);
    while (q--)
    {
          scanf("%s", query);
          scanf("%d", &idx);
          if (query is get_c)
          {
             get_c(idx);
          }
          else if (query is set_a)
          {
               cin>>x;
               a[idx] = x;
          }
          else if (query is set_b)
          {
               cin>>x;
               b[idx] = x;
          }
    }
    return 0;
}
4

1 に答える 1

0

2進数を単純に数値として実装し、ビットマスクとビットシフトを使用してクエリ/変更する方が速い場合は、配列を使用して2進数を実装したようです。get_cこれにより、 ;で反復アプローチを使用する必要がなくなります。get_c関数は線形時間ではなく定数時間になります。

于 2012-05-25T23:58:47.823 に答える