HDU多校第九场 1003 Rikka with Mista —— 折半搜索 + 基数排序 + 双指针_综合

题目链接：点我啊╭(╯^╰)╮

题目大意：

$n$ 个数，选取任意的数的和，一共有 $2^n$ 种方案
求所有方案的数的十进制下 $'4'$ 的个数和

解题思路：

     $n = 40$ ，则可以折半搜索，预处理前后 $20$ 位的所有组合
    要统计每种方案的十进制下 $'4'$ 的和，发现可以通过枚举每一位的贡献
    计算每一位的贡献，只需要考虑这位及其以后的位，所组成的方案
    并且只需要考虑 $a + b = 4***$ 和 $a + b = 14***$ ， $a$ 和 $b$ 分别来自两组
    因为计算每一位的贡献，要忽略前面的数，所以每次都需要排序
    时间复杂度： $O(10 * 2 ^ {20} * 20)$

    考虑优化，因为这里只需要对这一位及以后排序，刚好符合基数排序的性质
    对每位进行基数排序，时间为 $O(n)$
    排序后用对每个 $a$ ， $b$ 只会减小，则可以用双指针扫描
    总时间复杂度： $O(10 * 2 ^ {20})$

核心：折半搜索 + 基数排序 + 双指针

#include<bits/stdc++.h>
#define rint register int
#define deb(x) cerr<<#x<<" = "<<(x)<<'\n';
using namespace std;
typedef long long ll;
const int maxn = 2e6 + 5;
int T, n, n1, n2, w[maxn];
ll a[maxn], b[maxn], pw[15];
ll aa[maxn], bb[maxn];
vector <int> cnt[15];void init() {scanf("%d", &n);memset(a, 0, sizeof(a));memset(b, 0, sizeof(b));for(int i=0; i<n; i++) scanf("%d", w+i);int m = n / 2;n1 = 1 << m, n2 = 1 << (n - m);for(int i=0; i<n1; i++)for(int j=0; j<20; j++)if(i & (1ll << j)) a[i] += w[j];for(int i=0; i<n2; i++)for(int j=0; j<20; j++)if(i & (1ll << j)) b[i] += w[j + m];
}void ksort(int k) {for(int i=0; i<=10; i++) cnt[i].clear();for(int i=1; i<=n1; i++) cnt[(a[i]%pw[k])/pw[k-1]].push_back(a[i]);for(int i=0, num=0; i<=10; i++) for(auto j : cnt[i]) a[++num] = j;for(int i=0; i<=10; i++) cnt[i].clear();for(int i=1; i<=n2; i++) cnt[(b[i]%pw[k])/pw[k-1]].push_back(b[i]);for(int i=0, num=0; i<=10; i++) for(auto j : cnt[i]) b[++num] = j;
}int main() {scanf("%d", &T);pw[0] = 1;for(int i=1; i<11; i++) pw[i] = pw[i-1] * 10;while(T--) {init();ll ans = 0;for(int k=1; k<=10; k++) {ksort(k);for(int i=1; i<=n1; i++) aa[i] = a[i] % pw[k];for(int i=1; i<=n2; i++) bb[i] = b[i] % pw[k];for(int i=1, p1=n2, p2=n2; i<=n1; i++) {while(aa[i] + bb[p1] >= 4ll * pw[k-1] && p1) p1--;while(aa[i] + bb[p2] >= 5ll * pw[k-1] && p2) p2--;ans += p2 - p1;}for(int i=1, p1=n2, p2=n2; i<=n1; i++) {while(aa[i] + bb[p1] >= 14ll * pw[k-1] && p1) p1--;while(aa[i] + bb[p2] >= 15ll * pw[k-1] && p2) p2--;ans += p2 - p1;}}printf("%lld\n", ans);}
}