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>
const int N = 100000+4;
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);
    for (int i = 1; i <= t; ++i)
    {
        printf("Case #%d: ", i);
        int j, n, m; scanf("%d%d", &n, &m);
        memset(b, 0, sizeof(b));
        memset(c, 0, sizeof(c));
        long long ans = 0;
        for (j = 1; j <= n; ++j) {
            scanf("%d", a+j);
            b[j] = b[j-1] | a[j];
        }
        for (j = n; j >= 1; --j) {
            c[j] = c[j+1] | a[j];
        }
        int Head = 1, Tail = 1;
        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);
    }

    return 0;
}

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

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

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

嗨，中村。