# 2020 建中校隊初選題解
## pA 君のコンパスは。
這題的定位是一題水題。

### Subtask 1
先將數學式子列出來：$P_i$和$P_j$所組成的圓的直徑為
$$D_{ij} = \sqrt{(x_i - x_j)^2 + (y_i - y_j)^2}$$
所以其面積
$$A_{ij} = \frac{D_{ij}^2}{4} \cdot \pi$$
所以呢，所求
$$\sum_{i \not= j}A_{ij} = \sum_{i \not= j}\frac{D_{ij}}{4} \cdot \pi = \frac{\pi}{4} \sum_{i \not = j} \left[\sqrt{(x_i - x_j)^2 + (y_i - y_j)^2}\right]^2$$
會變成
$$\frac{\pi}{4}\sum_{i \not = j} (x_i - x_j)^2 + (y_i - y_j)^2$$
用兩個迴圈$O(N^2)$跑即可。

### Subtask 2
因為$|x_i|, |y_i| \leq 20$，所以會發現一堆點都會重複座標。若$C_{xy}$代表「位於$(x, y)$有幾個點」，則所求
$$\sum_{x_1, y_1, x_2, y_2} C_{x_1y_1}C_{x_2y_2} \cdot \left( \frac{\pi}{4} \cdot \left( \sqrt{(x_1 - x_2)^2 + (y_1 - y_2)^2} \right)^2\right)$$
可以$O\left(C^4\right)$內跑完。

### Subtask 3
這個其實是一個通往滿分解的墊腳石，因為回到以上的式子：
$$\frac{\pi}{4}\sum_{i \not = j} (x_i - x_j)^2 + (y_i - y_j)^2$$
因為$y_i = 0$，所以可以更進一步簡化為
$$\frac{\pi}{4}\sum_{i \not = j} (x_i - x_j)^2$$
而因為$\sum_{i \not = j} (x_i - x_j)^2 = 2\times\sum_{i < j} (x_i - x_j)^2$，所以可以考慮少一點。透過觀察來優化：
$$(x_1 - x_2)^2 = x_1^2 + x_2^2 - 2x_1x_2$$
$$(x_1 - x_2)^2 + (x_1 - x_3)^2 + (x_2 - x_3)^2 = 2x_1^2 + 2x_2^2 + 2x_3^2 - 2x_1x_2 - 2x_1x_3 - 2x_1x_2$$
可以知道：
$$\sum_{i < j} (x_i - x_j)^2 = (N - 1) \times\sum_{i}x_i^2 - 2\sum_{i < j}x_ix_j$$
前面那項可以輕易的以$O(N)$的時間算出，但是後面的呢？慢慢條列，可以整理出後面的等於
$$x_1 \cdot x_2 + (x_1 + x_2) \cdot x_3 + (x_1 + x_2 + x_3) \cdot x_4 + \dots + (x_1 + x_2 + \dots + x_{N -1}) \cdot x_N$$
對於任何一個$x_ix_j$，它會在第$\max(i, j)$項被算到。

### Subtask 4
只要發現
$$\frac{\pi}{4}\sum_{i \not = j} (x_i - x_j)^2 + (y_i - y_j)^2 = \frac{\pi}{4}\sum_{i \not = j} (x_i - x_j)^2 + \frac{\pi}{4}\sum_{i \not = j} (y_i - y_j)^2$$
分開做一次就好。

### 常見問題
#### 如何輸出精準的小數？
以下以將變數x印出小數點後20位來舉例
若你使用C++
請`#include<iomanip>`並在main中加入
`cout << setprecision(20) << fixed;`
之後照常`cout << x`即可
若你使用C
請使用`printf("%.20lf", x);`
若你使用haskell
請使用`Text.Printf`中的`printf`
format specifier請參照C
若你使用python
請使用其他語言
或使用`print("%.20f"%x);`

#### 如何取得圓周率$\pi$？
可以使用內建`#include <math.h>`後的`acos(-1)`（$\arccos(-1)$）、直接用背的（`3.1415926535...`）或者用題目給的（範測$1$除以二）
## pB 對發票
這題的定位是一題水題。
可以發現如果有一個字串 $S$ 是解的話，任何 $S$ 的子字串都是一個解
因此我們只需要分別檢查 `a-z` 單獨一個字母組成的字串是不是解就可以了
如果 `a-z` 都沒有解的話，肯定沒有更長的字串是合法的解。

