手機(jī)站首頁(yè)散文詩(shī)歌雜文隨筆日記小小說(shuō)

散文網(wǎng) » 科技 »學(xué)習(xí) » NCTU PCCA Winter Contest 2021 個(gè)人題解

NCTU PCCA Winter Contest 2021 個(gè)人題解

2021-03-10 17:48 作者:俊杰_Charles 0人讀過(guò) | 我要投稿

比賽鏈接：https://codeforces.com/gym/102946

官方題解：https://hackmd.io/@HNO2/HJTOKCOe_

難度：3星

A. A Water Problem

題意：給定一個(gè)數(shù) $x$ ，求 $x$ 的各位數(shù)字之和與 $x$ 本身的乘積。

題解：按題意計(jì)算即可。

B. Bongcloud

題意：給定一個(gè) 01 矩陣，求上下對(duì)稱的子矩陣有多少個(gè)。

題解：對(duì)于每列使用一次馬拉車算法，求得以每個(gè)位置為中心，上下拓展的最長(zhǎng)回文串長(zhǎng)度。對(duì)于某一行，我們將以各位置為中心的最長(zhǎng)回文串描出對(duì)應(yīng)方格，得到如下的圖。

這里是回文串長(zhǎng)度為奇數(shù)的情況，若回文串長(zhǎng)度為偶數(shù)，則對(duì)稱軸在兩行之間

如上圖，以藍(lán)色行為對(duì)稱軸，且范圍在黑色方格內(nèi)的子矩形一定滿足條件。對(duì)于每條對(duì)稱軸，求出這樣的子矩形有多少個(gè)即可。根據(jù)對(duì)稱性，我們可只關(guān)注對(duì)稱軸的一側(cè)。

問(wèn)題便可轉(zhuǎn)化為，求以每個(gè)藍(lán)色方格作為右下角的矩形有多少個(gè)。以最右側(cè)藍(lán)色方塊為例，滿足條件的矩形范圍落在下圖的黃色區(qū)域中，以該藍(lán)色方塊作為右下角的矩形個(gè)數(shù)實(shí)際上就是區(qū)域中的方格數(shù)。

而這樣的區(qū)域一定是一個(gè)單調(diào)上升的區(qū)域，因此我們?cè)趶淖笙蛴颐杜e這些位置時(shí)，用一個(gè)單調(diào)棧維護(hù)這樣的區(qū)域即可。時(shí)間復(fù)雜度 $O(nm)$ 。

C. Chicken Nuggets

題意：給定一個(gè)樹(shù)，各點(diǎn)有一個(gè)點(diǎn)權(quán)。如果一個(gè)點(diǎn)被去掉，則與之相連的邊也會(huì)被去掉?，F(xiàn)需要去掉一些點(diǎn)，使得剩下的各點(diǎn)與之相連的邊數(shù)都為奇數(shù)，求剩下各點(diǎn)的點(diǎn)權(quán)和最大是多少。

題解：定義狀態(tài) $%5Ctext%7Bdp%7D%5Bu%5D%5B0%2F1%5D%5B0%2F1%5D$ ，表示以 $u$ 為根的子樹(shù)，點(diǎn)? $u$ 去掉/保留，點(diǎn) $u$ 的度數(shù)為偶數(shù)/奇數(shù)，該狀態(tài)下點(diǎn)權(quán)和的最大值。最初， $%5Ctext%7Bdp%7D%5Bu%5D%5B0%5D%5B0%5D%3D0$ ， $%5Ctext%7Bdp%7D%5Bu%5D%5B1%5D%5B0%5D%3Dc%5Bu%5D$ ， $%5Ctext%7Bdp%7D%5Bu%5D%5B1%5D%5B1%5D%3D-%5Cinfty$ （ $%5Ctext%7Bdp%7D%5Bu%5D%5B0%5D%5B1%5D$ 是不可能出現(xiàn)的狀態(tài)）。然后像背包 dp 一樣，將? $u$ 的各個(gè)兒子放入背包中。假設(shè)將? $u$ 的兒子? $v$ 放入背包前， $u$ 的各個(gè) dp 值為 $%5Ctext%7Bpre%7D%5Bu%5D%5B0%2F1%5D%5B0%2F1%5D$ 。此時(shí)將 $v$ 放入背包中，有：

