owned this note
owned this note
Published
Linked with GitHub
# 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` 都沒有解的話,肯定沒有更長的字串是合法的解。
```cpp
#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$
```cpp
#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
```cpp
#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的事情就好了。