# 2021 北市賽

不知不覺已經打完高中生涯最後一次北市賽了。
從高一在校內賽就被刷掉、高二被建中打爆差點只剩佳作，到高三終於如願進了全國賽。

今年的題目鑑別度跟去年相比有很大的進步 (或者說是恢復往年的水準？)，但題目還是偏怪，甚至跟去年一樣出現不可做題目 OAO

## 題目

### A
給一個 $n \times m$ 的二維表格
上面有一些連通的格子是黑色的 (不保證是凸的)
求黑色格子外圍的輪廓，從最左上的點順時針依序輸出
$n, m \le 1000$

### B
有一個字串集合
一開始為空
接下來會依序加入 $n$ 個字串 $s_1, ..., s_n$
定義一個字串 $s_i$ 的價值是 $|s_i|^2 - M \times \#\{k | 1 \le k \le i-1 \land lcp(s_i, s_k) = M \}$
其中 $M = \max_{1 \le j \le i-1}{lcp(s_i, s_j)}$
求所有字串的價值總和
$n \le 10^4, |s_i| \le 200$

### C
一個套圈圈遊戲有 $n$ 個目標物排成環形
每個目標物有一個權重 $v_i$
套中一個目標物可得分數是他左右兩邊的目標物權重相乘
之後被套中的目標物會消失
(特例：剩一個目標物時套中他的得分是他的權重)
問最大可能得分
$n \le 100, v_i \le 100$

### D
給一張無向圖
每個點有兩種權重 $a, b$
每個點的 $a$ 是事先決定好的，$b$ 是他和他所有鄰居的 $a$ 的總和
給你每個點的 $b$
求所有點的 $a$ 總和
$n \le 1000$

### E
給 $n$ 個區間，代表一張無向圖
區間 $[l, r]$ 代表 $l$ 跟 $l+1, l+2, ..., r$ 有連邊
如果一個點同時被包含在所有最大的 clique 裡，則稱這個點是關鍵的
輸出所有關鍵的點
$n \le 10^4$

### F
output only
給一張圖，問你是幾分圖，並給出一種分割方式
$V \le 10^4, E \le 2 \times 10^6$
(羊神說這是 NP-Hard OAO)

## 比賽過程記錄

其實我忘記當時的寫題順序了 QQ
計分板點選手名字沒跳出詳細資訊，不知道 484 師大 CMS 燒雞，總之我只能憑印象還原出大概的寫題順序

比賽剛開始 CMS 居然直接掛掉 OAO，全部人都登不進去，還好很快就恢復了

看完題目發現，居然有六題，而且沒有很顯然的水題欸
對題目們的第一印象是

A 煩躁實作
B 裸 Trie
C 可能是區間 DP，但不太像
D 除了高斯消去還是高斯消去
E 某種觀察
F 沒想法

總之先把 B 拿到再說

雖然是實作難度不高的 Trie，但比賽用的筆電鍵盤鍵位跟我的筆電不一樣，方向鍵還超小，好死不死左右鍵的上面就剛好是 PgUp 跟 PgDn，寫的時候一直按到，花了不少時間在適應這件事

在開始後 30 分鐘把 B 拿到手了

- 0/100/0/0/0/0

之後發現 C 暴搜居然可以拿 80 分，因為對滿分解還沒有想法，當然先撈了再說
傳上去發現，$O(n!)$ 居然 AC 了 ?\_?
怎麼可能，我連剪枝都沒剪欸？就算是師大測資也該有個限度吧？

- 0/100/100/0/0/0

這時候大概過了 50 分鐘，跑去刻 A 的滿分解，花了 30 分鐘好不容易刻完了
結果卻吃了個大大的 WA
這時朝著題本仔細一看，蛤，長方形有 71 分？
不管滿分解了，開撈

(再不先看子題啊，毒瘤)

- 71/100/100/0/0/0

中途 C 有 rejudge，果然就算是師大測資也不會讓我暴搜拿滿分的，我的 80 分總算是被打回原形

- 71/100/80/0/0/0

快過兩個小時了，還是連一半的分數都沒拿到
再這樣下去可能進不了全國
我開始慌了
看著還沒動過的 DEF，我挑了 F 來做
隨便構了一個 greedy 解，結果只拿了 10 分

- 71/100/80/0/0/10

時間不多了，我決定把一切都賭在 D 的高斯消去上
甚至沒去思考 $O(n^3)$ 會不會 TLE，就直接刻下去了
高斯消去刻出來以後，測範測居然沒有消乾淨 :EEEEE:

在極度慌張的情況下
我從腦海翻出在 AA 競程寫過的那題高斯消去的 AC code，試圖找出修好我 code 的方法
最後我採用的作法是，如果遇到要用第 $i$ 行消第 $i+1 \sim n$ 行，但第 $i$ 行第 $i$ 個變數係數是 $0$，就要從第 $i+1 \sim n$ 行找一行第 $i$ 個變數不是 $0$ 的跟他 swap
範測總算過了

上傳，拿到了 73 這個奇怪的分數 (27/0/46)
幸好是 TLE 不是 WA
把一行模運算的部分優化一下，就拿到 AC 了

- 71/100/80/100/0/10

還剩最後一點點時間，我把 E 的 37 分喇到
F 換了一種 greedy 方法，最後 30 秒壓線上傳，又唬爛過了兩筆
比賽結束

- 71/100/80/100/37/30

三小時六題真的寫不完啦 QwQ

## 成績

總分：418/600
Rank：一等四

## 一些有趣以及不有趣的事

0. 今年北市賽還是被建中主宰，十個全國賽名額有七個建中
1. 今年選訓高一保進來的張庭瑋，北市賽直接起飛，無情開電拿走一等三
2. 燒雞定理三人組都三等獎，其中山姆是第 11 名 QQ，還有 Foxdd 終於學會喇分了
3. dreamoon 預測的第六跟第七名結果分別得到 11 跟 12 名，或成新一代舒服大師？
4. 師大的神祺魔法總是會讓一二三等線切開，今年 400+ 都是一等，300+ 都是二等，250+ 都是三等
5. 下午跟其他選手和去年高三的電神玩桌遊，打風聲好幾次打到快終局都會出現各種鎖定、調虎離山、識破、角色技能滿天飛，超刺激
6. 張庭瑋 BFS 大師 orz
7. 打🉐國蟑螂，王政祺為了讓劉澈相信一隻蠍子不是蠍子，不惜犧牲三張牌來誘導他，心機大師