NPSC補完計劃

登入註冊帳號.

請輸入帳號, 密碼以及預計登入時間
進階搜尋  

最新消息:

歡迎光臨NPSC補完計劃

+ NPSC補完計劃 » NPSC高中組 » NPSC2019高中組決賽
 轉發 FB 現場題解概要

作者 主題: 轉發 FB 現場題解概要  (閱讀 117 次)

lose

  • 新手
  • *
  • 文章數: 14
    • 檢視個人資料
轉發 FB 現場題解概要
« 於: 十二月 08, 2019, 07:00:08 pm »

原文網址: https://www.facebook.com/permalink.php?story_fbid=431563037518690&id=338441636830831

引用
NPSC題解
先講下,我是拉基我只有一題,寫這題解是聽裁判寫出來的,只是因為想找去年題解找不到覺得很不爽,才幫別人紀錄一下,拜託電神別嘴,等等邊聽邊更新。

pA 逆序輸出
題:給一正整數及24格儲存整數的格子,構造一指令印出從N ~ 0的數字,指令有將任意格複製到另一格,任一格 +1,輸出第x格,要求兩次輸出中不得超過15個指令。
使用log2(N)個格子,分別儲存lowbit為(1 << i)(i <= log2(N))的值,每次取小於且最接近需要的值的格子複製過來,在暴力加到需要的值,證明感覺很麻煩,不過應該可以感覺的到,每次操作都不會太多。

pB 忙碌的國度
題:一二維座標平面存在兩種點,一種代表公司並包含該公司下班時間,另一種代表餐廳並包含打烊時間及美味程度。問對於每一間公司,可以在下班後並在打烊前到達的餐廳的美味程度最大值為和?
formula : (Off work time + abs(x2 - x1) + abs(y2 - y1) <= Closure)
這題留言裡有超級電神的解釋,去膜拜吧。

pC 最小三倍完全數
題:求最小N倍完全數(N >= 1 && N <= 5)
這題我坐在那思考著自己跟垃圾有什麼差別時聽到了許多的解法,評審的解法也感覺很酷,但是,\爆搜!!/。

pD 回文樹
題:給一字串,將其排成字典序最小的回文字串。
引用評審的一句話:就排阿。

pE 密碼鎖
題:給N, K,及一N數字排列,問有幾種排列在移動K次後會剛好等於該排列。
首先應該很快的可以想到,不管排列長什麼樣子,結果都一樣,也就是答案只跟N, K有關,再來好像可以位元DP,這題我聽題解時在恍神,所以還要再推一下,之後更新。

pF 猜數字
題:互動題,給k個數字n,做最少次詢問得到每一個數字,每次詢問回傳是否大於詢問。
首先定義一函數F(N, K) 表示K個數字N大小區間的最佳詢問,就這樣去做分治。
這題其實我也沒有搞很懂為甚麼是那一坨東西,坐等電神解釋。
那一坨東西:F(N, K) = ( (N - 1) mod 2 * ceil( log2 ( (N - 1) / 2K + 1 ) ) ) + 1
我不會打很酷的數學符號QQ

pG 航線建設
題:給N, Q代表對於N個節點的圖有K次操作,每次操作可以加上一條邊或刪除一條邊,對於每次操作輸出當前MST的直徑,若不連通則輸出-1。
這題評審講了兩個解法,不過第一個解法我完全聽不懂,所以就講第二種。
記得沒錯的話就是很簡單的暴力,每次操作就用並查及維護及確認是否連通,做出最小生成樹,並找直徑。應該沒有這麼簡單拉,不過我有點忘了。

pH 鐵路維修問題
題 : 給N個節點及N - 1條邊,求任兩點間距離乘上路上最大邊權的和。

這題評審給了3個做法,第二個我不是很會用treap,第三個我直接問號
,所以就講第一個就好。

首先要先想辦法用O(n)的時間求出每一個點到任意點的邊數,方便後續查詢。可以先從任意點開始DFS,使用簡易dp求出對於每個節點的所有子節點到該節點的邊數和。接下來再做一次DFS,這時我們已經有了每個節點的下面的邊數和,所以就剩下上面的。而上面的我們可以再用祖先的狀態推過來,對於每個節點,他上面的邊數和會是祖先除了自己以外所有的邊數和加上祖先自己上面的邊數和,這樣就可以求出對於任意點的邊數和了。

再來整題就變簡單了。因為是乘上最大的邊,所以我們可以對於所有的邊,去算出以這條邊為最大的邊的答案。直接依照邊權去由小排到大,當增到第i個邊權時,代表目前圖中最大的邊權就會是i這條邊,所以就用目前的圖去算出答案,一直到把全部的邊都加進去。

最近粉專突然被一堆電神看到,有點緊張。感覺內容有超級多的錯誤,如果電神們看到有問題,請不要吝嗇直接辱罵並糾正我吧。
記錄
+ NPSC補完計劃 » NPSC高中組 » NPSC2019高中組決賽
 轉發 FB 現場題解概要