程序设计与实践第一次题目

• T1 达拉崩吧的酒宴
• Description
• 思路
• T2 A+B (I)
• Description
• 思路
• T3 解谜游戏
• Description
• 思路
• T4 北湖挖坑
• Description
• 思路
• T5 北湖填坑
• Description
• 思路
• 鸣谢

T1 达拉崩吧的酒宴

Description

很久很久以前，巨龙突然出现，带来灾难带走了公主又消失不见，王国十分危险，世间谁最勇敢，一位勇者赶来大声喊：“我要带上最好的剑，翻过最高的山，闯进最深的森林，把公主带回到面前”……最后，英雄 达拉崩巴斑得贝迪卜多比鲁翁 ，他战胜了巨龙 昆图库塔卡提考特苏瓦西拉松 ，国王把公主 米娅莫拉苏娜丹妮谢莉红 嫁给了 达拉崩巴斑得贝迪卜多比鲁翁 。

于是国王第二天要在 蒙达鲁克硫斯伯古比奇巴勒城 举办酒宴，一共准备了 N 桶酒。此时一位忠诚的仆人来报，有人在其中一桶酒里下毒，并且此毒要经过24小时后才会毒发身亡。现在距离晚会酒宴开始还有正好24小时，为在酒宴开始前找出哪一桶酒有毒，国王决定找一些小白鼠来试酒。（仆人不可能说谎，即一定有且只有一桶酒有毒）

聪明的 达拉崩巴斑得贝迪卜多比鲁翁 本着善良的天性，决定用尽量少的小白鼠来试酒。

请问最少需要多少只小白鼠试酒？

思路

设一共有M只小白鼠，那么一共可以测出
C M 0 C_M^0 CM0​+ C M 1 C_M^1 CM1​+ C M 2 C_M^2 CM2​+…+ C M M C_M^M CMM​ = 2 M 2^M 2M
瓶酒是否有毒。
即对应0只，1只…M只小白鼠死掉。
所以只需要去测给出的N桶酒处在在2的几次方和几+1次方之间即可。
即 2 R e s < N ≤ 2 R e s + 1 2^{Res}<N\le2^{Res+1} 2Res<N≤2Res+1。

T2 A+B (I)

Description

   11101
+    110
--------
  100011

请你模拟这个过程。

思路

此题和高精度加法类似，一开始我还想着能不能二进制转十进制然后相加，最后十进制转二进制，但是好像不太行。
其实直接高精度进位就完事
注意格式问题，最后输出是结果前面空两个格

T3 解谜游戏

Description

基本同 POJ1222
只不过原题是一个固定的大小，本题是16*16以内的随意大小。
以及原题是要输出一个具体哪个按了哪个没按的矩阵，本题需要输出一共按下的次数的最小值。

思路

我们去枚举第一行一共按了哪些灯，因为只要第一行的灯被按下过，那么第一行剩下来的亮着的灯就只能被第二行所按灭，这样一行一行传递下去，最后检测最后一行是否全是灭的就彳亍 。
总共所需要枚举的次数是 2 长 度 2^{长度} 2长度，对应第一行的第X位有没有被按下

T4 北湖挖坑

Description

十一年前，北湖曾经是一片平整的土地，北湖的施工队打算将其挖出深坑，注水造出人工湖。

为了简化运算，我们假设北湖的地面是一维的，每一块宽度都为1，高度是非负整数，那么可以用一个数组来表达一块地面。

一开始北湖是一片平地，每一块的高度为 h 。下图是 h=3 的情况，用数组表示为[3,3,3,3,3,3,3,3,3,3,3,3]。

施工队根据图纸想将其挖成凹凸不平的形状，如下图所示，数组表示为[0,1,0,2,1,0,1,3,2,1,2,1].

施工队有一台挖土机，每一天挖土机可以将连续一段区间挖掉一格土。包工头小张想尽快完成任务，请你告诉他将平整的土地挖成图纸所示的情况最少需要多少天？

思路

这个题一开始我的想法是一层层地去找，然后找到连续的，不连续的+1，最后输出结果。但是4 5 6 7全部TLE，迫不得已改方法。
先把整个地图倒过来，即用高度h-每一块的高度，然后从左往右遍历，先加上第一块的全部高度，因为3层最少要挖3次，然后只要后面的比前面低那就无所谓，继续遍历，直到后一块比前一块高，这样需要加上高度差，然后从后一块开始继续遍历。
一定要使用long long不然会错

T5 北湖填坑

Description

十年前，北湖还只是一个深坑，未完成蓄水工作。为了确保蓄水工作的顺利进行，我们需要对北湖的蓄水量进行粗略估计。

为了简化运算，我们假设北湖的地面是一维的，每一块宽度都为1，高度是非负整数，那么可以用一个数组来表达一块地面。

这题跟OpenJudge4074基本一样。

思路

同样，这个题我一开始的想法还是一层层地去找，但是2 3全部TLE。
实际上，这个题只需要分成两半，在第一次遍历（输入）的时候找到最大值，然后分成从开头到最大值和从末尾到最大值两段分别计算。
计算的方法跟T4相近，只不过不用先用高度h-每一块的高度，直接读取就好。
以从开头到最大值位置举例：
先初始化局部最大值位置 = 开头
如果后一位比前一位低那就要加上高度差，如果后一位比前一位高，那必然不会积水，但是要把局部最大值位置换成当前这一位的位置。

鸣谢