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

似乎您已经使用数组实现了二进制数，而将它们简单地实现为数字并使用位掩码和位移位查询/修改它们会更快。这将消除您在get_c;中使用迭代方法的需要。您的get_c函数将是恒定时间而不是线性时间。

于 2012-05-25T23:58:47.823 回答