by wangzhihao

分類: 幾何,中等

題目大意:給你兩個三維凸包,如何放置使得他們的質心相距最近?(每個凸包只給你它的頂點,無序),求最近距離

思路:肯定是把兩個凸包的兩個面疊在一起,這樣就轉化成單獨求質心到凸包每一面所在的平面的距離,然后再相加即可.

接下來主要問題是求質心位置. 我們可以隨便取一個頂點,以它基點把凸包剖分成若干個四面體,分別求每個四面體的重心,然后加權的加起來即可.

分類: 數學,簡單

題目大意:有n座電梯,你只能從中選擇一輛乘,中途不能換乘,每一座電梯只有兩個鍵,要么上a層樓,要么下b層樓,假設樓無限高,電梯不能低于0樓,你最開始在0樓,你連續按n次,最低會在第幾樓?

思路:理解上直接用實數解 x * a + y * b = 0 && x + y = n; 然后把x取上整即可.實際做的時候可以用取模避免使用實數

分類: 數學,偏難

題目大意:這是一個交互題, 告訴你有一個1-n的排列(n < 200),但你不知道這個排列的樣子,你可以詢問第i , j, k位的中值是誰, 最多詢問2000次,給出那個不知道的排列, 有些排列是通過這種詢問不可能區分的, 這種情況下輸出任何一個都可以.

思路:這道題的解法很巧妙,貌似交互題的解法都很妙.

首先如果我知道1的位置,那么我可以很快確定其他數的位置.假設現在有三個數的位置為x, y, z. 分別ask(1, x, y) ask(1, y, z) ask(1, x, z)這樣必定有且只有兩個ask是一樣的值, 而且這個值的位置就是公共的那個位置,這樣問3次就可以確定一個數.

上面只是舉了個例子, 實際上對于一個排列,知道了最小值,或者最大值,都可以用上面的方法快速的確定其他的值.

當然直接找1或者n的位置比較困難,可以隨便找一對a,b.不妨設 a < b, 對所有的x去ask(x, a, b), 這樣對于(a< x < b)直接一次詢問就可以確定了 ,對于(x<=a)詢問會返回a, 對于(x >= b)會返回 b. 然后分別處理兩端即可

分類: Hash,簡單

題目大意:給你一個n*m的表,(1 <= n <= 10 000, 1 <= m <=10),問是否有兩行他們滿足下面條件: 他們中有兩列相同.

思路:枚舉列,然后hash判重

分類: 集合DP,偏難

題目大意:每種進程需要兩種資源, 一共有最多15種資源. 但是為了避免沖突,使用某種資源前要申請,使用時要加鎖.這樣又有可能會造成死鎖, 改變進程對自己的兩種資源的申請順序,使得不會發生死鎖,且等待鏈最長的最短.

思路:

分類: 優先隊列,簡單

題目大意:給你一個字典,字典里有m個單詞, m <1000. 你需要再找n個單詞,這n個單詞要求能夠盡量多的能從字典里派生.單詞a能從單詞b中派生意味著a是b刪掉若干字母(也可不刪),再按一定排列形成的.

思路:用一個優先隊列去不斷的生成答案,開始是一個空串,每次隊首元素必定是當前最優的,然后把它的26個后繼加入到隊列中,優先級的設置就是該單詞能由字典里單詞派生的數目.

分類: 找循環 , 中等

題目大意: 題目描述比較長, 定義了若干規則,然后模擬n步(n <= 10^100),然后計數.

思路: 想法比較直接,直接找循環

分類:  概率, 簡單

題目大意: 兩人在用左輪手槍賭命, 現在對手開一槍沒事,輪到自己有兩種選擇,一是重新轉一下再開槍,二是直接開槍,告訴你子彈初始的放置情況,問那種生存概率更大.

思路:直接統計一下兩種概率,再比較一下即可

分類: 網絡流,中等

題目大意:給你一個有向無環圖, 找若干路徑把所有點覆蓋, 路徑直接可以相交

思路:

分類: 動規,中等

題目大意:  題目大概意思是有個人參加考試。這張試卷上有m種題型，共n道題（全是選擇題~），最后的成績上告訴他一共錯了k道題，對于每類題型，正確率分別為 Pi% 。現在他想知道每類題里面他分別錯了多少道。但是可能會有很多合法的情況。求在所有題型中，最多題目數 - 最少題目數 的差值最小的那種情況。保證至少存在一種合法情況。所有數為整數。（正確率使用一個比較糾結的取整函數，具體見題目）

思路: dp[i][j][k] 表示考慮到第i個題型，一共做了j個題，錯了k個題是否可能。轉移再枚舉第i個題型一共做x個題，錯y個題，看是否可行, 由于真正能轉移的很少,所以可搞

分類:

題目大意:

思路: