第1题 LightOJ - 1027 A Dangerous Maze (期望)
LightOJ - 1027 A Dangerous Maze
题意：小Q在迷宫中，他站在$n$个门前面，每个门只有两个可能，要么在$A_i$时间后，回到原地，要么在$A_i$时间后离开迷宫。每次他都会随机选择一个门，计算他离开的期望时间。
解：设当前期望为$E$
如果选择了正数时间，那么期望值为$\frac{A_i}{n}$
如果选择了负数时间，那么期望值为$\frac{E-A_i}{n}$，因为浪费了$-A_i$的时间
然后让所有负数和为$T_0$，负数个数为$n_0$，正数和为$T_1$，正数个数为$n_1$
$E=\frac{T_1}{n}+\frac{n_0E-T_0}{n}$，整理可得$E=\frac{T_1-T_0}{n_1}$，用 GCD 约分一下
知识点：期望的递归定义在处理无法直接用普通式子表达的时候非常好用，最后化简式子即可。
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<vector>
#include<climits>
#include<cmath>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
#define fir first
#define sec second
#define mp make_pair
using namespace std;
namespace flyinthesky {
int gcd(int a, int b) {
return (b == 0) ? a : gcd(b, a % b);
}
void clean() {}
int solve() {
int n, K, T0, T1, N1, kase = 0;
cin >> K;
clean();
while (K--) {
T0 = 0, T1 = 0, N1 = 0;
++kase, cin >> n;
for (int x, i = 1; i <= n; i++) {
cin >> x;
if (x < 0) T0 += x; else T1 += x, ++N1;
}
int x = -T0 + T1, y = N1;
if (y == 0) printf("Case %d: inf\n", kase); else {
int g = gcd(x, y);
printf("Case %d: %d/%d\n", kase, x / g, y / g);
}
}
return 0;
}
}
int main() {
flyinthesky::solve();
return 0;
}
第2题 LightOJ - 1030 Discovering Gold (期望DP)
LightOJ - 1030 Discovering Gold
题意：有一个直线的金矿，每个点有一定数量的金子；你从$0$开始，每次扔个骰子，扔出几点就走几步，然后把那个点的金子拿走；如果扔出的骰子超出了金矿，就重新扔，知道你站在最后一个点；问拿走金子的期望值是多少
解：设$dp(i)$为从$i$到$n$的期望值，则$dp(i)=\frac{1}{x}\sum dp(i + j) + a_i$，其中$x$是不超出金矿的掷骰子次数。初始化$dp(i)=a_i$
答案是$dp(1)$。注意本题正推有问题，无法保证$dp(n)$由$1$推来。
我们类比飞行棋那题，发现那题因为出现了航线所以不能倒推，否则能倒推。并且本题因为不能掷骰子的数大于$n$，所以不能像飞行棋那题一样全部概率为定值，在边缘的概率不一样。
知识点：
1、要看期望DP的状态是否从无效状态推向有效来确定枚举顺序
2、每一步概率和为1，否则有错
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<vector>
#include<climits>
#include<cmath>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
#define fir first
#define sec second
#define mp make_pair
using namespace std;
int kase = 0;
namespace flyinthesky {
int n, a[105];
db dp[105];
void clean() {
ms(dp, 0);
}
int solve() {
cin >> n;
clean();
for (int i = 1; i <= n; i++) cin >> a[i], dp[i] = a[i];
for (int i = n - 1; i >= 1; i--) {
db tmp = 0.0;
int tms = 0;
for (int j = 1; j <= 6; j++) {
if (i + j <= n) tmp += dp[i + j], ++tms;
}
dp[i] = tmp / (db)tms + a[i];
}
printf("Case %d: %.7f\n", ++kase, dp[1]);
return 0;
}
}
int main() {
int T; cin >> T;
while (T--) flyinthesky::solve();
return 0;
}
第3题 Loj 10230/Bzoj 3398 牡牛和牝牛 (组合数学)
Loj 10230
题意：见上。
解：
方法1：DP
设$dp(i)$表示$i$位置以牡牛结尾的方案数。
那么$dp(i)=\sum^{i-k-1}_{j=1} dp(j)$，使$pre(i)=\sum^{i}_{j=1} dp(j)$，那么原转移方程变为$O(n)$，最后输出$pre(n)$即可。
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<vector>
#include<climits>
#include<cmath>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
#define fir first
#define sec second
#define mp make_pair
using namespace std;
namespace flyinthesky {
const LL MO = 5000011;
LL n, k, dp[100000 + 5], pre[100000 + 5];
void clean() {
}
int solve() {
cin >> n >> k;
clean();
pre[0] = dp[0] = 1;
for (LL i = 1; i <= n; i++) {
dp[i] = pre[max(i - k - 1, 0ll)];
pre[i] = (pre[i - 1] + dp[i]) % MO;
//cout << dp[i] << " " << pre[i] << endl;
}
cout << pre[n];
return 0;
}
}
int main() {
flyinthesky::solve();
return 0;
}
方法2：排列组合
考虑枚举当前方案的牡牛只数$i$，可以知道每个犊牛间一定有$k$个牝牛，所以每次将这固定的$(i-1) \cdot k$个牝牛删除，然后再剩下的牛中选$i$个犊牛，将删除的牝牛加回来显然满足条件。所以答案是$C^{i}_{(i-1) \cdot k}$，因为这个组合数范围大不方便二维求出，我们预处理阶乘和阶乘逆元用定义法求解组合数。
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<vector>
#include<climits>
#include<cmath>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
#define fir first
#define sec second
#define mp make_pair
using namespace std;
namespace flyinthesky {
const LL MO = 5000011;
LL n, k, jc[100000 + 5], jc_inv[100000 + 5];
LL ksm(LL a, LL b) {
LL bs = a % MO, ans = 1ll;
while (b) {
if (b & 1) ans = (ans * bs) % MO;
bs = (bs * bs) % MO;
b >>= 1ll;
}
return ans;
}
LL c(LL n, LL m) {
if (m > n) return 0;
LL tmp = jc[n];
tmp = (tmp * jc_inv[m]) % MO;
tmp = (tmp * jc_inv[n - m]) % MO;
return tmp;
}
void clean() {
}
int solve() {
cin >> n >> k;
clean();
jc[0] = jc[1] = 1ll;
jc_inv[0] = jc_inv[1] = 1ll;
for (int i = 2; i <= n; i++) {
jc[i] = (jc[i - 1] * i) % MO;
jc_inv[i] = (jc_inv[i - 1] * ksm(i, MO - 2)) % MO;
}
int ans = 0ll;
for (int i = 1; i <= n; i++) {
int tmp = n - (i - 1ll) * k;
if (tmp < 0) break ;
ans = (ans + c(tmp, i)) % MO;
}
cout << ans + 1ll;
return 0;
}
}
int main() {
flyinthesky::solve();
return 0;
}
知识点：
1、计数问题可以 1 DP 2 组合数学
2、DP 方程如果出现了求前缀DP和，可以用前缀和优化
3、排列组合中将定下来的东西删除或者添加不影响答案的东西(插板法求有空的部分)可以帮助解题
4、预处理能带入$n$就用$n$，防止 TLE
第4题 Loj 10231 方程的解 (组合数学)
Loj 10231
题意：见上。
解：显然插板法求。用快速幂算出$g(x)$，然后答案为$C^{k}_{g(x)}$，注意要高精度。代码没写高精
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<vector>
#include<climits>
#include<cmath>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
#define fir first
#define sec second
#define mp make_pair
using namespace std;
namespace flyinthesky {
LL k, x, c[1005][1005];
LL ksm(LL a, LL b, LL c) {
LL bs = a % c, ans = 1ll;
while (b) {
if (b & 1) ans = (ans * bs) % c;
bs = (bs * bs) % c;
b >>= 1;
}
return ans;
}
void clean() {
ms(c, 0);
}
int solve() {
clean();
cin >> k >> x;
for (LL i = 0; i <= 1001; ++i) c[i][i] = c[i][0] = 1;
for (LL i = 2; i <= 1001; ++i) {
for (LL j = 1; j < i; ++j) c[i][j] = c[i - 1][j] + c[i - 1][j - 1];
}
/*for (LL i = 0; i <= 10; ++i) {
for (LL j = 0; j <= i; ++j) printf("%I64d%c", c[i][j], (j == i) ? '\n' : ' ');
}*/
LL gg = ksm(x, x, 1000ll);
//cout << gg << endl;
cout << c[gg - 1][k - 1];
return 0;
}
}
int main() {
flyinthesky::solve();
return 0;
}
第5题 Loj 10232 车的放置 (组合数学)
Loj 10232
题意：见上。
解：
方法1：排列组合
我们先考虑不被切掉一块的方法，很显然是$C^{n}_{k} \cdot A^{k}_{m}$，其中长为$n$, 宽$m$。
然后我们考虑切一块的方法，我们将它分成两个矩形来处理，然后枚举一个矩形放几个车，设当前枚举到$i$, 则最终答案加上$C^{a}_{i} \cdot A^{i}_{b} \cdot C^{a+c-i}_{k-i} \cdot A^{k - i}_{d}$
方法2：DP
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<vector>
#include<climits>
#include<cmath>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
#define fir first
#define sec second
#define mp make_pair
using namespace std;
namespace flyinthesky {
LL MO = 100000 + 3;
LL a, b, c, d, k, C[2005][2005];
void clean() {
ms(C, 0);
}
int solve() {
cin >> a >> b >> c >> d >> k;
clean();
LL sz = a + c;
for (LL i = 0; i <= sz; ++i) C[i][i] = C[i][0] = 1;
for (LL i = 2; i <= sz; ++i)
for (LL j = 1; j < i; ++j) C[i][j] = (C[i - 1][j] + C[i - 1][j - 1]) % MO;
/*for (LL i = 0; i <= sz; ++i)
for (LL j = 0; j <= i; ++j) printf("%I64d%c", C[i][j], j == i ? '\n' : ' ');*/
LL ans = 0ll;
for (LL i = 0; i <= k; ++i) {
LL tmp = C[a][i];
for (LL j = b; j >= b - i + 1; --j) tmp = (tmp * j) % MO;
tmp = (tmp * C[a + c - i][k - i]) % MO;
for (LL j = d; j >= d - (k - i) + 1; --j) tmp = (tmp * j) % MO;
ans = (ans + tmp) % MO;
}
cout << ans;
return 0;
}
}
int main() {
flyinthesky::solve();
return 0;
}
第6题 LightOJ - 1038 Race to 1 Again (期望DP)
LightOJ - 1038 Race to 1 Again
题意：给定一个整数$n$, 每次操作可以对当前数进行除以它的某个因子。除以哪个因子是随机的，求把$n$变成$1$的期望步数。
解：设$dp(i)$为$i$除到$1$的期望步数。
则$dp(i)=\frac{dp(a_1)+dp(a_2)+…+dp(a_n)}{m}+1$，其中$a_n | i$，我们将右边的$dp(i)$拿过来以后式子变为$dp(i)=\frac{dp(a_1)+dp(a_2)+…+dp(a_{n-1})+m}{m-1}$
然后DP即可，先进行DP后$O(1)$询问。
知识点：
1、这题使用了记忆化打表的思想
2、期望DP式子右边有$dp(i)$就移到左边
3、期望DP不要忘了转移花费
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<vector>
#include<climits>
#include<cmath>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
#define fir first
#define sec second
#define mp make_pair
using namespace std;
namespace flyinthesky {
int n, p[100005], sz; //p[index] = val, sz is index
db dp[100005]; //dp[val] = expected number
void clean() {
}
int solve() {
clean();
dp[1] = 0.0;
for (int x = 2; x <= 100000; ++x) {// x is val
sz = 0;
for (int i = 1; i * i <= x; ++i) { // i is val, x / i is val
if (x % i == 0) p[++sz] = i;
if (i != (x / i) && x % (x / i) == 0) p[++sz] = x / i;
}
for (int i = 1; i <= sz; ++i) dp[x] += dp[p[i]]; // i is index
dp[x] += sz, dp[x] /= (db)(sz - 1);
}
int T, kase = 0; scanf("%d", &T);
while (T--) {
cin >> n;
printf("Case %d: %.8f\n", ++kase, dp[n]);
}
return 0;
}
}
int main() {
flyinthesky::solve();
return 0;
}
第7题 Bzoj 3505 输三角形 (组合数学)
第8题 LightOJ - 1079 Just another Robbery (概率背包DP)
题意：XX想抢银行，当危险率低于$P$的时候才能行动，现在给出每家银行的金钱$m_i$和危险率$p_i$，求最多能获得多少金钱。
解：设$dp(i,j)$为前$i$个银行抢$j$元钱的不被抓概率。
$dp(i,j)=min(dp(i-1,j-w_i) \cdot (1-p_i))$
转移即可
知识点：
1、设概率求期望
2、正难则反思想
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<vector>
#include<climits>
#include<queue>
#include<cmath>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
#define fir first
#define sec second
#define mp make_pair
using namespace std;
int kase = 0;
namespace flyinthesky {
const db INF = 1000000000.0, eps = 1e-9;
const int MAXV = 10005;
db maxP, p[105], dp[10010];
int n, w[105];
void clean() {
for (int i = 0; i <= MAXV; ++i) dp[i] = -INF;
}
int solve() {
scanf("%lf%d", &maxP, &n);
for (int i = 1; i <= n; ++i) scanf("%d%lf", &w[i], &p[i]);
clean();
dp[0] = 1.0;
for (int i = 1; i <= n; ++i) {
for (int j = MAXV; j >= w[i]; --j) {
dp[j] = max(dp[j], dp[j - w[i]] * (1 - p[i]));
}
}
int ans = 0;
for (int j = MAXV; j >= 0; --j) {
db tmp = 1.0 - dp[j];
if (maxP - tmp > -eps) {
ans = j; break;
}
}
printf("Case %d: %d\n", ++kase, ans);
return 0;
}
}
int main() {
int T; scanf("%d", &T);
while (T--) flyinthesky::solve();
return 0;
}
第9题 LightOJ - 1265 Island of Survival (期望)
LightOJ - 1265 Island of Survival
题意：有$ t $只老虎，$ d $只鹿，还有一个人，每天都要有两个生物碰面，现在有以下规则：老虎不管碰到谁都吃掉，同类的话就同归于尽。问人存活下来的概率。
解：如果老虎有奇数只，那么老虎绝对可以把人吃掉，概率为0
如果老虎有偶数只，那么老虎可以两两吃掉，并且人遇到鹿不会死，所以人存活的概率和鹿没关系。
所以我们从$t+1$个生物中选1个出来当做幸存者，那么人存活概率为$\frac{1}{t+1}$
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#define LL long long
#define db double
#define ms(i, j) memset(i, j, sizeof i)
using namespace std;
namespace flyinthesky {
void clean() {
}
int solve() {
clean();
int kase = 0, T; scanf("%d", &T);
while (T--) {
int t, d; scanf("%d%d", &t, &d);
if (t % 2 == 0) printf("Case %d: %.8f\n", ++kase, 1.0 / (t + 1.0));
else printf("Case %d: 0\n", ++kase);
}
return 0;
}
};
int main() {
flyinthesky::solve();
return 0;
}
第10题 LightOJ - 10228 Discovering Gold (Lucas 定理)
#10228. 「一本通 6.6 例 3」组合
题意：见上。
解：发现 $ m $ 很小，我们用组合数阶乘定义式两边求，即先乘$(n-m+1)$到$n$，再除$m!$。然后因为 $ p $ 不一定和所要求逆元的数互质，所以我们要用 Lucas 定理来求，因为 Lucas 保证了每次的组合数$n, m$小于 $p$，并且$p$为质数，所以不会有不互质的情况。
知识点： Lucas 定理可以用来求模数和被求逆元数不互质下的组合数公式。
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<vector>
#include<map>
#include<cmath>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
#define fir first
#define sec second
#define mp make_pair
using namespace std;
namespace flyinthesky {
LL n1, m1, p;
LL ksm(LL a, LL b) {
LL bs = a % p, ans = 1ll;
while (b) {
if (b & 1) ans = (ans * bs) % p;
bs = (bs * bs) % p;
b >>= 1;
}
return ans;
}
LL C(LL n, LL m) {
LL ans = 1ll, ni = 1ll;
for (LL i = n - m + 1; i <= n; ++i) ans = (ans * i) % p;
for (LL i = 2; i <= m; ++i) ni = (ni * ksm(i, p - 2)) % p;
return (ans * ni) % p;
}
LL lucas(LL n, LL m) {
if (m == 0) return 1;
return (C(n % p, m % p) * lucas(n / p, m / p)) % p;
}
void clean() {
}
int solve() {
clean();
cin >> n1 >> m1 >> p;
cout << lucas(n1, m1) << endl;
return 0;
}
}
int main() {
int T; scanf("%d", &T);
while (T--) flyinthesky::solve();
return 0;
}
第11题 Poj 1845 (分治+分解质因数+约数和公式 / 逆元讨论)
Poj 1845
题意：求$A^B$因子和。
解：这里主要讲讲等比数列求和方法。
可以用逆元，但是模的质数太小可能有倍数关系不存在逆元，但是可以通过同余来化简特判没逆元的情况。
也可以在$log(c)$的时间内分治求解, 具体看算法竞赛进阶指南上的解析，注意分治边界特判
注意$B=0$
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<vector>
#include<queue>
#include<cmath>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
#define fir first
#define sec second
#define mp make_pair
using namespace std;
namespace flyinthesky {
const LL MO = 9901;
LL A, B, pri[50000000 + 5], cnt[50000000 + 5], tot;
LL ksm(LL a, LL b) {
LL bs = a % MO, ans = 1ll;
while (b) {
if (b & 1) ans = (bs * ans) % MO;
bs = (bs * bs) % MO;
b >>= 1;
}
return ans;
}
LL sum(LL n, LL q) {
if (n == 0) return 0;
if (n == 1) return q + 1;
if (n == 2) return q + 1 + q * q;
if (n % 2 == 1) {
return (1ll + ksm(q, (n + 1) >> 1)) * sum((n - 1) >> 1, q) % MO;
} else {
LL qtmp = ksm(q, n >> 1);
LL qtmp2 = ksm(q, (n >> 1) + 1);
return (qtmp + ((qtmp2 + 1ll) * sum((n >> 1) - 1, q) % MO)) % MO;
}
}
void clean() {
tot = 0;
}
int solve() {
cin >> A >> B;
if (B == 0) return cout << 1 << endl, 0;
clean();
for (LL i = 2; i * i <= A; ++i) {
if (A % i == 0) {
pri[++tot] = i;
while (A % i == 0) A /= i, ++cnt[tot];
}
}
if (A != 1) ++cnt[++tot], pri[tot] = A;
LL ans = 1ll;
for (LL i = 1; i <= tot; ++i) {
ans = (ans * sum(cnt[i] * B, pri[i])) % MO;
}
cout << ans;
return 0;
}
}
int main() {
flyinthesky::solve();
return 0;
}
第12题 P1365 WJMZBMR打osu! / Easy
利用两个数组DP，期望值计算
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<cmath>
#include<map>
#include<queue>
#include<set>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
#define fir first
#define sec second
#define mp make_pair
using namespace std;
namespace flyinthesky {
int n;
db f[300000 + 5], g[300000 + 5];
char s[300000 + 5];
void clean() {
}
int solve() {
clean();
cin >> n;
scanf("%s", s + 1);
for (int i = 1; i <= n; ++i) {
if (s[i] == 'o')
f[i] = f[i - 1] + 2.0 * g[i - 1] + 1.0, g[i] = g[i - 1] + 1.0;
else if (s[i] == 'x')
f[i] = f[i - 1], g[i] = 0.0;
else
f[i] = f[i - 1] + g[i - 1] + 0.5, g[i] = (g[i - 1] + 1) / 2.0;
}
printf("%.4f\n", f[n]);
return 0;
}
}
int main() {
flyinthesky::solve();
return 0;
}
第13题 CF 1154 G. Minimum Possible LCM
CF 1154 G. Minimum Possible LCM
可以枚举因数$d$，然后$O(n\ln n)$去找，然后算第一个和第二个的$\text{lcm}$即可，具体可以容易证明。
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<cmath>
#include<map>
#include<queue>
#include<set>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
#define fir first
#define sec second
#define mp make_pair
using namespace std;
namespace flyinthesky {
const int MAXN = 1000000 + 5;
LL n, a[MAXN], vis[10000000 + 5], ans = 1e18;
LL g1, g2;
LL gcd(LL a, LL b) {return b != 0 ? gcd(b, a % b) : a;}
LL lcm(LL a, LL b) {return a * b / gcd(a, b);}
void clean() {
}
int solve() {
clean();
cin >> n;
for (LL i = 1; i <= n; ++i) {
scanf("%lld", &a[i]);
if (vis[a[i]]) {
if (ans > a[i]) ans = a[i], g1 = vis[a[i]], g2 = i;
}
vis[a[i]] = i;
}
for (LL d = 1; d <= 10000000; ++d) {
if (d >= ans) break ;
LL h1 = 0, h2 = 0;
for (LL j = d; j <= 10000000; j += d) {
if (vis[j]) {
if (!h1) h1 = j; else if (!h2) h2 = j; else break;
}
}
if (h1 && h2) {
if (lcm(h1, h2) < ans) ans = lcm(h1, h2), g1 = vis[h1], g2 = vis[h2];
}
}
if (g1 > g2) swap(g1, g2);
cout << g1 << " " << g2 << endl;
return 0;
}
}
int main() {
flyinthesky::solve();
return 0;
}
