我的蓝桥杯

蓝桥杯省赛结束了，是时候放松一下~

最优分组

小蓝开了一家宠物店，最近有一种 X 病毒在动物之间进行传染，小蓝为了以防万一打算购买测试剂对自己的宠物进行病毒感染测试。 为了减少使用的测试剂数目，小蓝想到了一个好方法：将 N 个宠物平均分为若干组，使得每组恰好有 K 只宠物，这样对同一组的宠物进行采样并混合后用一个试剂进行检测，如果测试结果为阴性则说明组内宠物都未感染 X 病毒；如果是阳性的话则需要对组内所有 K 只宠物单独检测，需要再消耗 K 支测试剂（当 K=1 时，就没必要再次进行单独检测了，因为组内只有一只宠物，一次检测便能确认答案）。 现在我们已知小蓝的宠物被感染的概率为 p，请问 K 应该取值为多少才能使得期望的测试剂的消耗数目最少？如果有多个答案输出最小的 K。 我们根据数学知识可以有： 然后得出公式： 当各只宠物独立地以概率 p 感染时，K > 1 的每组期望成本为 1 + K × (1 - (1-p)^K)，总成本再乘以组数 N/K。K=1 时无需复检，总成本直接为 N，不能套用混检公式。按 K 从小到大枚举 N 的约数，仅在成本更小时更新，保留最小的最优 K。

商人随从过河问题

随从们密约，在河的任一岸，一旦随从的人数比商人多，就杀人越货。 乘船渡河的方案由商人决定。 商人们怎样才能安全过河？ 3名商人 3名随从 小船至多可载2人 两岸均需满足：随从人数 ≤ 商人人数（若某岸商人人数为0，则随从人数可任意） 这是一个多步决策过程： 决策：每一步（此岸到彼岸或彼岸到此岸）船上的人员。 要求：在安全的前提下（两岸的随从数不比商人多），经有限步使全体人员过河。 我们利用DFS和BFS来进行数学建模，用DFS找出所有的符合题意且合法的状态，再利用BFS找出最短路径（图论），在BFS中记录从起点到终点的路径，一种合法的路径 --> 之前的路径，利用哈希表记录。 设置状态 (左岸商人, 左岸随从, 船的方向) 设置起点 (3, 3, '左') 设置终点 (0, 0, '右') 在遍历到目标的时候，执行函数ok，还原路径。 输出 因此所有的合法状态得出： 最短的合法路径： 一共需要11趟 过河过程（共 11 步）： 完成，全部过河。

分巧克力

子集 / 全排列

子集 Python 算法 按输入位置枚举、输出元素值；基础版本假设元素互异。若输入含重复值，可能产生重复子集。 全排列 Python 算法