BOI 2020

BOI 2020

Day 1

傳送門
HackMD
競プロ日常

Problem A. Colors

題意

互動式問題,給定 n,每次你可以將頭髮染成 1-n 中間的一個數字,如果相鄰兩次的數字差的絕對值 >= C,那麼男朋友會注意,返回 1,否則返回 0。每個顏色只能用一次,用儘可能少的詢問找到 C。

題解

很優雅的倍增構造。

Problem B. Mixture

題意

動態維護若干瓶調味料,每瓶調味料中裝有一定質量的 鹽,胡椒與大蒜 的混合物,給定美食家最喜歡的調味料的組成,每次詢問,可以增加一瓶新的調味料或者刪除一瓶之前添加過的調味料,返回至少需要幾瓶可以混合出美食家最喜歡的口味。

題解

不會。

Problem C. Joker

題意

給定一張有 n 個點 m 條邊的無向圖,每次詢問給出一個區間 [L, R],問是否存在奇環,使得環中不包含區間中的點。

題解

是否存在奇環,等價於二分圖判定。靜態可以 dfs,動態的話可以 dsu,最後外面套一層莫隊演算法即可。

當然也可以直接用 lct!

對於刪除 [l, r] 區間的邊,我們可以用類似破環為鏈的方法,轉化為每次詢問保留 (r, l+m) 區間的邊,顯然邊越少越容易合法,滿足單調性。我們按照時間順序依次插入所有邊,用 double-point 維護出處理到時間 r 時,最大的 l 使得當前的狀態合法即可。這樣就可以貼 BZOJ 4025 的代碼了。

Day 2

傳送門
競プロ日常

Problem A. Graph

題意

給定一個邊被紅、藍染色的無向圖,求一組節點的權值方案,滿足對所有的紅邊,關聯的節點的權值和為 1,對所有的藍邊,權值和為 2,滿足條件的基礎上,最小化所有節點的權值和。

題解

讓人想起了之前 Atcoder 上的一道染色的題。不過這個題是實數。做法是隨便找個點和初始標記一路 dfs 下去把每個節點標記成 ax+b 的形式,其中 a 屬於集合 {-1, 0, 1},x 是一個待定係數,最後算出 x 的值即可,需要一些 insight。

Problem B. Village

題意

給定一個樹,求兩組錯位排列的方案 P,分別使得 \sum dist(i, P[i]) 的權值和最大和最小。

題解

首先最小的話顯然儘可能交換相鄰的結點編號就好了,我們就每次找葉子,如果沒有交換過,就和父節點交換,這樣最後有可能還剩一個,沒關係隨便找一個相鄰結點再交換一次就好。

對於最大的情況,我們考察每條邊 (u,v),那麼這條邊貢獻的上界是 min(sz[u], sz[v]),我們發現可以構造方案讓所有邊的上界都達到,方法是只要考察重心,讓每個點都標記在另一顆子樹中即可。

這樣看的話,似乎是需要找一下重心的。。。但是 最快的提交代碼 直接就上了。。只要證明這樣構造之後,可以找到一個節點作為根,使得每個節點都不落入同一子樹中就行了。。而這是顯然的,因為以重心分割的話,子樹的 size 不會超過 n/2。

Problem C. Viruses

題意

基因序列是一個由 n 種數字形成的字元串,其中 0、1 為終止字元,其他為病毒字元,給定一張基因突變的表格,每個表格表示一個病毒字元可能會突變成的基因串,一個基因序列每一秒中,會有一個病毒字元突變,一些病毒字元可能有多種突變方向。給定一些模式串作為抗體,問每個病毒字元所能形成的最短的,不被任意一個抗體所識別的終止序列的長度(或者輸出不存在)。

題解

沒有病毒串的時候顯然可以用類似最短路的方法 dp 出最短長度。。有病毒串的時候開個自動機就好。。由於我們需要支持合併字元串的操作,所以 dp 狀態需要加維,記錄在自動機中的狀態區間,具體說來就是 dp[i][st][ed] 表示基因 i 展開之後,從狀態 st 到狀態 ed 的最短路徑長度。

沖了一發 果斷 TLE 了。雖然本質上是最短路模型,但是本題的邊是廣義的,可能會與多個節點關聯,Dijkstra 著實不太好寫,所以用了 Bellman_Ford,考慮到瓶頸主要在鬆弛(Relax)操作上(每次都要跑一遍神似 Floyd 的 DP),感覺改成 SPFA 可過。

換了 SPFA 之後還是有一個點過不去,看來本題數據還是很良心的。。

看了一下其他人的搞法,最快的 WZYYN 同學非常厲害,直接 Bellman_Ford 加了一個奇怪的剪枝就過了,然後 duality 看起來是常規的 SPFA,在 Relax 的時候跳過了無窮的情況,原理就跟一些矩陣乘法的題目,需要優化掉內層循環的取模差不多。

然後 BenQjiangly 的給都是 Dijkstra 正解。最猛的是 liouzhou_101,直接卡時,居然還卡過去了 Orz。。。(所以我也卡時吧。。> <。。。