程式設計與實踐第一次題目
- T1 達拉崩吧的酒宴
- Description
- 思路
- T2 A+B (I)
- Description
- 思路
- T3 解謎游戲
- Description
- 思路
- T4 北湖挖坑
- Description
- 思路
- T5 北湖填坑
- Description
- 思路
- 鳴謝
T1 達拉崩吧的酒宴
Description
很久很久以前，巨龍突然出現，帶來災難帶走了公主又消失不見，王國十分危險，世間誰最勇敢，一位勇者趕來大聲喊：“我要帶上最好的劍，翻過最高的山，闖進最深的森林，把公主帶回到面前”……最后，英雄 達拉崩巴斑得貝迪卜多比魯翁 ，他戰勝了巨龍 昆圖庫塔卡提考特蘇瓦西拉松 ，國王把公主 米婭莫拉蘇娜丹妮謝莉紅 嫁給了 達拉崩巴斑得貝迪卜多比魯翁 ，
于是國王第二天要在 蒙達魯克硫斯伯古比奇巴勒城 舉辦酒宴，一共準備了 N 桶酒，此時一位忠誠的仆人來報，有人在其中一桶酒里下毒，并且此毒要經過24小時后才會毒發身亡，現在距離晚會酒宴開始還有正好24小時，為在酒宴開始前找出哪一桶酒有毒，國王決定找一些小白鼠來試酒，（仆人不可能說謊，即一定有且只有一桶酒有毒）
聰明的 達拉崩巴斑得貝迪卜多比魯翁 本著善良的天性，決定用盡量少的小白鼠來試酒，
請問最少需要多少只小白鼠試酒？
思路
設一共有M只小白鼠，那么一共可以測出
+++…+ =
瓶酒是否有毒，
即對應0只，1只…M只小白鼠死掉，
所以只需要去測給出的N桶酒處在在2的幾次方和幾+1次方之間即可，
即，
T2 A+B (I)
Description
11101
+ 110
--------
100011
請你模擬這個程序，
思路
此題和高精度加法類似，一開始我還想著能不能二進制轉十進制然后相加，最后十進制轉二進制，但是好像不太行，
其實直接高精度進位就完事
注意格式問題，最后輸出是結果前面空兩個格
T3 解謎游戲
Description
基本同 POJ1222
只不過原題是一個固定的大小，本題是16*16以內的隨意大小，
以及原題是要輸出一個具體哪個按了哪個沒按的矩陣，本題需要輸出一共按下的次數的最小值，
思路
我們去列舉第一行一共按了哪些燈，因為只要第一行的燈被按下過，那么第一行剩下來的亮著的燈就只能被第二行所按滅，這樣一行一行傳遞下去，最后檢測最后一行是否全是滅的就彳亍 ，
總共所需要列舉的次數是，對應第一行的第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-每一塊的高度，直接讀取就好，
以從開頭到最大值位置舉例：
先初始化區域最大值位置 = 開頭
如果后一位比前一位低那就要加上高度差，如果后一位比前一位高，那必然不會積水，但是要把區域最大值位置換成當前這一位的位置，
鳴謝
| QWQ感謝DF和LHL兩位大佬的支持QWQ |
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/4424.html
標籤：其他