内外网网站栏目建设方案郑州网站建设公司

内外网网站栏目建设方案,郑州网站建设公司,php 做资讯网站,郑州网络营销题目概述 Taha\texttt{Taha}Taha 有一副特殊的扑克牌#xff0c;包含 525252 张常规牌和 222 张 Joker\texttt{Joker}Joker 牌。常规牌的花色分为 梅花、 方块、 红心 和 黑桃 四种#xff0c;每种花色 131313 张。Joker\texttt{Joker}Joker 牌没有花色。Sara\texttt{Sara}Sa…题目概述Taha\texttt{Taha}Taha有一副特殊的扑克牌包含525252张常规牌和222张Joker\texttt{Joker}Joker牌。常规牌的花色分为梅花、方块、红心和黑桃四种每种花色131313张。Joker\texttt{Joker}Joker牌没有花色。Sara\texttt{Sara}Sara随机洗牌后逐张发牌目标是使得桌面上至少有CCC张梅花、DDD张方块、HHH张红心、SSS张黑桃。当出现Joker\texttt{Joker}Joker时Taha\texttt{Taha}Taha必须立即将其指定为某种花色以最小化达成目标所需牌数的期望值。两个Joker\texttt{Joker}Joker的指定可以不同。求这个最小期望值若不可能达成目标则输出−1.000-1.000−1.000。输入格式第一行测试用例数TTTT50T 50T50。每行四个整数C,D,H,SC, D, H, SC,D,H,S0≤C,D,H,S≤150 \le C, D, H, S \le 150≤C,D,H,S≤15。输出格式每个测试用例输出一行Case i: X.XXX其中X.XXXX.XXXX.XXX为期望值保留三位小数。解题思路详解1. 问题分析这是一个带有控制的随机过程问题可以看作一个马尔可夫决策过程MDP\texttt{MDP}MDP状态已经抽到的四种花色的数量以及已经使用且分配到各花色的Joker\texttt{Joker}Joker数量。动作当抽到Joker\texttt{Joker}Joker时选择将其分配给哪种花色。目标最小化达到目标所需的期望抽牌数。2. 状态定义令(c,d,h,s)(c, d, h, s)(c,d,h,s)表示已经抽到的四种花色的实际牌数不包括Joker\texttt{Joker}Joker转换来的。令(jc,jd,jh,js)(j_c, j_d, j_h, j_s)(jc​,jd​,jh​,js​)表示Joker\texttt{Joker}Joker被指定为四种花色的数量。由于只有222张 Joker有0≤jcjdjhjs≤20 \le j_c j_d j_h j_s \le 20≤jc​jd​jh​js​≤2。当前有效牌数为梅花cjcc j_ccjc​方块djdd j_ddjd​红心hjhh j_hhjh​黑桃sjss j_ssjs​终止条件cjc≥C,djd≥D,hjh≥H,sjs≥S c j_c \ge C,\quad d j_d \ge D,\quad h j_h \ge H,\quad s j_s \ge Scjc​≥C,djd​≥D,hjh​≥H,sjs​≥S3. 状态转移与期望计算设E(c,d,h,s,jc,jd,jh,js)E(c, d, h, s, j_c, j_d, j_h, j_s)E(c,d,h,s,jc​,jd​,jh​,js​)为当前状态下的最小期望抽牌数从当前开始到结束。当前已抽牌数drawncdhsjcjdjhjs \texttt{drawn} c d h s j_c j_d j_h j_sdrawncdhsjc​jd​jh​js​剩余牌数remain54−drawn \texttt{remain} 54 - \texttt{drawn}remain54−drawn若remain0\texttt{remain} 0remain0且未达标则E∞E \inftyE∞不可达。对于下一张牌可能是梅花概率pc13−cremainp_c \frac{13 - c}{\text{remain}}pc​remain13−c​期望贡献pc×(1E(c1,d,h,s,jc,jd,jh,js))p_c \times (1 E(c1, d, h, s, j_c, j_d, j_h, j_s))pc​×(1E(c1,d,h,s,jc​,jd​,jh​,js​))方块概率pd13−dremainp_d \frac{13 - d}{\text{remain}}pd​remain13−d​期望贡献pd×(1E(c,d1,h,s,jc,jd,jh,js))p_d \times (1 E(c, d1, h, s, j_c, j_d, j_h, j_s))pd​×(1E(c,d1,h,s,jc​,jd​,jh​,js​))红心概率ph13−hremainp_h \frac{13 - h}{\text{remain}}ph​remain13−h​期望贡献ph×(1E(c,d,h1,s,jc,jd,jh,js))p_h \times (1 E(c, d, h1, s, j_c, j_d, j_h, j_s))ph​×(1E(c,d,h1,s,jc​,jd​,jh​,js​))黑桃概率ps13−sremainp_s \frac{13 - s}{\text{remain}}ps​remain13−s​期望贡献ps×(1E(c,d,h,s1,jc,jd,jh,js))p_s \times (1 E(c, d, h, s1, j_c, j_d, j_h, j_s))ps​×(1E(c,d,h,s1,jc​,jd​,jh​,js​))Joker\texttt{Joker}Joker概率pj2−(jcjdjhjs)remainp_j \frac{2 - (j_c j_d j_h j_s)}{\text{remain}}pj​remain2−(jc​jd​jh​js​)​此时需要选择一种花色使得后续期望最小min⁡{1E(c,d,h,s,jc1,jd,jh,js)1E(c,d,h,s,jc,jd1,jh,js)1E(c,d,h,s,jc,jd,jh1,js)1E(c,d,h,s,jc,jd,jh,js1) \min \begin{cases} 1 E(c, d, h, s, j_c1, j_d, j_h, j_s) \\ 1 E(c, d, h, s, j_c, j_d1, j_h, j_s) \\ 1 E(c, d, h, s, j_c, j_d, j_h1, j_s) \\ 1 E(c, d, h, s, j_c, j_d, j_h, j_s1) \end{cases}min⎩⎨⎧​1E(c,d,h,s,jc​1,jd​,jh​,js​)1E(c,d,h,s,jc​,jd​1,jh​,js​)1E(c,d,h,s,jc​,jd​,jh​1,js​)1E(c,d,h,s,jc​,jd​,jh​,js​1)​总期望E∑suitpsuit×(1Enext)pj×Ejoker-best E \sum_{\texttt{suit}} p_{\texttt{suit}} \times (1 E_{\texttt{next}}) p_j \times E_{\texttt{joker-best}}Esuit∑​psuit​×(1Enext​)pj​×Ejoker-best​4. 可行性判断由于每种花色最多131313张牌若目标超过131313则超出的部分必须由Joker\texttt{Joker}Joker补充。设needExtramax⁡(0,C−13)max⁡(0,D−13)max⁡(0,H−13)max⁡(0,S−13) \texttt{needExtra} \max(0, C-13) \max(0, D-13) \max(0, H-13) \max(0, S-13)needExtramax(0,C−13)max(0,D−13)max(0,H−13)max(0,S−13)若needExtra2\texttt{needExtra} 2needExtra2则即使全部Joker\texttt{Joker}Joker都用上也不够输出−1.000-1.000−1.000。5. 算法设计使用记忆化搜索Memoization\texttt{Memoization}Memoization实现动态规划状态维数14×14×14×14×3×3×3×3≈3.8×10614 \times 14 \times 14 \times 14 \times 3 \times 3 \times 3 \times 3 \approx 3.8 \times 10^614×14×14×14×3×3×3×3≈3.8×106可以存储。递归边界达标时返回000无牌可抽时返回∞\infty∞。利用概率计算期望对Joker\texttt{Joker}Joker决策取最小值。6. 复杂度分析状态数144×34≈3.8×10614^4 \times 3^4 \approx 3.8 \times 10^6144×34≈3.8×106每个状态转移常数时间最多888种可能总时间复杂度O(状态数×8)O(\text{状态数} \times 8)O(状态数×8)在可接受范围内。代码实现// Cards// UVa ID: 12369// Verdict: Accepted// Submission Date: 2025-12-15// UVa Run Time: 1.010s//// 版权所有C2025邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;constdoubleINF1e30;// 表示无穷大用于不可达状态constintMAXN14;doublememo[MAXN][MAXN][MAXN][MAXN][3][3][3][3];boolvisited[MAXN][MAXN][MAXN][MAXN][3][3][3][3];intneedC,needD,needH,needS;doubledfs(intc,intd,inth,ints,intjc,intjd,intjh,intjs){// jc, jd, jh, js 分别表示Joker被指定为梅花、方块、红心、黑桃的数量// 总Joker使用数 jc jd jh js ≤ 2inttotalCcjc;inttotalDdjd;inttotalHhjh;inttotalSsjs;if(totalCneedCtotalDneedDtotalHneedHtotalSneedS){return0.0;// 目标已达成无需再抽牌}// 边界检查if(c13||d13||h13||s13)returnINF;if(jcjdjhjs2)returnINF;if(cdhsjcjdjhjs54)returnINF;intstateCmin(c,13);intstateDmin(d,13);intstateHmin(h,13);intstateSmin(s,13);if(visited[stateC][stateD][stateH][stateS][jc][jd][jh][js]){returnmemo[stateC][stateD][stateH][stateS][jc][jd][jh][js];}intremainingClubs13-c;intremainingDiamonds13-d;intremainingHearts13-h;intremainingSpades13-s;intremainingJokers2-(jcjdjhjs);intdrawnCardscdhsjcjdjhjs;intremainingCards54-drawnCards;if(remainingCards0){// 无牌可抽仍未达标visited[stateC][stateD][stateH][stateS][jc][jd][jh][js]true;memo[stateC][stateD][stateH][stateS][jc][jd][jh][js]INF;returnINF;}doubleexpected0.0;// 抽到梅花的期望if(remainingClubs0){doubleprob(double)remainingClubs/remainingCards;expectedprob*(1.0dfs(c1,d,h,s,jc,jd,jh,js));}// 抽到方块的期望if(remainingDiamonds0){doubleprob(double)remainingDiamonds/remainingCards;expectedprob*(1.0dfs(c,d1,h,s,jc,jd,jh,js));}// 抽到红心的期望if(remainingHearts0){doubleprob(double)remainingHearts/remainingCards;expectedprob*(1.0dfs(c,d,h1,s,jc,jd,jh,js));}// 抽到黑桃的期望if(remainingSpades0){doubleprob(double)remainingSpades/remainingCards;expectedprob*(1.0dfs(c,d,h,s1,jc,jd,jh,js));}// 抽到Joker的期望if(remainingJokers0){doubleprob(double)remainingJokers/remainingCards;doublebestINF;// 尝试四种花色选择期望最小的if(jcjdjhjs2){bestmin(best,1.0dfs(c,d,h,s,jc1,jd,jh,js));bestmin(best,1.0dfs(c,d,h,s,jc,jd1,jh,js));bestmin(best,1.0dfs(c,d,h,s,jc,jd,jh1,js));bestmin(best,1.0dfs(c,d,h,s,jc,jd,jh,js1));}expectedprob*best;}visited[stateC][stateD][stateH][stateS][jc][jd][jh][js]true;memo[stateC][stateD][stateH][stateS][jc][jd][jh][js]expected;returnexpected;}intmain(){intT;cinT;for(intt1;tT;t){cinneedCneedDneedHneedS;// 检查是否可能intrequired0;if(needC13)requiredneedC-13;if(needD13)requiredneedD-13;if(needH13)requiredneedH-13;if(needS13)requiredneedS-13;if(required2){printf(Case %d: -1.000\n,t);continue;}// 初始化记忆化数组memset(visited,0,sizeof(visited));doubleresultdfs(0,0,0,0,0,0,0,0);if(result1e20){printf(Case %d: -1.000\n,t);}else{printf(Case %d: %.3lf\n,t,result);}}return0;}总结本题的核心在于状态的定义和期望的计算状态需要区分“抽到的花色牌”和“Joker\texttt{Joker}Joker转换的花色牌”因为Joker\texttt{Joker}Joker的分配是可控决策。期望计算采用标准的条件期望公式对Joker\texttt{Joker}Joker的决策取最小值。使用记忆化搜索避免重复计算确保在合理时间内完成。