北郵

北郵2014年

PRoblem A. 分數加法

題目描述 求2-a+2-b，其中a和b均為正整數，結果請用最簡分數表示。 輸入格式 第一行為測試數據的組數T（1<=T<=400）。請注意，任意兩組測試數據之間是相互獨立的。 每組測試數據一行，包含兩個整數a和b（2<=a,b<=20）。 輸出格式 對于每組測試數據，在一行內輸出結果，分子和分母用“/”隔開。 輸入樣例 2 2 4 3 2 輸出樣例 5/16 3/8

比較a,b大小，結合pow函數即可

Problem B. 最小堆

題目描述 給定一棵帶權二叉樹，請判斷它是不是一個最小堆。 一棵二叉樹是一個最小堆，當且僅當對于樹上任意一個節點，它的權值都小于或等于以它為根的子樹中的所有權值。 輸入格式 輸入數據第一行是一個整數T（1<=T<=100），表示測試數據的組數。 對于每組測試數據： 第一行是一個整數N（1<=N<=100），表示樹的節點個數。 接下來一行包含N個正整數，第i個整數valuei(1<=valuei<=1000)表示編號i的點的權值。 接下來N-1行，每行兩個整數u和v（1<=u，v<=N, u!=v），表示節點u是節點v的父節點。 測試數據保證給定的一定是一棵二叉樹，并且節點1是樹的根結點。 輸出格式 對于每組測試數據，如果給定的樹是一個最小堆則輸出Yes，否則輸出No。 輸入樣例 3 1 10 3 10 5 3 1 2 1 3 5 1 2 3 4 5 1 3 1 2 2 4 2 5 輸出樣例 Yes No Yes

構造二叉樹，遞歸檢查

Problem C. 進程管理

題目描述 在操作系統中，進程管理是非常重要的工作，每個進程都有唯一的進程標識（PID）。每個進程都可以啟動子進程，此時我們稱它為其子進程的父進程，除了PID為0的進程之外，每個進程有且只有一個父進程，在這個任務中，你需要實時維護操作系統運行中的三個基本操作： 1.FORK PID1 PID2：標識為PID1的進程啟動了一個標識為PID2的子進程。 2.KILL PID：結束標識為PID的進程。請注意，與此同時所有PID的子進程也將同時結束。如果PID是不存在或已經結束的進程，則不做任何操作。 3.QUERY PID：查詢標識為PID的進程是否仍然存在。 在初始狀態下，系統只開啟了PID為0的進程，并且在任何情況下該進程不會結束。 輸入格式 輸入的第一行是一個整數T（T<=50），表示輸入的數據組數。 每組測試數據的第一行是一個整數N（1<=N<=100），表示操作的數量。 沒下來N行，每行按照上面的描述給出每個操作，輸入保證所有的進程的PID都不相同，且一個進程結束后不會被重新啟動，所有PID都是[1,100]之間的整數。 輸出格式 5 FORK 0 1 QUERY 1 KILL 1 QUERY 1 QUERY 2 輸出樣例 Yes No No Yes

構建樹的結構

Problem D. 網絡傳輸

題目描述 網絡的高效互聯與智能傳輸是提升海量用戶服務請求映射效率的重要措施。在這個任務中，你要用最少的傳輸時間，將特定的數據源發送到指定的網絡節點中。 我么給定的網絡一共包含N個節點（從1到N編號），其中節點1為數據源。網絡中有M條無向邊（u,v,w），表示一條傳輸線連接節點u和節點v，且數據通過這條傳輸線的平均時間為w。由于傳送機制的限制，當一個節點接收到數據之后，它只能選擇與它互連的一個節點，并將數據轉發到該節點。節點1在初始化時只會發送一次數據，但在傳輸過程中它可以作為轉發節點。 網絡中有k個目標節點，你需要計算出該數據從節點1傳送到所有K歌節點所需要的最短時間。注意目標節點可以按任意順序進行傳送，數據也可以多次經過同一節點。 輸入格式 輸入數據第一行是一個整數T（T<=5），表示測試數據的組數。 對于每組測試數據： 第一行是三個正整數N,M,K（2<=N<=1000，1<=M<=N(N-1)/2，K<=10），分別表示節點數，邊數和目標節點數。 接下來M行，每行三個整數u,v,w（1<=u,v<=N, 0<=w<=1000,u!=v）。如上所述給出每條傳輸線。任意兩個網絡節點之間最多只會有一條邊相連。 最后一行是K個整數，給出所有的目標節點的編號，所有目標節點的編號都在2到N之間。 輸出格式 對于每組測試數據，輸出數據傳送到所有K個目標節點的最短時間。 樣例輸入 2 3 2 2 1 3 1 1 2 3 2 3 6 6 4 1 5 1 5 6 2 2 1 20 2 3 5 3 4 5 6 3 1 2 3 4 6 樣例輸出 5 19 樣例說明 在第一組樣例中，最短路線是：1->3->1->2 在第二組樣例中，最短路線是：1->5->6->3->2->3->4，或者1->5->6->3->4->3->2