十月做题记录

10月1日

CF54C

\(CF54C First Digit Law\)

\(Solution:\) 概率\(DP\) + 期望\(DP\)。 由简单数位 \(DP\) 可得到第 \(i\) 个数为 \(1\) 开头的概率。设 \(f[i][j]\) 表示前 \(i\) 个数有 \(j\) 个 \(1\) 开头的概率，\(f_{i,j} = p_if_{i-1,j-1} + (1-p_i)f_{i-1,j}\) 转移即可。

const int N = 1e3 + 10;
int n, k, l, r; double g[N], f[N]; int p[N];

inline int calc(int x){
    if(x == 0) return 0;
    p[0] = 1; for(int i = 1; i <= 18; i ++) p[i] = p[i - 1] * 10; int X = x;
    vector<int> a; while(x) a.push_back(x % 10), x /= 10;
    int l = a.size() - 1, ans = 0;
    for(int i = 0; i < l; i ++) ans += p[i]; if(a[l] == 1) ans += X - p[l] + 1;
    else ans += p[l]; return ans;
}
inline double solve(int x, int y){ return (calc(x) - calc(y - 1)) * 1.0 / (x - y + 1); }
 
signed main(){
    read(n); for(int i = 1, l, r; i <= n; i ++){ read(l), read(r); g[i] = solve(r, l); }
    int tem, m; read(tem); m = ceil(tem * n * 1.0 / 100); f[0] = 1;
    for(int i = 1; i <= n; i ++) for(int j = n; j >= 0; j --)
        f[j] = f[j] * (1 - g[i]) + (j > 0) * f[j - 1] * g[i];
    double ans = 0; for(int i = m; i <= n; i ++) ans += f[i]; printf("%.9g", ans);
}