信息学中概率类题目的分析.doc

信息学中概率类题目的分析上海市上海中学 swj05652关键词： 信息学 概率 动态规划 这篇文章中的“概率类题 目” 指的是题目所求 为某一事件的发生几率或是某一个量的平均意义下的值通常要求输出一个小数或是一个最简分数这类题目通常会涉及到递推或是动态规划的思想一般来说要抓住这一点去进行思考下面我们来看几道典型题目终极情报网神奇口袋百事世界杯之旅单人纸牌三国围棋对抗赛并行期望值迷宫统计神经衰弱聪聪和可可巧克力总结终极情报网agent.pas (exe)【题目叙述】在最后的诺曼底登陆战开始之前，盟军与德军的情报部门围绕着最终的登陆地点展开了一场规模空前的情报战这场情报战中，盟军的战术是利用那些潜伏在敌军内部的双重间谍，将假的登陆消息发布给敌军的情报机关的负责人那些已经潜入敌后的间谍们都是盟军情报部的精英，忠实可靠；但是如何选择合适的人选，以及最佳的消息传递方法，才能保证假消息能够尽快而且安全准确地传递到德军指挥官们的耳朵里，成了困扰盟军情报部长的最大问题他需要你的帮助以下是情报部长提供的作战资料：在敌后一共潜伏着我方最优秀的 N 名间谍，分别用数字 1, 2, …, N 编号在给定的作战时间内，任意两人之间至多只进行一次点对点的双人联系。

我将给你一份表格，表格中将提供任意两位间谍 i 和 j 之间进行联系的安全程度，用一个 [0, 1] 的实数 Si j 表示；以及他们这次联系时，能够互相传递的消息的最大数目，用一个正整数表示 Mi j (如果在表格中没有被提及，那么间谍 i和 j 之间不进行直接联系)假消息从盟军总部传递到每个间谍手里的渠道也不是绝对安全，我们用 [0, 1] 的实数 ASj 表示总部与间谍 j 之间进行联系的安全程度， AMj 则表示总部和间谍 j 之间进行联系时传递的消息的最大数目对于不和总部直接联系的间谍，他的 AMj=0（而表格中给出的他的 ASj 是没有意义的） 当然，假消息从间谍手中交到敌军的情报部官员的办公桌上的过程是绝对安全的，也即是说，间谍与敌军情报部门之间要么不进行直接联系，要么其联系的安全程度是 1（即完全可靠） 现在情报部打算把 K 条假消息“透露”到德军那里消息先由总部一次性发给 N 名间谍中的一些人，再通过他们之间的情报网传播，最终由这 N 名间谍中的某些将情报送到德军手中对于一条消息，只有安全的通过了所有的中转过程到达敌军情报部，这个传递消息的过程才算是安全的；因此根据乘法原理，它的安全程度 P 就是从总部出发，经多次传递直到到达德军那里，每一次传递该消息的安全程度的乘积。

而对于整个计划而言，只有当 N 条消息都安全的通过情报网到达德军手中，没有一条引起怀疑时，才算是成功的所以计划的可靠程度是所有消息的安全程度的乘积显然，计划的可靠性取决于这些消息在情报网中的传递方法我需要一个方案，确定消息应该从哪些人手中传递到哪些人手中，使得最终计划的可靠性最大你可以利用计算机，来求得这个最可靠的消息传递方案输入文件】输入文件 agent.in 包含了盟军的作战资料表格第一行包括两个整数 N 和 K，分别是间谍的总人数和计划包含的消息总数第二行包括 2N 个数，前 N 个数是实数 AS1, AS2, …, ASN（范围在[0, 1]以内）；后 N 个数是整数 AM1, AM1, …, AMN第三行包含了 N 个整数，其中第 i（i = 1, 2, …, N）个整数如果为 0 表示间谍 i 与德军情报部不进行联系，如果为 1 则表示间谍与德军情报部进行联系第四行开始，每行包括 4 个数，依次分别是：代表间谍编号的正整数 i 和j，间谍 i 和 j 联系的安全性参数 Si j（[0，1]范围内的实数） ，以及 i、j 之间传递的最大消息数 Mi j（每一行的 i 均小于 j ） 。

最后的一行包含两个整数-1 -1，表示输入数据的结束010 的在 Pentium 4 1.70GHz CPU 上 n=15 大约 17sn=10 在 5s 之内考虑到当时 cpu 没有那么快，这个程序应当可以勉强过关这个算法仍然有待改进 （比如搜索中如何剪枝每一次搜索都要做一下递推，能否利用上次的结果空间消耗很小，怎么拿空间换时间这三大问题其实是一体的，一旦解决，时间效率将有极大的提高 ）(From SHTSC 2001)并行期望值(From 《算法艺术与信息学竞赛》 P125)迷宫统计Jimmy 自己办了一个游园活动，其中一个项目是让游客去走一个随机生成的m 行 n()列的迷宫，迷宫里有空地，也有障碍物（每个障碍物恰好占一个方格） 游客总是从左上角走到右下角，每次可以往东南西北四个方向之一行走迷宫的生成方式很简单：每一个格子都有一个独立的概率 p，表示该格子为障碍物的概率如果程序生成了一个误解的迷宫，他会重新生成一个你的任务是计算每个格子成为一个有解迷宫中的障碍物的概率From 《算法艺术与信息学竞赛》 P139）神经衰弱（shinkei）【题目叙述】有个游戏相信大家都不陌生，拿一副 54 张的扑克牌，面朝下铺开在桌子上。

