Problem
每個六角形會有 1 ~ 6 的數字在每一條邊,可以旋轉六角形,但是相鄰的數字要相同。
請問是否可以拼出目標的形狀。
Sample Input
|
|
Sample Output
|
|
Solution
決定好中心,中心不需要旋轉,接著考慮外面繞一圈的接法。窮舉一下即可。
|
|
每個六角形會有 1 ~ 6 的數字在每一條邊,可以旋轉六角形,但是相鄰的數字要相同。
請問是否可以拼出目標的形狀。
|
|
|
|
決定好中心,中心不需要旋轉,接著考慮外面繞一圈的接法。窮舉一下即可。
|
|
first cousin :如果兩個字串可以藉由移除不多於一半的字符,可以變成相同的字串。
ex. abcdef
、axcyd
分別移除 (b, e, f)
、(x, y)
,就可以變成 acd
。
然而如果它們 string (A, B)要稱為 (n+1)th cousin
,則存在一個媒介 C,A 和 C 是 first cousin
以及 B 和 C 是 nth cousin
。
|
|
|
|
這題看題看得很痛苦,也就是說找兩個字串最短的關係 (請無視長的)。
然而要如何找到最短的,思考一下絕對跟 LCS 有點關係,想了一整個早上仍然沒有結果,後來看了大神代碼回溯想法:
|
|
仔細想想,這解法類似於貪心?而 LCS 存在的關係是起手用。增倍貪心,把不需要的地方直接填跟目標的內容。
|
|
A 要追 B,結果 B 偽裝成 C,B 告訴 A,B 將會怎麼走並且沿路指導 A 該怎麼走,然而真正的 C 也會在地圖中某一個地方開始移動。
如果 A、C 相遇,則會發現 B 是偽裝的,給予兩個人的路線,請問 B 是否能安全抵達目的地,如果再目的地被抓到也相當於安全抵達,因為他已經抵達目的地。
假設 A、C 的移動速度相同。
|
|
|
|
這一題與 11796 - Dog Distance 很類似。找兩個路線的最接近距離。
- 题目大意:
两条狗匀速分别沿着折线跑,已知同时出发,同时到达,问你求相差最大的距离 与相差的最小的距离之间的差值。- 解题思路:
如果两只狗都走1条线段的话,根据相对运动的理论,可以把其中一只狗看成静止不动,另一只狗相对运动,且线路为线段,那么立刻转化为点到线段的距离的问题。
而這一題檢查最近距離是否為 0 即可。特別 case 終點碰到的情況,此外測資中兩個路線的距離長貌似相同,因為討論區的有幾組不同長的測資,雖然以下代碼沒有通過,但是還是 AC。
|
|
給一個簡單多邊形,接著詢問許多通過兩點的直線,與多邊形的交集長度為何?
|
|
|
|
一開始以為是線段與簡單多邊形,後來才發現不太對勁,原來是直線與簡單多邊形。
事實上也很簡單,直接拿所有多邊形的線段進行嘗試,算出所有交點後,將其放置於直線上,會看得出很多線段,檢查線段中點是否在多邊形內部,如果是則將該線段的長度納於交集。
如果該線段位於簡單多邊形內,則保證其線段中點也一定在。
這一題鬼畜的地方在於測資的精準度,因為在多邊形邊界上也要算交集,死活地卡不過去,最後下了測資,看下才發現是多邊形端點是否在直線上,那裏必須特別判斷,靠很近就可以將其算為交點。
|
|
檢查生的測資是否符合規格,規則共有七條,分別告知每一條是否符合規格。
|
|
|
|
附上討論區的噁心測資
|
|
很明顯地方發現,居然有空字串 …,用空白切割檢查一下參數個數是否正確。
|
|
給一個用 ASCII Area 拉出來的簡單多邊形,求其面積為何?
|
|
|
|
看別人的代碼相當簡單,只是有點不知道它們怎麼構思的。
首先,保證每一個端點都是格子點,靈機一動想到 Pick’s theorem,$A = i + b/2 - 1$,那麼接著就是找到 i 的個數 (內部存在的整數節點個數),b 個數 (邊上的整數節點個數)。
b 很好求得,相當於 \
和 /
的個數而已,然而 i 求法會比較特別一點,思路類似於掃描線的方式,性質則是利用射線法 (一個點拉一個射線無限延伸,如果該點在簡單多邊形內,則會穿過奇數個點。)。
如果是凸多邊形,也許就能用行列式求值。
|
|
給定 N 個字串 (N 為偶數),現在來了一個人,將其命名名字,其名字長度越小越好,同時必須按照字典順序時,必須大於等於前 N/2 個人,大於 N/2 個人。
在相同的最短長度下,輸出一個字典順序最小的。
|
|
|
|
先對輸入的字串排序,找到相鄰的兩個中位數字串 p, q (p < q)。
接著分開討論。
p.length() < q.length()
:要不前綴相同,或者是比 p 大一點,當前綴都相同時跟 p 相同。p.length() >= q.length()
:一樣貪心處理前綴,特別小心 ‘Z’ 的存在,這種情況將會逼不得已將長度增加,而其他狀況只要想辦法增加字典順序的大小即可。
|
|
現在有 N 個國家在一棟建築物裡面各自擁有辦公室,辦公室相鄰的定義為同一樓層的前後左右,或者是上一樓層的同一位置、下一樓層的同一位置。
由於各方想要藉由一面牆或者是天花板進行秘密會議。因此希望每一個國家的辦公室可以跟其他所有辦公室相鄰。
輸出其中一組解即可。
|
|
|
|
直接建造兩層,參照如上圖的建造方式,交錯的形式能保證可以在 O(2 n^2)
個數內完成建築物。
|
|
機器人能轉移只有上下左右四個方向,機器人切換快速移動模式,將自己跨過小於等於 K 個連續的障礙物。也就是說,當障礙物連續出現形成一座厚牆時,機器人就爬不過去。
求最少移動次數。
|
|
|
|
將每一點多一個狀態 s,表示當前經過連續 s 個障礙物。如果下一個轉移地點不是障礙物,則 s 會歸零。
|
|
俄羅斯套娃遊戲,每一次只能將相鄰的兩個套娃合併。合併時,打開套娃的次數相當於操作成本,請問至少要打開的次數為何,使得最後的數個套娃可以收成連續大小 1 ~ n
。
一開始給定每個套娃內部都沒有別的套娃。
從第二組測資中,可以看出必須整理成 [1 2 3][1 2 3 4]
兩組完整的套娃。要把 [2][4]
合併成 [2 4]
要打開大小為 4 的套娃,並且把大小為 2 的套娃裝進去。同理,[1][3]
合併成 [1 3]
也需要打開一次。最後合併 [2 4][1 3]
成 [1 2 3 4]
其中必須將 4 打開 (看到 2),再把 2 打開,把 3 打開,接著把 1 裝進 2,把 2 裝進 3,最後裝進 4 中。
此時已經花費成本 5 次 (打開次數),而要把 [1][2][3]
合併成 [1 2 3]
需要打開 2、打開 3 才能完成。共計成本 7 次。
|
|
|
|
類似矩陣鏈乘積 DP,但是這一題必須使用兩次 DP。
dp[l, r]
找到序列 [l, r]
之間合併成一個套娃的花費。-O(n^3)
A[l, r]
之間是否是一個 complete set,也就是一個完整的套娃 (連續大小)。-O(n^3)
這裡應該還可以更快,不過步驟 1 應該很慢,所以沒有必要。O(n^2)
|
|