算法艺术与信息学竞赛习题部分提示

算法艺术与信息学竞赛习题部分提示

部分习题提示

1.1节习题

1.1.1

对；不对

1.1.2

提示：考虑规模增长时的时间开销，可以对比运行时间，也可以在程序中统计基本操作数目

1.2节习题

1.2.1

不一定。这要看枚举量和枚举时间

1.2.3

枚举即可。需要注意的是要保证每个问题只有一个正确答案而不是有个答案。本题有唯一解cdebeedcba。

1.2.5

注意行有很多但是列不太多。硬币翻两次等于不翻，所以所有行/列最多翻一次。枚举每列是否翻有2^9=512种情况，此时可以用O(n)的时间计算每行是否翻（注意：列确定以后每行独立）。

1.2.6

只需要枚举横坐标相邻的点

1.2.7

设S1的长度为n。注意用串匹配来做的话时间复杂度至少为O(10^n)，不是有效算法。应该枚举S1的“分段方式”。例如231241，如果分段方式为23|124|1，则124为完整的一段，前面必为123，后面必为125，经检验这是可行的。因此如果有一个完整段的情况可以用O(n^2)次枚举来判定。剩下只需要解决没有完整段的情况，即被分成两段。如2312，如果被分为2|312，则需要枚举位数。如果是3位，有方程??2 + 1 = 312，无解；如果是4位，有方程???2 + 1 = 312?，有解3122 + 1 = 3123。基本思想如此，但是需要注意有进位的情况。建议读者自己写程序并提交到ural在线题库检查自己的程序是否考虑周全。

1.2.12

首先可以证明：覆盖整个草坪当且仅当覆盖草坪的上边界。这样每个圆的作用范围是一条线段，问题转化为用最少的线段覆盖整个区间。先预处理再贪心，具体方法留给读者思考。

1.2.14

本题较难，需要先推出n=4时的两种可能最优策略（用代数方法容易推导出），然后用递归的思想把n>4的情况转化为n<=4的情况加以解决。提示：考虑四人速度为1,3,4,5和1,2,5,6的情况，最优时间分别为16和13。

1.2.17

本题答案不唯一。例如：解方程组。

1.2.23

枚举去掉的数字位置后，几乎就可以直接解方程了（需要分类讨论和少量附加枚举）。具体方式留给读者思考

1.2.24

把袋子编号为0,1,2...n-1，如果没有1717克的限制，就是第0,1,2...n-1个袋子依次取豌豆0,1,2...n-1颗，把称得的重量和0+1+2+...+(n-1)比较，重了几克就是第几个袋子是魔法豌豆！可是现在有总重量限制，因此

算法艺术与信息学竞赛习题部分提示

只有当0+1+2+...+n-1<=1717时才能一次称出。记M(1)为能保证一次称出的最大n值，则解不等式得n<=59。二次称可以用以下策略：59个袋子为一组，第0组不取，第1组每个取1颗，第2组每个取2颗...只要总重量<=1717，则多了几克就是第几组的。由于每组只有59个，所以再称一次就可以了。解不等式可以求出保证二次称出的最大n，记为M(2)。这样递推出M(10)发现M(10)>10000，因此用我们刚才的策略就可以在10次内称出了。 1.2.27

如果某张纸上只有一个程序，则可以在其他顺序恢复后再单独把它插入；如果某张纸上有至少三个程序，则除了头尾之外的中间程序都只会出现一次，也可以最后处理，因此只需要保留恰好有两个程序的纸张。剩下的工作就不难了，留给读者思考。

1.3节习题

1.3.6

自上而下的读取各行，可以用本节介绍的floodfill方法来作，但是更节省空间的方法是1.4节介绍的并查集。需要注意的是要正确的处理新块开始、旧块结束、不同块合并、相同块再次合并（形成“洞”）等几种情况。

1.3.7

下确界可以简单的通过求轮廓线的并来实现。交就没有这么简单了，因为在求轮廓线交以后可能形成非矩形的区域，即出现“凹角”。先作一次floodfill后删除有三侧属于同一个区域的角，直到不存在这样的角。

1.3.24

设电路对应的函数是f(i)，其中i是一个n进制数，n为输入个数。如果f(000..0)=f(111..1)，则所有x设置为0即可。否则考虑序列：000..000,000..001,000..011,000...111, ... 011..1, 111..1，每相邻两项只相差一个字符。显然一定存在相邻两项的f值不同，不同的字符保留为x，其他设置为相同值即可。可以二分查找，总时间复杂度为O(mlogn)，m为门的数目。

1.4节习题

1.4.1

先作标记，等到浪费空间大于一半时重构树。可以证明均摊时间复杂度不变。另外还有保持每个操作最坏情况时间复杂度不变的算法，非常巧妙。

1.4.7

设s[0]=0，s[i]=a[1]+a[2]+...+a[i]，则信息i j even等价于a[i]+...+a[j]为偶数，即s[j]-s[i-1]为偶数，即s[j]与s[i-1]同奇偶。这样，每条信息都可以变为某两个s[i]和s[j]是否同奇偶的信息。记same[i]为当前和s[i]同奇偶的s[j]集合，diff[i]为当前和s[i]不同奇偶的s[j]集合，则一条信息i j even将导致same[j]和same[i-1]合并，diff[j]和diff[i-1]合并；信息i j odd将导致same[j]和diff[i-1]合并；diff[j]和same[i-1]合并。具体细节留给读者思考。

1.4.12

和标准的Young Tableau查找算法很类似，稍微修改一下即可。

1.4.16

先按照x坐标排序，然后建立一棵静态的BST用于统计。需要记录附加信息。建议读者写写程序，要写得尽量简单，很少几行即可写完。

1.5节习题

算法艺术与信息学竞赛习题部分提示

1.5.8

先作减法，把两个权变成一个。可以进一步发现如果矩形有重叠，可以把重叠部分去掉和权和保持不变。这样问题变成了即找出k个不重叠的矩形使得权和最大。们用区域(i,j)来表示在矩阵W中的“第一行第i个格子右边所有元素加上第二行第j个格子右边的所有元素”这个区域，用d[s,i,j]来表示在这个区域中选择s个子矩阵，它们的元素总和的最小值。看作多阶段决策问题，则决策有五种：决策一：第一行第i个格子不用的情况，这种决策转移到状态d[s,i+1,j]；决策二：第二行第j个格子不用的情况，这种决策转移到状态d[s,i,j+1]；决策三：第一行从第i个格子放一个矩形，则大小L有O(n)种选择；转移到d[s,i+L,j]决策四：第二行从第j个格子放一个矩形，则大小L有O(n)种选择；转移到d[s,i,j+L]决策五：两行一起放宽度为2的矩形，也有O(n)种选择。

1.5.10

如果是求利益最大的方案，显然可以定义状态d[i]为考虑前i个订单并接受订单i的最大利润。但是第k的方案呢？这种状态表示是不行的。它的一个重要问题在于：问题不具备最优子结构！第k大方案所对应的决策的子决策不一定是第k大的。无奈之下，我们只好增加一维状态参量，用d[i,j]表示考虑前i个订单并介绍订单i的第j大利润，而状态转移时也必须考虑所有前趋状态各自的第1,2,3…j大利润（想一想，为什么不考虑第j+1,j+2…k大利润？），然后加以比较。需要注意的是可以利用堆来降低时间复杂度，请读者思考。

1.5.11

注意到命令序列长度不超过50，机器人不可能走得太远。所以可以先枚举终止位置，然后单独考虑每个机器人，让每个机器人删除的指令数都最少。用d[x,y,i]表示要让前i条指令被执行（或被删除）后机器人处于位置(x,y)所需要删除的最少指令数，请读者列出状态转移方程。

1.5.12

首先，我们直观的猜测：任意一副筷子中A和B一定是长度相邻的两只筷子。证明如下：对于某副筷子(A1,B1,C1)和另一副筷子(A2,B2,C2)，如果A1<=A2<=B1<=B2，那么交换一下筷子重新组合成(A1,A2,C1)和(B1,B2,C2)质量和会更优。对于某副筷子(A,B,C)和闲置的筷子D，如果A<=D<=B，那么交换一下 …… 此处隐藏：3096字，全部文档内容请下载后查看。喜欢就下载吧 ……