考前押题卷解题分析

1、模拟试题说明奖金（Reward）出题意图： 图论是每年分区联赛必考内容，本题是一道基础的图论题，此题重点考察选手以下几方面：根据问题建立图论模型，并应用图论知识解题对邻接表的掌握对拓扑排序算法的掌握简单递推简要解答： 首先构图，若存在条件“a的钱比b多”则从b引一条有向指向a； 然后拓扑排序，若无法完成排序则表示问题无解（存在圈）； 若可以得到完整的拓扑序列，则按序列顺序进行递推： 设fi表示第i个人能拿的最少奖金数； 首先所有fi=100（题目中给定的最小值）； 然后按照拓扑顺序考察每个点i，若存在有向边(j,i)，则表示fi必须比fj大，因此我们令fi = Max fi , fj+1 即可

2、； 递推完成之后所有fi的值也就确定了，而答案就等于f1+fn。编码（Encode）出题意图： 递推题几乎也是分区联赛的必考题，本题考察选手运用递推思想解题的能力。简要解答： 本题目的是求出M，换言之只要确定M转换成二进制后每一位是0还是1即可。 首先我们把32-bit整数二进制位从低位到高位编号为第1位到第32位； 设输入的9个整数为A1.A9，即A1=N1 Xor M，A2=N2 Xor MA9=N9 Xor M； Ai,j0或1，表示Ai转化为2进制后第j位上的数字； 之后类似做竖式加法，设FI,J表示计算N1N8的第i位到第32位的和，且第1位到第i-1位做加法进位到第i位后余下j，这

3、种情况下8个数的和是不是可能等于N9。FI,J=0或1，0表示不可能，1表示可能。 那么如何递推呢？ 显然我们需要枚举M的第i位数字是0还是1： 1、M的第i位数字是0：则N1.N9第i位上的数字分别为A1,i Xor 0，A2,i Xor 0，A9,i Xor 0，我们用B1.B9来表示；则根据竖式加法规则，必然有（B1+B2+B8+J）Mod 2 = B9，否则M第i位数字不可能为0； 若满足条件，令X=(B1+B8+J) Div 2，则X为进位到第i+1位时余下的数，此时取FI,J = Max FI,J , FI+1,X 2、M的第i位数字是1： 则N1.N9第i位上的数字分别为A1,i

4、 Xor 1，A2,i Xor 1，A9,i Xor 1，我们用B1.B9表示； 则必然有(B1+B2+B8+J) Mod 2=B9，否则M第i位不能为1； 若满足条件，令Y=(B1+B8+J) Div 2，则Y为进位到第i+1位时余下的数，此时取FI,J = Max FI,J , FI+1,Y 边界条件即F33,x1； 在求FI,J时顺便记录FI,J=1时M的第i位是0还是1，则只要求出F1,01后，便可根据记录推出M的具体数值。工作（Work）出题意图： 考察选手对动态规划的掌握简要解答： 此题是一道较简单的动态规划问题； 设Fi表示从开始时刻工作到第i时刻初（或者说是第i-1时刻末），当前空闲，目前最少工作时间是多少。 若Fi=无穷大则表示此种情况不可能；设S表示工作开始的时刻（即最早的一个工作的到达时间），则FS=0；很容易写出动态规划方程：