# NCTU PCCA Winter Camp Contest 2021 - 題解
###### tags: `Editorial`

本場比賽的題目與記分板皆有備份到 [Codeforces Gym](https://codeforces.com/gym/102946)。

## 目錄
<table style="text-align: center; font-weight: bold;">
<tr>
<td><a href="#A-A-Water-Problem">A</a></td>
<td><a href="#B-Bongcloud">B</a></td>
<td><a href="#C-Chicken-Nuggets">C</a></td>
<td><a href="#D-Discombobulator-3000">D</a></td>
</tr>
<tr>
<td><a href="#E-Evenly-Distributed">E</a></td>
<td><a href="#F-Fishy-Study">F</a></td>
<td><a href="#G-Group-Theoretic-Machine">G</a></td>
<td><a href="#H-Halting-Problem">H</a></td>
</tr>
</table>

# A. A Water Problem
###### 出題者：郭軒語（HNO2）
## 題目翻譯
給 $n$ 個正整數，每次求 $\mathcal{P}(a_i)=a_i \times \mathcal{D}(a_i)$ 為何，其中 $\mathcal{D}(x)$ 為 $x$ 中所有位數的總和。
## 解法
直接模擬即可。求出一個數字 $a_i$ 的所有位數總和可以紀錄一個變數 `digitsum=0` ，當 $a_i>0$ 時將 $a_i \mod 10$ 加至 `digitsum` ，並將 $a_i$ 設為 $\lfloor\frac{a_i}{10}\rfloor$ 直到 $a_i=0$ 為止。

如果使用 C++ 的話要注意到答案有可能會超出 `int` 的範圍。
# B. Bongcloud
###### 出題者：林栢瑋
## 題目翻譯
給 $N \cdot M$ 的矩陣，求上下對稱的子矩陣數目。
## 解法
因為是上下對稱矩陣，可以想成是回文，所以只須需要先維護每一直排的最長回文長度，每一橫排再橫著維護回文長度的遞增序列，就能夠輕易地算出答案。
# C. Chicken Nuggets
###### 出題者：黃克崴
## 題目翻譯

給一棵樹，每個節點有權重。請選擇一些點，使得其導出子圖 (induced subgraph) 中每個點的度都是奇數，且總權重最大，並求該權重。

## 解法

樹 DP。每個節點 $v$ 存 4 個值：
- $\operatorname{ans}(v)$：$v$ 的子樹的答案
- $\operatorname{no}(v)$：不選擇 $v$ 時，$v$ 的子樹的答案
- $\operatorname{even}(v)$：選擇 $v$ 和偶數個 $v$ 個子節點時，$v$ 的子樹的答案
- $\operatorname{odd}(v)$：選擇 $v$ 和奇數個 $v$ 個子節點時，$v$ 的子樹的答案

我們可以得到根節點的值是 $\operatorname{ans}(v)=\operatorname{no}(v)=0,\operatorname{even}(v)=c_v,\operatorname{odd}(v)=-\infty$ 以及轉移式：
- $\operatorname{ans}(v)=\max(\operatorname{odd}(v),\operatorname{no}(v))$
- $\operatorname{no}(v)=\sum_{x\text{ is a child of }v} \operatorname{ans}(x)$
- $\operatorname{even}(v)$ 就是 $($ 選偶數個 $v$ 個子節點的 $\operatorname{even}$ 值總和 $+$ 其他子節點的的 $\operatorname{no}$ 值總和 $)$ 的最大值
求這個值可以用貪婪的方法，把每個子節點的 $\operatorname{even}-\operatorname{no}$ 排序之後從最大的開始取。
- $\operatorname{odd}(v)$ 就是 $($ 選奇數個 $v$ 個子節點的 $\operatorname{even}$ 值總和 $+$ 其他子節點的的 $\operatorname{no}$ 值總和 $)$ 的最大值
求這個值的方法同上。

最後的答案即是 $\operatorname{ans}($根節點$)$。因為要對每個點的子節點們進行排序，總時間複雜度是 $O(n \log (n))$。

另外，$\operatorname{even}$ 和 $\operatorname{odd}$ 也可以用 DP 方式求得（令 $dpe_i,dpo_i$ 分別是處理完前 $i$ 個子節點時得到的 $\operatorname{even}$ 和 $\operatorname{odd}$），這樣時間複雜度可以降到 $O(n)$。

# D. Discombobulator 3000
###### 出題者：郭軒語（HNO2）
## 題目翻譯
互動題：有兩個 $1$ 到 $n$ 的排列 $a$ 和 $b$（0-indexed），其中存在常數 $k$ 滿足對於所有 $i$ 從 $0$ 到 $n-1$，$a_i=b_{(i+k) \mod n}$，但是你只知道排列的長度 $n$。
你每次詢問可以給定兩個整數 $x,y$ 會得到 $\max(a_x,b_y)$，要求在 $2n$ 次詢問內求出 $k$ 的值。
## 解法
這題應該有滿多種解法的 (?)，以下提供其中一種。以下的策略是希望能找到兩個排列中 $n$ 各在哪個位置。
1. 首先先詢問 `0 0,0 1,...,0 n-1` 各一次。
2. 如果在 1 中所有的答案都是 $n$，代表 $a_0=n$，之後再詢問 `1 0,1 1,...,1 n-1` 就能獲得 $n$ 在 $b$ 中的位置，就是詢問 `1 y'` 後得到 $n$ 的 $y'$。
3. 否則我們可以得到 $n$ 在序列 $b$ 中的位置。隨便再找一個 $b$ 中的位置 $y''$ 使得 $b_{y''} \neq n$ ，並詢問 `0 y'',1 y'',...,n-1 y''`，就可以獲得 $n$ 在序列 $a$ 中的位置，就是詢問 `x' y''` 後得到 $n$ 的 $x'$。
# E. Evenly Distributed
###### 出題者：郭軒語（HNO2）
## 題目翻譯
給定兩個正整數 $k,n$，將 $k$ 分成 $n$ 個正整數的總和，使得這 $n$ 個正整數形成的多重集合的非空子集都**不存在**均勻分割。
一個集合**存在**均勻分割，若且唯若存在一些數字總和是這個集合裡數字總和的一半。
## 解法
**Lemma:** 存在解的充要條件是 $k \geq 2^n -1$。

證明：若 $k < 2^n-1$ ，則可以發現 $n$ 個正整數形成的非空子集個數是 $2^n-1$ 個，然而每個子集的元素總和卻只有 $k$ 中，根據鴿籠原理必有兩個集合的總和相同。不妨假設是 $S$ 和 $T$，則可以發現 $S\bigtriangleup T$（其中 $\bigtriangleup$ 是[對稱差](https://en.wikipedia.org/wiki/Symmetric_difference)）會是存在均勻分割的集合，故集合不存在。

另一方面，若 $k \geq 2^n -1$，則可以發現 $\{2^0,2^1,2^2,\cdots,2^{n-2},k-2^{n-1}+1\}$ 是一個滿足題意的集合，因為可以發現對於每個字集而言，他的最大值都超過其數字總和的一半。若選到這個最大值，總和就會超過一半；若不選這個最大值，則總和就會不到一半。因此這個集合符合條件。
# F. Fishy Study
###### 出題者：林栢瑋
## 題目翻譯
給 $N \cdot N$ 的 $01$ 矩陣，以及一個會在格與格之間動的點，每回合會動的點必須選擇往四方位的其中一個方位動一步，動完後 $01$ 矩陣的每一格會以以下方法同時更新
- 若該格與會動的點重疊，則該格變為 $0$ 。
- 否則若該格原本為 $1$ 且其八方位有 $[2, 3]$ 個 $1$ ，則該格繼續為 $1$ 。
- 否則若該格原本為 $0$ 且其八方位有 $3$ 個 $1$ ，則該格變為 $1$ 。
- 否則該格為 $0$ 。
給開始時矩陣的樣子，問是否存在一種方法，能在 $d$ 步之內，使矩陣與最終矩陣長的一樣。
## 解法
非常普通的爆搜題，因為 $N, d$ 都非常小，所以只要暴力將所有動點的走法走一遍，每次暴力更新矩陣並檢查目前的矩陣與最終的矩陣是否相同即可。
# G. Group-Theoretic Machine
###### 出題者：黃克崴
## 題目翻譯

給定空間中 6 個點，分別為橘、紅、白、黃、綠、藍，且滿足：
- 橘點和紅點的連線平行 $x$ 軸
- 白點和黃點的連線平行 $y$ 軸
- 綠點和藍點的連線平行 $z$ 軸

請判斷是否能將一顆邊長為 $d$ 的魔術方塊置於空間中，使得這六個點都碰到對應顏色的那面。若答案為是，請給出一種做法。

## 解法

### 這題的小朋友版

在解這題之前，你可能會想嘗試一下 [2009-2010 NEERC, Northern Subregional Contest](https://codeforces.com/gym/100622) 的 Problem F。
:::spoiler 題目敘述
給平面上 4 個點，請找到一個正方形使其每一條邊上都恰有一個給定的點。
:::

[這裡](http://neerc.ifmo.ru/subregions/northern.html)雖然有題解，但可惜的是，他介紹的解法都有點複雜（而 Codeforces 排行榜上的大部分解法都與官解相似）。你可以在看完這一節之後試著找出一個簡潔的做法。

### 這題的普通版

如果不想要乘開一堆矩陣然後解三元三次方程的話，我們會需要一個工具，叫做[四元數](https://zh.wikipedia.org/zh-tw/%E5%9B%9B%E5%85%83%E6%95%B8%E8%88%87%E7%A9%BA%E9%96%93%E6%97%8B%E8%BD%89)。

假設有解，那麼我們一定可以把魔術方塊旋轉到某個方向，使得：

- 紅色面平行 $yz$ 平面
- 黃色面平行 $xz$ 平面
- 藍色面平行 $xy$ 平面

因為魔術方塊的紅黃藍三面是逆時針排列的，不失一般性可以令：

- 橘色面的方程為 $x=x_1$、紅色面的方程為 $x=x_1+d$
- 白色面的方程為 $y=y_1$、黃色面的方程為 $y=y_1+d$
- 綠色面的方程為 $z=z_1$、藍色面的方程為 $z=z_1+d$

假設某個四元數 $q=r+a\,\mathbf{i} +b\,\mathbf{j} +c\,\mathbf{k}$ 可以把方塊轉成上述的樣子。考慮 $\overrightarrow{OR}$ 向量旋轉之後的樣子：
\\[
\begin{aligned}
q \cdot \overrightarrow{OR} \cdot q^*
&=(r+a\,\mathbf{i} +b\,\mathbf{j} +c\,\mathbf{k}) \cdot (x_d\,\mathbf{i}) \cdot (r-a\,\mathbf{i} -b\,\mathbf{j} -c\,\mathbf{k})\\
&=(r^2 + a^2 - b^2 - c^2)x_d\,\mathbf{i} + 2(ab + cr)x_d\,\mathbf{j}+ 2(ac - br)x_d\,\mathbf{k}
\end{aligned}
\\]
，其中 $x_d$ 是 $O$ 和 $R$ 之間的距離。由於 $O,R$ 分別在橘色與紅色面上，我們可以寫出：
\\[
(r^2 + a^2 - b^2 - c^2)x_d=(x_1+d)-x_1=d
\\]
同理，
\\[
\begin{cases}
(r^2 - a^2 + b^2 - c^2)y_d = d\\
(r^2 - a^2 - b^2 + c^2)z_d = d
\end{cases}
\\]
而旋轉四元數會是單位四元數，因此有
\\[
r^2 + a^2 + b^2 + c^2 = 1.
\\]
題目保證了 $x_d, y_d, z_d$ 皆非零，於是我們有四條線性方程了！他們的解是：
\\[
\begin{cases}
r^2 = \frac{1}{4}\left( 1+\frac{d}{d_x}+\frac{d}{d_y}+\frac{d}{d_z} \right) \\
a^2 = \frac{1}{4}\left( 1+\frac{d}{d_x}-\frac{d}{d_y}-\frac{d}{d_z} \right) \\
b^2 = \frac{1}{4}\left( 1-\frac{d}{d_x}+\frac{d}{d_y}-\frac{d}{d_z} \right) \\
c^2 = \frac{1}{4}\left( 1-\frac{d}{d_x}-\frac{d}{d_y}+\frac{d}{d_z} \right) \\
\end{cases}
\\]
如果這些值有一個是負的，那答案一定是 `NO`。否則，有 16 個四元數 $q$ 能滿足上面的方程組（正負號的組合）（其實最多只有 8 種相異的），我們只要把他們分別拿來把輸入旋轉一下並檢查，就能得到答案。答案的頂點就是旋轉後平面交點們反向轉回去的結果：
\\[
\begin{cases}
V_1=q^* \cdot ((x_1+d)\,\mathbf{i} +(x_2+d)\,\mathbf{j} +(x_3+d)\,\mathbf{k}) \cdot q \\
V_2=q^* \cdot (x_1\,\mathbf{i} +(x_2+d)\,\mathbf{j} +(x_3+d)\,\mathbf{k}) \cdot q \\
V_3=q^* \cdot ((x_1+d)\,\mathbf{i} +x_2\,\mathbf{j} +(x_3+d)\,\mathbf{k}) \cdot q \\
\hfill\vdots\hfill
\end{cases}
\\]
需要檢查的地方是輸入的點是否真的都有碰到那些面，因為有可能發生共平面卻沒有碰到的情況。

# H. Halting Problem
###### 出題者：郭軒語（HNO2）
## 題目翻譯
給定一張 $n$ 個結點 $m$ 條邊的無向簡單連通圖 $G$，求最多可以在圖中選多少的結點，使得從中選取任意相異兩結點，他們之間任意走道（walk）長都是 $k$ 的倍數。一條走道的長度定義為經過的邊數。
## 解法
分成以下幾種情況討論：
* 若 $k=1$，顯然可以所有結點都選，答案就是 $n$。
* 若 $k\geq 3$，則可以發現如果有一條走道長是 $l$，則存在一條長為 $l+2$ 的走道（在其中一條邊來回走一次即可。由於 $k \geq 3$ 時 $l$ 和 $l+2$ 不可能同時是 $k$ 的倍數，所以不可能選兩個以上的結點，答案是 $1$。
* 若 $k=2$ 且 $G$ 為二分圖，則存在結點的一種黑白染色方法使得邊都連接到相異顏色結點。如果選擇了同為黑色與同為白色的相異結點，則由於每次走到相鄰結點都會換一次顏色，他們之間的任意走道長度必為偶數。因此答案就是黑色結點數與白色結點數取 $\max$。
* 若 $k=2$ 但 $G$ 不是二分圖，則圖上必定存在至少一個奇環。假設 $u$ 為任意奇環上的任意一點，$v_1,v_2$ 為任意相異結點點對。考慮以下兩種走道：
1. 從 $v_1$ 走到 $u$ 後，再從 $u$ 走到 $v_2$。
2. 從 $v_1$ 走到 $u$ 後，繞奇環一圈，再從 $u$ 走到 $v_2$。

可以發現以上兩種走道的奇偶性不同，故不可能選兩個以上的結點，答案是 $1$。

因此只要檢查 $k$ ，和檢查 $G$ 是否為二分圖即可。