2019 杭电多校第七场

2019 Multi-University Training Contest 7

补题链接：2019 Multi-University Training Contest 7

1001 A + B = C

题意：

给出 $a, b, c$，求 $x, y, z$ 满足 $a\cdot 10^x + b\cdot 10^y = c\cdot 10^z$。$a, b, c \le 10^{100000}$。

题解：

补零到 $a, b, c$ 长度相等之后，可能的情况只有四种: $b | (c − a), b | (10 · c − a), a | (c − b), a | (10 · c − b)$。

Java 写炸了。

1006 Final Exam (HDU 6651)

题意：

一次考试共有 $n$ 道题，总分为 $m$ 分。每道题的分数不一定，可能是 $0$ 分，也可能是 $m$ 分，分数一定是整数。如果一道题分数为 $x$，那么复习这道题的时间为 $x + 1$，现在要保证在考试中做出 $k$ 题，求准备考试的时间最少为多少。

题解：

思维

如果做不出 $k$ 题，那么也就是复习时间最少的 $n − k + 1$ 道题的难度都小于等于复习的时间。因此想要做出 $k$ 题，只要让复习时间最少的 $n − k + 1$ 道题的复习时间总和 $> m$ 即可。

也就是 $n - k + 1$ 道题的复习时间总和为 $m + 1$，剩下 $k - 1$ 道题的复习时间不是最少的 $k - 1$ 道题即可。

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

int main() {
    int T;
    cin >> T;
    while(T--) {
        ll n, m, k;
        scanf("%lld%lld%lld", &n, &m, &k);
        printf("%lld\n", m + 1 + (m / (n - k + 1) + 1) * (k - 1));
    }
    return 0;
}

1011 Kejin Player (HDU 6656)

题意：

从 $i$ 级升级到 $i + 1$ 级需要花费 $a_i$ RMB，成功的概率为 $p_i = \frac{r_i}{s_i}$，若失败则降到 $x_i$ 级，然后给出 $q$ 个询问求 $l$ 级升级到 $r$ 级花费的期望。

题解：

期望DP 逆元

设 $g(l, r)$ 为 $l$ 升到 $r$ 的期望，这种期望满足减法 $g(l, r) = g(1, r) − g(1, l)$。因为升级只能一级一级升, 所以要从 $1$ 升级到 $r$, 必然要经过 $l$。可以降维，用 $dp[i]$ 表示从 $1$ 升到 $i$ 的期望，则 $g(l, r) = dp[r] − dp[l]$。

从 $dp[i]$ 转移至 $dp[i + 1]$，假设尝试了 $t$ 次才成功，那么也就是前面 $t - 1$ 次都是失败的，所以下一状态的花费为当前状态的花费 + 成功的花费 + 失败的花费 + 失败后再次回到当前状态的花费。于是：

$dp[i + 1] = dp[i] + 1 \times a[i] + (t - 1) \times a[i] + (t- 1) \times (dp[i] - dp[x_i])$

又 $\frac{t - 1}{t} = 1 - \frac{r_i}{s_i}$，即 $t = \frac{s_i}{r_i}$

于是状态转移方程为：

$dp[i + 1] = dp[i] + \frac{s_i}{r_i} \times a[i] + (\frac{s_i}{r_i} - 1) \times (dp[i] - dp[x_i])$

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 5e5 + 10;
const ll mod = 1e9 + 7;

ll r[maxn], s[maxn], x[maxn], a[maxn];

ll dp[maxn];

ll qmod(ll a, ll b, ll p) {
    ll ans = 1;
    while(b) {
        if(b & 1) ans = (a * ans) % p;
        a = (a * a) % p;
        b >>= 1;
    }
    return ans;
}

int main() {
    int T;
    cin >> T;
    while(T--) {
        int n, q;
        scanf("%d%d", &n, &q);
        for(int i = 1; i <= n; ++i) {
            scanf("%lld%lld%lld%lld", &r[i], &s[i], &x[i], &a[i]);
            ll t = (s[i] * qmod(r[i], mod - 2, mod)) % mod;
            dp[i + 1] = (dp[i] + (t * a[i]) % mod + ((t - 1) * (dp[i] - dp[x[i]])) % mod + mod) % mod;
        }
        for(int i = 0; i < q; ++i) {
            int l, r;
            scanf("%d%d", &l, &r);
            printf("%lld\n", (dp[r] - dp[l] + mod) % mod);
        }
    }
    return 0;
}