一个人每次翻开两张牌，如果两张牌点数一样，则把这两张牌同时拿走，否则的话，就还是把两张牌翻回去就这样继续，直到所有牌全部被拿完看自己可以在多少轮内把牌拿完在日本，一般管这个游戏叫神经衰弱我们把这个问题扩展到更一般的情形假设有 n 种不同的牌，每一种牌有完全相同的 2m 张假设你是一个记忆力非常好的人，只要看过一次的牌就绝对不会忘记并且，你总是按照这样的步骤进行游戏：· 如果存在至少一对已知的牌，则下一步一定是将这两张牌翻开并拿走，如果这样的牌不止一对，则从其中任意选择一对· 如果不存在已知的相同的牌，则首先从未知的牌中任意翻开一张如果这张牌与已知的某张牌相同，则将那张牌翻开并拿走这一对牌如果不存在已知的牌与这张牌相同，则从未知的牌中再任意翻开一张如果两张牌恰巧相同，则拿走这一对牌这样，你总是重复以上的步骤直到所有的牌都被拿完当然，由于运气的好坏不同，每次拿完所有的牌所需要的论述的平均值（数学期望）究竟是多少？这里，定义每翻开两张牌（无论相同与否）为一轮输入文件】输入数据仅有一行，为两个整数 n 和 m(1≤n≤16 ，1≤m≤4)，两个数字用一个空格分开输出文件】输出在该情况下拿完所有牌需要的轮数的数学期望，结果四舍五入到小数点后 6 位小数。

输入输出样例】shinkei.in sheinkei.out2 1 2.666667【分析】我们同样来关注状态的设计从 n 入手是比较容易想到的也就是 n 维状态，每一维表示还剩几对，整个状态的值表示还需要几回合完成游戏这样空间需求为 4^16=4096MB，是不现实的m 的数据范围提示我们应当从此入手，设计一个 m 维的状态我们又会注意到每一种牌至多已知一张牌的位置（如果知道两张就可以立即翻掉了） ，那么我们设计 f(a1,a2,a3,a4,b1,b2,b3,b4).其中 ai 表示剩下 I 对的牌有几种Bi 表示 ai 这些牌中有多少种已知单牌状态转移方程有点复杂，需要考虑到多种情况：(1)翻开一张，与已知的相配代价为 1，加上后继节点 f(a1-1,a2,a3,a4,b1-1,b2,b3,b4) (或是其它 3 种)，乘上概率(2)乱翻两张，居然正好凑巧摸到了之前不知道单牌的一对，代价为 1，加上后继节点 f(a1-1,a2,a3,a4,b1,b2,b3,b4) (或是其它 3 种)，乘上概率.(3)翻开一张，增加一张单牌，再翻一张，可以与之前某张配对。

后继节点为 f(a1-1,a2,a3,a4,b1-1,b2,b3+1,b4)之类的，代价为 24)翻开两张，增加两张单牌，代价 1 转移到f(a1,a2,a3,a4,b1,b2+1,b3,b4+1)(只要 4 个 b 中间加两个 1 或是加一个2)这仅仅是四个大类，每一类分别对应一段代码，每一类中的转移都有若干种，要仔细写好概率的计算式也许有同学会怀疑：这种状态设计空间不仍然是 16^8=4096MB 吗？其实a1+a2+a3+a4≤16，所以把这四个参量压缩成一个大约需要 1~4067 的范围B1,b2,b3,b4 也如法炮制，空间需求达到了 16MB，时间复杂度约为 1E8做好四维压缩的映射表，仔细考虑好递推顺序From SHTSC 2006)聪聪和可可（cchkk）【题目叙述】【输入文件】【输出文件】【输入输出样例】【算法分析】设 dp[i,j,k]表示时间 i，猫在 j，老鼠在 k 时，猫平均还需要多少步吃掉老鼠dp[i,j,k]=∑dp[i+1,xj,ku]/(en+1)+1，其中 xj 是猫走两步（或一步）后的位置，k u 是包括 k 在内所有与 k 相连的点，en 是 k 的出度。

为了求猫的位置，预处理时作一次 ASSP（原来想的是 Dijkstra+Heap 优化，后来发现只要 BFS 就可以了）即可但时间复杂度是 O(n3)注意到在推节点的过程中，如果在某一时间猫和老鼠分别在 tc,tm，那么在以后的时间，猫和老鼠不会再在 tc,tm，否则猫永远不会捉到老鼠那么在设计状态的时候就没有必要考虑时间设 dp[i,j]表示猫在 i，老鼠在 j 时，猫平均还需要几步可以吃掉老鼠于是有：dp[i,j]=∑dp[xi,ju]/(en+1)+1 这样时间复杂度降到 O(n^2)(From NOI 2005 Day2)巧克力（From 《算法艺术与信息学竞赛》 P259）通过对这十道题目的分析，我们大概可以窥得概率类题目一二有时候，所谓概率值是一个伪装，其本质还是我们所熟悉的模型，如 终极情报网(agent) 有时候，概率的出 现考验一些数学能力，如神奇口袋，又如要用到母函数的巧克力而更多的情况下，这类问题与动态规划思想联系在一起把概率值作为一个整体进行运算，很少会用概率=发生次数 / 总次数 的做法百事世界杯之旅（PEPSI） 单 人纸牌都是其中比较基本的题目， 神经衰弱（shinkei）三国围棋 对抗赛就稍微复杂， 并行期望值迷宫统计 聪聪和可可（cchkk） 都非常经典且有难度，值得反复揣摩。

概率类问题可以很好的包装问题，也便于评测，能够将多方面知识包装成一种适于出题的形式，所以在信息学竞赛中有相当高的出现频率。