Rikka with Mista

Posted on | In , , ,

题目链接

题意

一个人有$n$张牌，每张牌$i$正面有，反面有$0$，没面概率是。现在所有牌随意摆放，朝上面的数字求和为$S$，记录$S$的十进制表示中$4$的个数。问所有摆放方式的和为多少。

思路

计算贡献，每一位为$4$的方案数都计算出来，然后双指针扫一下。
关键这个基数排序，比我原来做法少一个$\log$，我觉得其思想我好像还没掌握？

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define mp make_pair
#define pb push_back
const int N=50;
int n,w[N];
struct atom{
    long long l,r;
};
vector<atom>x,y,A[10],B[10];
void solve(int k1,int lim,long long sum,vector<atom>&x){
    if (k1>lim){
        x.push_back((atom){sum,0}); return;
    }
    solve(k1+1,lim,sum,x);
    solve(k1+1,lim,sum+w[k1],x);
}
long long get0(vector<atom>&A,vector<atom>&B,long long lim){
    int now=B.size()-1;
    long long ans=0;
    for (int i=0;i<A.size();i++){
        while (now>=0&&B[now].r+A[i].r>=lim) now--;
        ans+=now+1;
    }
    return ans;
}
long long get1(vector<atom>&A,vector<atom>&B,long long lim){
    int now=0;
    long long ans=0;
    for (int i=A.size();i;i--){
        while (now<B.size()&&B[now].r+A[i-1].r<lim) now++;
        ans+=B.size()-now;
    }
    return ans;
}
void solve(){
    scanf("%d",&n);
    for (int i=1;i<=n;i++) scanf("%d",&w[i]);
    //n=40;
    //for (int i=1;i<=n;i++) w[i]=rand()%1000000000+1;
    int mid=n/2; x.clear(); y.clear();
    solve(1,mid,0,x);
    solve(mid+1,n,0,y);
    long long ans=0;
    long long base=1;
    for (int t=1;t<=12;t++){
        for (int i=0;i<10;i++) A[i].clear(),B[i].clear();
        for (int i=0;i<x.size();i++) A[x[i].l%10].push_back((atom){x[i].l/10,x[i].r});
        for (int i=0;i<y.size();i++) B[y[i].l%10].push_back((atom){y[i].l/10,y[i].r});

        for (int i=0;i<10;i++){
            int k1=(14-i)%10,k2=(13-i)%10;
            ans+=get0(A[i],B[k1],base)+get1(A[i],B[k2],base);
        }
        int now=0;
        for (int i=0;i<10;i++){
            long long ex=i*base;
            for (int j=0;j<A[i].size();j++)
                x[now++]=(atom){A[i][j].l,A[i][j].r+ex};
        }
        now=0;
        for (int i=0;i<10;i++){
            long long ex=i*base;
            for (int j=0;j<B[i].size();j++)
                y[now++]=(atom){B[i][j].l,B[i][j].r+ex};
        }
        base*=10;
    }
    printf("%lld\n",ans);
}
int main(){
    int t; scanf("%d",&t);
    for (;t;t--) solve();
    return 0;
}

0%