#include <iostream>
#include <string>
using namespace std;
signed main() {
    ios_base::sync_with_stdio(0), cin.tie(0);
    int fail[26] = {}, n;
    cin >> n;
    for(int i = 0; i < n; i++) {
        string s;
        cin >> s;
        int cnt[26] = {};
        for(char c: s) cnt[c-'a'] += 1;
        for(int i = 0; i < 26; i++)
            if(!cnt[i])
                fail[i] = 1;
    }
    for(int i = 0; i < 26; i++)
        if(!fail[i])
            return cout << char('a'+i) << '\n', 0;
    cout << 7122 << '\n';
}

對於使用 python 的人很抱歉，因為我測資是在 windows 上面生的，最後面會多上一個 `\r` 字元。 C++ 不會讀到這個字元，但是 python 的 `input()` 會，所以沒有驗題者發現，直到賽後聽到有人抱怨才趕緊 rejudge，很抱歉徒增你們的 debug 時間。
> python要去掉字串頭尾的特殊字元可以用 `.strip()`

還好沒人使用 Haskell 不用跟用 Haskell 的人道歉

## pC 開窗戶
### Subtask 1, 2
考慮到所有可能的情況只有 $2^{nm}$ 種
所以直接枚舉即可
score 20 gotcha

### Subtask 3
使用位元 $dp$
考慮 $dp_{i, mask}$ 為完成了前 $i$ 排，而第 $i$ 排的開窗戶情形為 $mask$
總共有幾種方法
每次在轉移的時候 枚舉下一排的 $mask'$ 狀況，並且
$O(m)$ 驗證是否能從 $mask$ 到 $mask'$
總共複雜度 $O(n\cdot 2^{m+m})$
score 40 gotcha
### Subtask 4
對位元 $dp$ 作一點改善
這次多作一格，對於輪廓線進行位元 $dp$

#include<bits/stdc++.h>
#define pb emplace_back
using namespace std;
const int maxn = 17;
int p;
int *dp = new int[1<<maxn]{}, *tmp = new int[1<<maxn]{};
int n, m;
void madd(auto &v, auto val) {
	v += val - p;
	v += (v>>31) & p;
}
void transform(int *&dp) {
	int *tmp = new int[1<<maxn]{};
	int ab = (1<<n)-1;
	for (int s = 0;s < 2<<n;++s) {
		madd(tmp[(s&ab)<<1], dp[s]);
		madd(tmp[((s&ab)<<1)|1], dp[s]);
	}
	swap(dp, tmp);

	for (int s = 0;s < 2<<n;++s) 
		if ((s&0b111) == 0)
			dp[s] = 0;
}

void ob(int v) {
	for (int i = 0;i <= n;++i)
		cout << (v&1), v>>=1;
}

void solve() {
	for (int s = 0;s < 2<<n;++s) 
		dp[s] = (s & 0b111) != 0;

	for (int i = 1;i < m;++i) {
		for (int j = 1;j < n;++j) {
			fill(tmp, tmp+(2<<n), 0);
			for (int s = 0;s < 2<<n;++s) {
				for (int w : {0, 1}) {
					if (w + !!(s&(1<<j-1)) + !!(s&(1<<j+1)) + !!(s&(1<<j)) < 2) continue;
					int ns = s ^ ((((s>>j)&1) ^ w) << j);
					madd(tmp[ns], dp[s]);
				}
			}
			swap(dp, tmp);
		}
		transform(dp);
	}
}
signed main(){
	ios_base::sync_with_stdio(0), cin.tie(0);
	cin >> n >> m >> p;
	solve();
	int res = 0;
	for (int i = 0;i < 1<<n;++i)
		madd(res, dp[(i<<1)|1]);
	cout << res << '\n';
}

## pD 運送蛋餅
題目的意思是給你 $n$ 個三維空間中的點，點與點之間相連的花費是距離的平方，要你找出最小的花費使得所有點連通，亦即最小生成樹。

### Subtask 1
手動展開或利用位元枚舉所有可能性，並取最小值。
$n \leq 3$ 都是可以一行解決的
如果出到$n = 4$ 可能得寫多行一點XD

#include <bits/stdc++.h>
using namespace std;
int n;
int x[10], y[10], z[10];
int cost(int a, int b) {
    int dx = x[a]-x[b], dy = y[a]-y[b], dz = z[a]-z[b];
    return dx*dx+dy*dy+dz*dz;
}
 
signed main
    cin >> n;
    for(int i = 0; i < n; i++) cin >> x[i] >> y[i];
    if(n == 1)
        cout << 0 << '\n';
    else if(n == 2)
        cout << cost(0, 1) << '\n';
    else if(n == 3) {
        int a = cost(0,1), b = cost(1,2), c = cost(2,0);
        cout << min({a+b,b+c,c+a}) << '\n';
    }
}