$%5Ctext%7Bdp%7D%5Bu%5D%5B0%5D%5B0%5D%20%3D%20%5Ctext%7Bpre%7D%5Bu%5D%5B0%5D%5B0%5D%20%2B%20%5Cmax(%5Ctext%7Bdp%7D%5Bv%5D%5B0%5D%5B0%5D%2C%20%5Ctext%7Bdp%7D%5Bv%5D%5B1%5D%5B1%5D)$
$%5Ctext%7Bdp%7D%5Bu%5D%5B1%5D%5B0%5D%20%3D%20%5Cmax(%5Ctext%7Bpre%7D%5Bu%5D%5B1%5D%5B0%5D%20%2B%20%5Ctext%7Bdp%7D%5Bv%5D%5B0%5D%5B0%5D%2C%20%5Ctext%7Bpre%7D%5Bu%5D%5B1%5D%5B1%5D%20%2B%20%5Ctext%7Bdp%7D%5Bv%5D%5B1%5D%5B0%5D)$
$%5Ctext%7Bdp%7D%5Bu%5D%5B1%5D%5B1%5D%20%3D%20%5Cmax(%5Ctext%7Bpre%7D%5Bu%5D%5B1%5D%5B0%5D%20%2B%20%5Ctext%7Bdp%7D%5Bv%5D%5B1%5D%5B0%5D%2C%20%5Ctext%7Bpre%7D%5Bu%5D%5B1%5D%5B1%5D%20%2B%20%5Ctext%7Bdp%7D%5Bv%5D%5B0%5D%5B0%5D)$

最終答案為 $%5Cmax(%5Ctext%7Bdp%7D%5B1%5D%5B0%5D%5B0%5D%2C%20%5Ctext%7Bdp%7D%5B1%5D%5B1%5D%5B1%5D)$ ，時(shí)間復(fù)雜度 $O(n)$ 。

D. Discombobulator 3000

題意：交互題?，F(xiàn)有兩個(gè)數(shù)列 $a_0%2Ca_1%2C%5Cdots%2Ca_%7Bn-1%7D$ 和 $b_0%2Cb_1%2C%5Cdots%2Cb_%7Bn-1%7D$ ，兩者都為? $1$ 到? $n$ 的排列，且? $b$ 為? $a$ 循環(huán)右移? $k$ 位的結(jié)果。每次詢問(wèn)兩個(gè)值 $x%2Cy$ ，可以得到 $%5Cmax(a_x%2Cb_y)$ 。在詢問(wèn)次數(shù)不超過(guò)? $2n$ 的條件下，求得 $k$ 。

題解：詢問(wèn) $%5Cmax(a_0%2Cb_0)%2C%5Cmax(a_1%2Cb_1)%2C%5Cdots%2C%5Cmax(a_%7Bn-1%7D%2Cb_%7Bn-1%7D)$ ，得到的結(jié)果中若只有一個(gè) $n$ ，則 $k%3D0$ 。若有兩個(gè) $n$ ，即 $%5Cmax(a_i%2Cb_i)%3D%5Cmax(a_j%2Cb_j)%3Dn$ ，則再詢問(wèn) $%5Cmax(a_i%2Cb_j)$ 。若 $%5Cmax(a_i%2Cb_j)%3Dn$ ，說(shuō)明 $a_i%3Db_j%3Dn$ ，否則說(shuō)明 $a_j%3Db_i%3Dn$ ，據(jù)此得出 $k$ 。詢問(wèn)次數(shù)最多為 $n%2B1$ 。

E. Evenly Distributed

題意：定義一個(gè)數(shù)集可以被均分，表示存在一種方案將這個(gè)數(shù)集分為兩個(gè)集合，使得這兩個(gè)集合中數(shù)的和相等?，F(xiàn)要求夠造一個(gè)含? $n$ 個(gè)正整數(shù)的集合，這? $n$ 個(gè)數(shù)的和為 $k$ ，且這個(gè)集合的任意一個(gè)子集都不能被均分。

