noip2003讲稿近年原文.ppt

[题二.侦探推理]【输出格式】如果你的程序能确定谁是罪犯，则输出他的名字；如果程序判断出不止一个人可能是罪犯，则输出CannotDetermine；如果程序判断出没有人可能成为罪犯，则输出Impossible。【输入样例】315MIKECHARLESKATEMIKE:Iamguilty.MIKE:TodayisSunday.CHARLES:MIKEisguilty．KATE:Iamguilty.KATE:Howareyou??【输出样例】MIKE[分析]经过读题可知，本题大意是有n位同学，分为两部分，一部分只说真话，另一部分只说假话，他们说了q句话而其中有一名同学是罪犯，要求我们找出这名罪犯。显然，这是一个逻辑推理的游戏。可以想到，真相存在于矛盾之中，而事实，是不可被改变的。让我们来看看样例：315MIKECHARLESKATEMIKE:Iamguilty.MIKE:TodayisSunday.CHARLES:MIKEisguilty．KATE:Iamguilty.KATE:Howareyou??法一：我注意到有一个人是在说假话的，那么我假设某一个人说的是假话，很容易得知道了凶手是Mike.但我们需注意到，法一的编程复杂度是很较高的，不易控制，再加上字符串的处理，将会占用很长的编程时间，那么是不是有更好的解决方法呢？于是，我注意到了这句话：如样例：大家注意到为什么会出现错误呢？题目中的一句话很重要：法一的时间复杂度约为：O(C(n,m){20!/(10!*10!)=184756}法二的时间复杂度约为：O(n^2){30^2=900}本体难点在于字符串的处理，有可能注意不到对空格的消除，第二个难点在于逻辑判断，要对题目进行全面的理解，比如，所有的人必须只说假话或只说真话，还有，如果不说话应当怎么办？这些都是应当仔细考虑的问题。[题三]【问题描述】设一个n个节点的二叉树tree的中序遍历为（l,2,3,…,n），其中数字1,2,3,…,n为节点编号。每个节点都有一个分数（均为正整数），记第j个节点的分数为di，tree及它的每个子树都有一个加分，任一棵子树subtree（也包含tree本身）的加分计算方法如下：subtree的左子树的加分×subtree的右子树的加分＋subtree的根的分数若某个子树为空，规定其加分为1，叶子的加分就是叶节点本身的分数。不考虑它的空子树。试求一棵符合中序遍历为（1,2,3,…,n）且加分最高的二叉树tree。要求输出；（1）tree的最高加分（2）tree的前序遍历?【输入格式】第1行：一个整数n（n＜30），为节点个数。第2行：n个用空格隔开的整数，为每个节点的分数（分数＜100）。?【输出格式】第1行：一个整数，为最高加分（结果不会超过4,000,000,000）。第2行：n个用空格隔开的整数，为该树的前序遍历。?【输入样例】5571210?【输出样例】14531245ABC我们对样例进行分析：中根遍历：1(5)2(7)3(1)4(2)5(10){节点编号(本点原分数)}前根遍历：31245根据前面对样历的分析，我们可以注意到在中根遍历中，一个节点的左子树与右子树分别分布于节点的两侧。树是一种具有子结构的存储结构，用f(i,j)表示从第i个节点到第j个节点的最大加分二叉树，则dp方程为：F(i,j)=max{f(i,i)+f(i+1,j),f(i+1,i+1)+f(I,i)*f(I+2,j),f(I+2,I+2)+f(I,I+1)*f(I+3,j),……,f(j-1,j-1)+f(I,j-2)*f(j,j),f(j,j)+f(I,j-1)};f(1,3)=max{5+8,7+5*1,12+1};f(2,4)=max{7+4,1+2*7,8+2}f(3,5)=max{1+12,2+1*10,3+10}本题要求输出先根遍历的结果，故在进行动态规划的过程中，需要记录根节点，并进行先根遍历，输出结果即可。本体考察的是动态规划算法与树的遍历，如果不采取正确的算法，是很难完美的解决问题的，所以，在解决其它问题时，应当正确的选取算法。[题四]传染病控制【问题背景】近来，一种新的传染病肆虐全球。蓬莱国也发现了零星感染者，为防止该病在蓬莱国大范围流行，该国政府决定不惜一切代价控制传染病的蔓延。不幸的是，由于人们尚