### Subtask 2
$n \leq 100$
利用 kruskal 演算法，$\mathcal{O}(|E|\log|E|)$
或者用 prim 搭配普通的 heap，$\mathcal{O}((|E|+|V|)\log|V|)$
注意 long long

### Subtask 3
$y_i=z_i=0$
所以有用的邊只有$x$座標相鄰的邊
把 $x$ sort之後相鄰項的差平方加起來就好了

### Subtask 4
注意到原圖是一張稠密圖，因此 prim 不適合用 heap 加速
改成每次 $\mathcal{O}(|V|)$ 找最小值、更新距離
複雜度 $\mathcal{O}(|V|^2)$ ， AC 。
如果你的 code 常數特小，kruskal 或者 boruvka 都有可能有機會過啦 :P

### 小插曲
波路前一天告訴我們一個唬爛解：按照$x$ sort 之後，只考慮每個點往前1000個點的邊然後做Kruskal，於是出題者努力卡掉了。旋轉之後的版本我也盡量卡掉了，按照 $x+y+z$ sort 的也被卡掉了，可是想不到的是有人一直試出按照 $x-y-z$ sort 就可以唬爛過了QQ測資不夠強喇

## pE 神奇寶貝獎章

初選仲了兩題 >< 開心開心反正題目就是說，給你兩堆兩兩相異的數字，第一堆有$N$個，第二堆有$M$個，和一個常數$1 \leq K \leq \min(N, M)$，我將隨機從兩堆數字中各選出$K$各數字，然後排序；排序後，再一一比較大小，請問來自第一堆的數字贏的次數比的期望值？

### 期望值的定義
首先，期望值的定義是：若有一堆事情會發生，第$i$件事情發生的機率是$p_i$，得到的分數是$x_i$，且令$X$為得到的分數，則
$$\mathbb{E}\left[X\right] = \sum_i p_ix_i$$

### Subtask 1
因為我不論怎麼選，每一局都會贏，所以直接輸出$K$即可獲得AC。

### Subtask 2

$N = M = 6$的情況下，有$\binom{N}{K} \times \binom{M}{K}$中選法。在最糟糕的境況下，$N = M = 6$，$K = 3$有最大值$20 \times 20 = 400$。所以，作法就是直接枚舉選了哪些數字，排序後再直接計算贏了幾局然後排序。這樣複雜度$O(\binom{N}{K}\binom{M}{K} \times K)$，AC。

### Subtask 3
原本我是出$K = 6$，$N, M \leq 2 \times 10^5$的，結果被AY用DP電爆了，所以就變成一個subtask了 ><

DP狀態為$dp[i][j][k][l]$，分別代表dp[前$n$張卡片][$A$派了幾個][$B$派了幾個][$A$目前贏幾場]

### Subtask 4
其實還挺廢的，只是如果你會滿分解但是懶得離散化的話，就可以直接來XD
不妨假設數字都已經排序過了，亦即$a_1 < a_2 < \dots < a_N$且$b_1 < b_2 < \dots < b_M$。若$a_i > b_j$，那這對分數的貢獻為何呢？假設也已經知道說$a_i$、$b_j$都是抽出來的第$r$大，則比$a_i$小的拿法有$\binom{i - 1}{r - 1}$，比$a_i$大的拿法有$\binom{N - i}{K - r}$種。若$a < b$，則定義$\binom{a}{b} = 0$。對於$b_j$亦然。則對答案的貢獻為：
$$\binom{i - 1}{r - 1}\binom{N - i}{K - r}\binom{j - 1}{r - 1}\binom{M - j}{K - r}$$

然後呢，就可以發現，假設固定了$r$，就可以知道說我要求的是
$$\sum_{a_i} \sum_{b_j < a_i} \binom{i - 1}{r - 1}\binom{N - i}{K - r}\binom{j - 1}{r - 1}\binom{M - j}{K - r}$$
$$=\sum_{a_i} \left[\binom{i - 1}{r - 1}\binom{N - i}{K - r}\sum_{b_j < a_i} \binom{j - 1}{r - 1}\binom{M - j}{K - r}\right]$$
就可以用一個支援區間查詢的資料結構（BIT、線段樹、Treap...）來實作了，複雜度$O\left(K(N + M)(\log(N) + \log(M))\right)$。

### Subtask 5
會發現數字其實是到$10^9$的，如果直接開那麼大的資料結構會爆，所以先離散化再做Subtask 4的事情就好了。