hdu4737 A Bit Fun ——O(n)做法、错误的做法 + 正确做法

囧== 下面的做法是错误的。下午在路上突然明白了==

哎，到现在还是只知道暴力的做法，囧爆了：http://www.cnblogs.com/liuxueyang/p/3322197.html

类似于前序和的那种思想。

b数组代表前序或，c数组代表后序或。

O(N)预处理出数组b和数组c

在从前往后扫一遍O(N)的复杂度，求出ans

如图：

可以发现c[Head] & b[Tail] 就可以求出任意区间内的f(Head, Tail)，可以知道，整个数组里面每个元素进入区间一次，出去一次，所以是O(N)的复杂度。

就这么欢乐地解决了==

 #include <cstdio>
 #include <cstring>
 +;
 int a[N], b[N], c[N];
 int main(void)
 {
   #ifndef ONLINE_JUDGE
   freopen("in.txt", "r", stdin);
   #endif // ONLINE_JUDGE
     int t; scanf("%d", &t);
     ; i <= t; ++i)
     {
         printf("Case #%d: ", i);
         int j, n, m; scanf("%d%d", &n, &m);
         memset(b, , sizeof(b));
         memset(c, , sizeof(c));
         ;
         ; j <= n; ++j) {
             scanf("%d", a+j);
             b[j] = b[j-] | a[j];
         }
         ; --j) {
             c[j] = c[j+] | a[j];
         }
         , Tail = ;
         while (Head <= n && Tail <= n) {
           int tmp = c[Head] & b[Tail];
           while (tmp < m && Tail <= n) {
             ans++; tmp = c[Head] & b[++Tail];
           }
           ++Head; Tail = Head;
         }
         printf("%I64d\n", ans);
     }

     ;
 }

其实正确的做法应该是这样的：

 #include <cstdio>
 #include <cstring>
 typedef long long int LL;
 +;
 ], cnt[];
 int main(void) {
 #ifndef ONLINE_JUDGE
     freopen("in.txt", "r", stdin);
 #endif
     int t; scanf("%d", &t);
     memset(dig, , sizeof(dig));
     dig[] = ;
     ; i <= ; ++i) dig[i] = dig[i-] * ;
     ; i <= t; ++i) {
         printf("Case #%d: ", i);
         , Tail = , n, m, j, k;
         scanf("%d%d", &n, &m);
         LL sum = (LL)n * (n+) / , tmp, nosum = ;
         memset(cnt, , sizeof(cnt));
         ; j < n; scanf("%d", a+j++));
         while (Tail < n) {
             tmp = ;
             ; j <= ; ++j)
                 if (dig[j] & a[Tail])
                     ++cnt[j];
             ; j <= ; ++j)
                 if (cnt[j])
                     tmp += dig[j];
             if (tmp >= m) {
                 k = Head;
                 while (tmp >= m) {
                     tmp = ;
                     ; j <= ; ++j)
                         if (dig[j] & a[Head])
                             --cnt[j];
                     ; j <= ; ++j)
                         if (cnt[j])
                             tmp += dig[j];
                     ++Head;
                 }
                 nosum += (LL)(n - Tail) * (Head - k);
             }
             ++Tail;
         }
         printf("%I64d\n", sum - nosum);
     }
     ;
 }

一定要记得强制类型转换！！！18行的那种。纠结了一晚上==

嗨，中村。

hdu4737 A Bit Fun ——O(n)做法、错误的做法 + 正确做法的相关教程结束。