某島

… : "…アッカリ~ン . .. . " .. .
July 26, 2021

Codeforces Global Round 15

傳送門

Problem C.

給定一個圓環,初始已經連了一些線段,要求連剩下的線段,問最優情況下,最後總交點最多是多少。

不考慮已經連的線段,對於剩下的我們按照最優情況 1234..1234.. 這樣連就行。。
最後把已經連的拉進來一起統計即可。

Problem D.

給定一個長度為 n 的序列 a,問是否可以構造一個長度同樣為 n 的序列 b,使得 a 中的每個元素都是 b 中某兩個元素的差。
n <= 10

Problem E. Colors and Intervals

給 n 種顏色,初始時給長度為 n*k 個位置染色,使得每種顏色恰好出現 k 次。
求構造 n 組區間的方案,滿足對於每種顏色,都有一組區間的端點是這種顏色。
且,不存在某個位置,使得被區間覆蓋超過 \ceil{n, k-1} 次。
(n, k <= 100)

貪心?顯然我們總是選擇那些儘可能小的區間,因此對於每種顏色,我們只需要考慮 k-1 種相鄰的區間即可。
我們按照所有區間大小排序來依次選擇?很遺憾這樣是錯的。但是稍微改改,按照每個區間的右端點來排序就對了。

證明?反證法。
考慮某種顏色,我們枚舉了所有 k-1 種區間發現都不滿足,那麼對於這些區間 [a, b],
每個區間都存在 \ceil{n, k-1} 個區間使得它們的右端點均位於 [a, b] 的內部,因為覆蓋 [a, b] 的區間因為右端點比 b 大還沒有被我們掃描到。
那麼此時一共已經選擇了 (k-1)*\ceil{n, k-1} >= n 個區間,但是我們還沒有選擇那麼多,與假設矛盾。

Problem H. Guess the Perimeter

格點圖裡 ( <= 200) 有一個矩形,你可以至多 4 次詢問後回答這個矩形的周長。
每次詢問,你可以挑選任意數目的點,返回里這個集合中有多少點在目標舉行的內部或者邊緣。

???

Problem F. Telepanting

數軸上有 n 個傳送門,每個傳送門用三元組表示為 (xi, yi, {0,1}),表示傳送門所在位置為 xi,傳送的目標位置為 yi,以及當前是否 active。(yi < xi)
有一隻螞蟻從 0 出發,每個單位時間向右移動一格,當走到傳送門時,如果 inactive 則變為 active,如果 active 則被傳送至 yi 並置該傳送門為 inactive。
問走到 xn + 1 需要多少時間。

走到某個傳送門時,不管這個傳送門當前的狀態是 inactive 還是 active,前面的傳送門一定當前都是 active。
因為所有的傳送門都是往後退,那麼要突破某個傳送門,一定走上去的時候是 inactive,通過之後翻成 active。
這樣狀態就很簡單了,a[i] 表示第 i 個傳送門的狀態是 active,那麼走上去之後傳送走到下次回來需要花費多少時間。

轉移方程是 …
a[i] += x[i]-y[i];
REP(j, i) if (x[j] >= y[i]) a[i] += a[j];

用前綴和 + 二分查找優化即可。

Problem I. Organizing a Music Festival

求有多少長度為 n 的排列,滿足某些集合出現在連續位置。
(n <= 100)

有點意思。

首先不妨弱化,只考慮集合 size = 2 的情況。
那麼顯然每個集合相當於一條邊,於是我們轉化為一個圖論計數問題。

對於每個連通塊,要麼 * 1 如果 size = 1。
要麼 * 2 如果 size >= 2 並且是一條鏈(正反兩種情況)。
要麼 * 0 如果 size >= 2 且不是鏈。

最後再乘以 連通塊數 的階乘即可。

對於一般情況?構成了某種奇妙的樹形結構,上面的點和邊都變成節點的集合,dfs 進去邊 reduce 邊統計即可。

快乐赛车app哪个好玩 快乐飞艇是官彩还是私人彩票 彩票快乐飞艇玩法 三分钟快乐飞艇 快乐飞艇用哪个计划 有快乐飞艇的彩票app 快乐飞艇官网开奖 澳洲快乐赛车pk拾计划 快乐飞艇定位胆技巧 快乐飞艇app官网下载