NOIP 数学训练

第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 约分一下

知识点:期望的递归定义在处理无法直接用普通式子表达的时候非常好用,最后化简式子即可。

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
#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,否则有错

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
#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)$即可。

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
#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}$,因为这个组合数范围大不方便二维求出,我们预处理阶乘和阶乘逆元用定义法求解组合数。

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
#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)}$,注意要高精度。代码没写高精

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
#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

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
#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不要忘了转移花费

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
#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 输三角形 (组合数学)

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、正难则反思想

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
#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}$

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
#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 定理可以用来求模数和被求逆元数不互质下的组合数公式。

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
#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;
}

------ 本文结束 ------