2019 Multi-University Training Contest 7
补题链接：2019 Multi-University Training Contest 7
1001 A + B = C
题意：
给出 (a, b, c)，求 (x, y, z) 满足 (acdot 10^x + bcdot 10^y = ccdot 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
", 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) 次都是失败的，所以下一状态的花费为当前状态的花费 + 成功的花费 + 失败的花费 + 失败后再次回到当前状态的花费。于是：
又 (frac{t - 1}{t} = 1 - frac{r_i}{s_i})，即 (t = frac{s_i}{r_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
", (dp[r] - dp[l] + mod) % mod);
}
}
return 0;
}