題解：貪心，每次把能放入集合中最小的數(shù)放入集合，那么依次放入集合的數(shù)為 $1%2C2%2C4%2C8%2C%5Cdots$ ，可以發(fā)現(xiàn)正好都是? $2$ 的冪次。按照貪心的思路，先在集合中放入 $1%2C2%2C4%2C%5Cdots%2C2%5E%7Bn-2%7D$ ，那么最后需要放入的則是? $k-(1%2B2%2B4%2B%5Cdots%2B2%5E%7Bn-2%7D)%3Dk-(2%5E%7Bn-1%7D-1)$ 。而最后放入的數(shù)應(yīng)當(dāng)大于 $2%5E%7Bn-1%7D$ ，也就是說(shuō)如果 $k-(2%5E%7Bn-1%7D-1)%3C2%5E%7Bn-1%7D$ ，即 $k%3C2%5En-1$ ，那么滿足條件的構(gòu)造方式便是不存在的。

F. Fishy Study

題意：有一個(gè)魚(yú)塘，以? $n$ 行? $n$ 列的 01 矩陣表示， $0$ 表示該位置一開(kāi)始沒(méi)有魚(yú)， $1$ 表示該位置一開(kāi)始有魚(yú)。同時(shí)，魚(yú)塘中某個(gè)位置還有一個(gè)海膽。每一天，魚(yú)塘中依次發(fā)生如下變化：

海膽會(huì)往上、下、左、右中可移動(dòng)的方向移動(dòng)一格。
對(duì)于每個(gè)位置，如果海膽在該位置，則該位置這一天沒(méi)有魚(yú)；否則，如果該位置前一天有魚(yú)，且周圍八個(gè)格子中有? $2$ 或? $3$ 條魚(yú)，則該位置這一天有魚(yú)；否則，如果該位置前一天周圍八個(gè)格子中有? $3$ 條魚(yú)，則該位置這一天有魚(yú)；否則，該位置這一天沒(méi)有魚(yú)。

給出魚(yú)塘的初始狀態(tài)，并給出一個(gè)理想狀態(tài)，問(wèn)? $d$ 天內(nèi)該魚(yú)塘是否可能出現(xiàn)理想狀態(tài)。

題解：魚(yú)塘的最終狀態(tài)其實(shí)只與海膽的移動(dòng)路線有關(guān)。由于? $d$ 最大為 $8$ ，海膽的移動(dòng)路線最多有? $4%5E8%3D65536$ 種，爆搜即可。我的代碼中使用了 bitset 存儲(chǔ)狀態(tài)，需要注意下標(biāo)的區(qū)別。

G. Group-Theoretic Machine

題意：給出三維空間里的六個(gè)點(diǎn) $O%2CR%2CW%2CY%2CG%2CB$ ，其中 $OR$ 平行于 x 軸， $WY$ 平行于 y 軸， $GB$ 平行于 z 軸。問(wèn)是否存在一個(gè)正方體，使得這六個(gè)點(diǎn)分別在正方體的六個(gè)面上。若存在，求出這個(gè)正方體的各頂點(diǎn)坐標(biāo)。

題解：不會(huì)。

H. Halting Problem

題意：給一張連通圖，要求選出一個(gè)點(diǎn)集，使得點(diǎn)集中任意選擇兩點(diǎn)，從一點(diǎn)到另一點(diǎn)的任意路徑長(zhǎng)度都為? $k$ 的倍數(shù)。求點(diǎn)集中點(diǎn)數(shù)最多為多少。

題解：顯然， $k%3D1$ 時(shí)答案為所有的點(diǎn)。由于是任意路徑，因此兩點(diǎn)間如果存在一條長(zhǎng)度為? $l$ 的路徑，那么通過(guò)重復(fù)走某條邊可以得到長(zhǎng)度為? $l%2B2$ 的路徑。因此，當(dāng)? $k%3E2$ 時(shí)，答案只能為 $1$ 。當(dāng)? $k%3D2$ 時(shí)，如果給出的圖為二分圖，二分圖左部和右部對(duì)應(yīng)的兩個(gè)點(diǎn)集都是滿足條件的，選擇點(diǎn)數(shù)更多的即可；如果不是二分圖，可以證明兩個(gè)不同點(diǎn)之間肯定既存在長(zhǎng)度為偶數(shù)的路徑，又存在長(zhǎng)度為奇數(shù)的路徑，所以此時(shí)答案只能為 $1$ 。判斷是否為二分圖使用染色法，時(shí)間復(fù)雜度 $O(n)$ 。