P4604 [WC2017] 挑战 题解

· · 题解

久仰久仰。

subtask 1

首先用快排显然会超时。

所以用基数排序。

然后基数排序的复杂度是 n \times \frac{\max{a_i}}{base}，base 是选择的基数的大小。

那你肯定觉得 base 越大排序越快对不对？

一般情况下确实是这样的。

但是你也不想想这是啥题目？

你选的基数如果大于 2^{8}，哦那你确实有一点点的常数优化，但是你没利用好 Cache 的缓存。

然后 2^{8} 的基数是在能卡进 Cache 的一级缓存的基础上尽量大的，所以选择 2^{8} 作为基数。

然后不用其他的任何优化就可以 AC 这个 subtask 了，可见 Cache 的优化多么巨大。

排序部分代码：

unsigned cnt[256];
#define sortarr(a , b , n , byte){\
    memset(cnt , 0 , sizeof(cnt));\
    for(int i = n - 1;i >= 0;i--){\
        cnt[(a[i] >> byte) & 255]++;\
    }\
    for(int i = 1;i < 256;i++) cnt[i] += cnt[i - 1];\
    for(int i = n - 1;i >= 0;i--){\
        b[--cnt[(a[i] >> byte) & 255]] = a[i];\
    }\
}

subtask 2

首先不考虑数据结构维护，对于某些数据你不管是啥数据结构应该都是维护不了的。

然后暴力非常容易写出：

#define solve(n , q , l , r , x , y , len , anss){\
    int check[3][3] = {{0 , 1 , 0} , {0 , 0 , 1} , {1 , 0 , 0}};\
    int i;\
    for(i = 0;i < n;i++){\
        l[i] ^= 48;\
        r[i] ^= 48;\
    }\
    for(i = 0;i < q;i++){\
        int ans = 0 , j;\
        for(j = 0;j < len[i];j++){\
            ans += check[l[x[i] + j]][r[y[i] + j]];\
        }\
        anss[i] = ans;\
    }\
}

虽然这东西也能过

然后我们用最无脑的卡常方法——循环展开来卡常。

可能有些同学并不知道循环展开是啥，这里说一下。

一个最简单的例子：

输入一个数 n，输出 1 到 n 的数之和。

最朴(la)素(ji)的写法：

inline int getsum(int n){
  int sum = 0;
  for(int i = 1;i <= n;i++){
      sum += i;
  }
  return sum;
}

循环展开后的写法：

inline int getsum(int n){
  int sum = 0 , sum1 = 0 , sum2 = 0 , sum3 = 0 , sum4 = 0 , sum5 = 0 , sum6 = 0 , sum7 = 0 , i;
  for(i = 1;i + 8 <= n;i += 8){
    sum += i;
    sum1 += i + 1;
    sum2 += i + 2;
    sum3 += i + 3;
    sum4 += i + 4;
    sum5 += i + 5;
    sum6 += i + 6;
    sum7 += i + 7;
  }
  for(;i <= n;i++){
    sum += i;
  }
  return sum + sum1 + sum2 + sum3 + sum4 + sum5 + sum6 + sum7;
}

错误的循环展开：

inline int getsum(int n){
  int sum = 0 , i;
  for(i = 1;i + 8 <= n;i += 8){
    sum += i;
    sum += i + 1;
    sum += i + 2;
    sum += i + 3;
    sum += i + 4;
    sum += i + 5;
    sum += i + 6;
    sum += i + 7;
  }
  for(;i <= n;i++){
    sum += i;
  }
  return sum;
}

但是这个也有优化作用。

那接下来，我们引出一个问题：

为什么循环展开能减小常数？

因为大多数时候 CPU 是有多个核心的，而我们评测的时候基本上只用了一个。多浪费啊！所以我们用循环展开来让 CPU 进行 CPU 并发，减小常数。

所以我们使用了循环展开后，这一部分的时间就会变的很少。

此部分代码：

#define solve(n , q , l , r , x , y , len , anss){\
    int check[3][3] = {{0 , 1 , 0} , {0 , 0 , 1} , {1 , 0 , 0}};\
    int i;\
    for(i = 0;i + 8 < n;i += 8){\
        l[i] ^= 48;\
        r[i] ^= 48;\
        l[i + 1] ^= 48;\
        r[i + 1] ^= 48;\
        l[i + 2] ^= 48;\
        r[i + 2] ^= 48;\
        l[i + 3] ^= 48;\
        r[i + 3] ^= 48;\
        l[i + 4] ^= 48;\
        r[i + 4] ^= 48;\
        l[i + 5] ^= 48;\
        r[i + 5] ^= 48;\
        l[i + 6] ^= 48;\
        r[i + 6] ^= 48;\
        l[i + 7] ^= 48;\
        r[i + 7] ^= 48;\
    }\
    for(;i < n;i++){\
        l[i] ^= 48;\
        r[i] ^= 48;\
    }\
    for(int i = 0;i < q;i++){\
        int ans = 0 , ans1 = 0 , ans2 = 0 , ans3 = 0 , ans4 = 0 , ans5 = 0 , ans6 = 0 , ans7 = 0 , j;\
        for(j = 0;j + 8 < len[i];j += 8){\
            ans += check[l[x[i] + j]][r[y[i] + j]];\
            ans1 += check[l[x[i] + j + 1]][r[y[i] + j + 1]];\
            ans2 += check[l[x[i] + j + 2]][r[y[i] + j + 2]];\
            ans3 += check[l[x[i] + j + 3]][r[y[i] + j + 3]];\
            ans4 += check[l[x[i] + j + 4]][r[y[i] + j + 4]];\
            ans5 += check[l[x[i] + j + 5]][r[y[i] + j + 5]];\
            ans6 += check[l[x[i] + j + 6]][r[y[i] + j + 6]];\
            ans7 += check[l[x[i] + j + 7]][r[y[i] + j + 7]];\
        }\
        for(;j < len[i];j++){\
            ans += check[l[x[i] + j]][r[y[i] + j]];\
        }\
        anss[i] = ans + ans1 + ans2 + ans3 + ans4 + ans5 + ans6 + ans7;\
    }\
}

subtask 3

显然是一个 dp。

具体实现的时候就是扫一遍，每遇到一个 ? 就把他左边的方案数和右边的方案数加起来。

但是显然过不了。

发现可达到的数的下标的奇偶性是和外层循环的奇偶性是一样的，因为一对匹配的左右括号占了两个位置。

再加个指针优化寻址就能过。

代码：

u32 ans[600000];
int solvee(int n , char *s){
    u32 *dp = ans + 270000;
    dp[0] = 1;
    for(int i = n - 1;i >= 0;i--){
        if(s[i] == '('){
            ++dp;
        }
        else if(s[i] == ')'){
            --dp;
        }
        else{
            int up = min(n - i , i) , lst = 0;
            for(int j = i % 2;j <= up;j += 2){
                dp[j] = dp[j - 1] + dp[j + 1];
            }
        }
        dp[-1] = 0;
    }
    return dp[0];
}

最后把代码结合起来，就可以 AC 了。