洛谷P17259 [ICPC 2017 Urumqi R] Coins

hello~我又来了我这篇是本来要发洛谷题解的但是管理员给我打回了我改完了以后就不能交了所以我就在这里也写一篇啦题目传送门题目描述Alice 和 Bob 正在玩一个简单的游戏。他们将 n 枚相同的硬币排成一行初始时所有硬币均正面朝下放置在桌面上反面朝上。他们恰好进行 m 次操作每次任意选出 k 枚硬币抛向空中再以相同概率将它们正面朝上或正面朝下放回。他们的目标是使最终正面朝上的硬币尽可能多。输入格式输入包含多组测试数据第一行是一个整数 t (1≤t≤1000)表示测试数据的总组数。对于每组数据一行包含三个由空格分隔的整数 n、m (1≤n,m≤100) 和 k (1≤k≤n)。输出格式对于每组测试数据输出在最优策略下最终能够得到的正面朝上的硬币数量的期望值结果为一个实数精确到小数点后 3 位。输入输出样例输入6 2 1 1 2 3 1 5 4 3 6 2 3 6 100 1 6 100 2输出0.500 1.250 3.479 3.000 5.500 5.000好的题目我们就先说到这接下来是解析部分题目理解与分析题目描述了一个硬币游戏初始有n 枚硬币全部反面朝上即正面朝上的硬币数为 0。进行 m 次操作每次选择 k 枚硬币抛向空中每枚硬币以 0.5 的概率正面朝上或反面朝上。目标是经过 m 次操作后使正面朝上的硬币数尽可能多。我们需要求出在最优策略下最终正面朝上硬币数的期望值。关键点初始状态所有硬币反面朝上即正面朝上的硬币数为 0。操作规则每次选 kk 枚硬币抛掷后每枚硬币正面朝上的概率是 0.5反面朝上的概率也是 0.5。最优策略每次操作时如何选择 k 枚硬币使得最终正面朝上的硬币数期望最大。期望计算由于每次抛掷是独立的且每枚硬币正面朝上的概率是 0.5我们需要通过动态规划来跟踪正面朝上硬币数的概率分布并在每一步选择最优的 k 枚硬币。核心思路设当前正面朝上的硬币数为 i 反面朝上的硬币数为n-i。每次操作需要选k枚硬币。为了最大化最终正面朝上的硬币数我们应该优先选择反面朝上的硬币因为将它们抛掷后有 0.5 的概率变成正面而选择正面朝上的硬币抛掷后有 0.5 的概率变成反面这会减少正面朝上的硬币数。因此策略是尽可能多地选择反面朝上的硬币若反面硬币不足k枚则剩余的选择正面朝上的硬币。优化由于n,m≤100 k≤n 直接三维循环不可行但 xyk a和b的范围分别是 0∼x 和 0∼y 总组合数为(x1)(y1) 最大为 (k/21)²,当 k100 时50²2500m×n×2500100×100×25002.5×10⁷可以接受。预处理组合数 C(n,k) 和 0.5^n的幂次。接下来就是你们最喜欢的代码部分了这道题总体来说不是特别的难思路理清了之后就比较好做了。我考试时做的时候确实没有想到他竟然是一道普及的题我不是说我学的特好哈我也是错了好几次后才做对的。好了不说闲话了上代码。话说你们是喜欢没有注释的代码还是有注释的代码呢我写代码一般比较喜欢没注释的我在写代码前写的提示和伪代码最后都会删掉不然感觉怪怪的。参考代码带注释我认为有注释的是不是好理解一点所以加一个有注释的ps只是是我后期加上的如果不太理解的话可以私信我#include bits/stdc.h using namespace std; const int MAXN 105; double C[MAXN][MAXN]; double pow2[MAXN]; void precompute() { for (int i 0; i MAXN; i) { C[i][0] 1; for (int j 1; j i; j) { C[i][j] C[i-1][j-1] C[i-1][j]; } } pow2[0] 1.0; for (int i 1; i MAXN; i) { pow2[i] pow2[i-1] * 0.5; } } void solve() { int n, m, k; cin n m k; vectordouble dp(n 1, 0.0); dp[0] 1.0; for (int step 0; step m; step) { vectordouble np(n 1, 0.0); for (int i 0; i n; i) { if (dp[i] 0) continue; int r n - i; // 反面硬币数 int x min(r, k); // 选的反面硬币数 int y k - x; // 选的正面硬币数 double pe pow2[k];// 0.5^k for (int a 0; a x; a) { for (int b 0; b y; b) { int new_i i - y b a; double prob C[x][a] * C[y][b] * pe; np[new_i] dp[i] * prob; } } } dp np; } double ee 0.0; for (int i 0; i n; i) { ee i * dp[i]; } cout fixed setprecision(3) ee endl; } int main() { precompute(); int t; cin t; while (t--) { solve(); } return 0;//完结撒花 }参考代码赛时代码这个是我考试的时候写的代码没有注释的需要的可以自行取用不懂的不理解的可以来问我。#include bits/stdc.h using namespace std; const int MAXN 105; double C[MAXN][MAXN]; double pow2[MAXN]; void precompute() { for (int i 0; i MAXN; i) { C[i][0] 1; for (int j 1; j i; j) { C[i][j] C[i-1][j-1] C[i-1][j]; } } pow2[0] 1.0; for (int i 1; i MAXN; i) { pow2[i] pow2[i-1] * 0.5; } } void solve() { int n, m, k; cin n m k; vectordouble dp(n 1, 0.0); dp[0] 1.0; for (int step 0; step m; step) { vectordouble np(n 1, 0.0); for (int i 0; i n; i) { if (dp[i] 0) continue; int r n - i; int x min(r, k); int y k - x; double pe pow2[k]; for (int a 0; a x; a) { for (int b 0; b y; b) { int new_i i - y b a; double prob C[x][a] * C[y][b] * pe; np[new_i] dp[i] * prob; } } } dp np; } double ee 0.0; for (int i 0; i n; i) { ee i * dp[i]; } cout fixed setprecision(3) ee endl; } int main() { precompute(); int t; cin t; while (t--) { solve(); } return 0; }后记留言好了今天的讲解就到这里。附上我的AC记录如果有需要改正的地方或有不完美的地方欢迎私信我如果有不懂的欢迎私信我提问我会一一解答如果我回复的不是那么及时也请见谅马上开学了我比较忙。如果觉得我写的还行的话可以留下一个赞吗非常感谢。