###### tags: `Competitive Programming`
# 2020北市賽心得

:::success
**Score: 265/500, Rk: 28 - 佳作**
:::
**懶人包：燒雞**

## 心得
剛接觸程式一年
沒想到這一年就獻給了演算法還有這些競賽
從高一校內初試就被刷下來
過了一年的高二，筆試、上機、培訓、模擬賽
一路到現在的北市賽
中間經歷了好多事，也受過很多打擊

雖然沒有預期的三等獎
可是能拿到這樣的名次其實也很滿意了
大家口中的電神
今天也都一一親眼見到，好神奇歐
"原來他就是那個OOO"
"哇他是橘人欸，好強歐"
電神就是擁有不一樣的風采

不過說真的今年的比賽滿誇張的
多了從來沒有的簽到題(雖然我很需要QQ)
也沒有需要奇怪演算法的題目（呃pD除外）
昨天晚上還在認真地整理先前寫過的模板
結果今天帶去的codebook根本只拿來當計算紙用QQ
而且題目一直改來改去，讓人有點火大

題目品質的話，
聽電神們說比去年還爛很多
他們說有四題簡單到爆，然後剩下一題爆難而且測資還有問題
(不過我應該是沒什麼資格嘴題目就是了QQ)
賽前的主持人解說tie breaker的時候
還說今年應該是用不到
結果...400分有9個，300分有5個，還有一堆同分
(wiwiho、王品翔、電餅因為這樣被排到二等獎去了QAQ)
自己打臉自己

接下來的兩個禮拜暫時休息不碰題目
先把漏掉一大半的段考讀回來
班排一的紀錄要中斷了，這次希望不要摔出前三就好
段考結束後要開始為半年後的TOI準備
培訓期間我發現超棒的資源 - CF EDU
他會一步一步用題目帶著你學會某個演算法
到時候會發祭品文，或是創個小帳督促/紀錄自己練習
畢竟寫過的題目真的太少了，明顯練習不夠
之後歡迎大家來卡

## 題目
嗯~有ISSC的味道呢
### pA - DP / 組合數學
在一個$n \times m$的網格上，欲從$(1, 1)$走到$(n, m)$
每一步可以往右/下
或者可以往上，往上最多 $k$ 次 ($k$不超過$1$)
但往上之後接著就要往下
問共有幾種走法?
$n, m \leq 15$

### pB - 排序語法題
一直線上有山頂跟山谷一共$N$個
其中山頂與山谷之間為一直線的坡，依序編號$1 \sim n-1$
將坡按照坡度( |斜率| )遞增排序後輸出順序
$N \leq 1000$

### pC - DP & 矩陣快速冪 / 組合數學
有$N$個旗子排成一排，每面旗子上面裝飾一個西洋棋子
棋子種類有騎士、城堡、主教、兵卒、國王、皇后
國王和皇后的數量分別要是偶數
求裝飾這些旗子有多少種方法
$N \leq 10^6 \to N \leq 10^9$ (更改題目)

### pD - 噁心數論 / 同餘方程組
(以下的"="符號指的是"同餘")
設多項式$f(x)$，$deg(f(x)) \leq 100$
給定一質數$p$、數個多項式$g_1(x)...g_n(x)$
和序列$A = {a_1...a_n}$
其中$deg(g_i(x)) \leq 100$ 且 $n \leq 1000$
並且滿足
$g_1(x) \equiv a_1 (mod\ p)$
$g_2(x) \equiv a_2 (mod\ p)$
...
$g_n(x) \equiv a_n (mod\ p)$
保證 $x$ 存在至少一組解，且此解 $\leq 2147483647$
求將解代入$f(x)$的值(保證此值唯一)

### pE 圖論
題目我不是很清楚
(他們一直改來改去我根本不知道他們要問什麼QQ)
好像可以轉化成有向圖最長路徑(?

## 解法
:::success
**廁所真棒**
:::
開場邊打模板邊讀題目
看到pB還以為自己想得太簡單又重看好幾次
沒想到真的是語法題，傻眼
這不是北市賽的風格吧吧吧吧
雖然是簽到題可是我還是debug好久qq
半小時後發現忘了加絕對值，改了丟上去就過了

pD一臉防破台樣直接跳過
pE一臉實作樣直接跳過

回頭看pA，想說$n, m \leq 15$感覺就是要推數學公式
就一直往很數學的方向想
結果卡了太久想不到滿分解，就先撈了65分

接著輪到pC，
去**上個廁所回來就突然通靈出DP作法**(????
令$dp[i][a][b]$為裝飾到第i面旗子的方法數
$a, b$分別代表國王、皇后數量是奇數或是偶數(1或0)
轉移式也很好推
反正就是$O(4 \cdot n)$的DP，$N \leq 10^6$會過

大概寫了10分鐘，要丟的時候看到公告
結果題目$N$居然改成$10^9$ wwwwwwwwwwwwwwwwwwwwwww
想說隨便，丟上去也還有52分
聽說測資本來就到10的9次方
有很多高手因為這個吃TLE吃好久
(幫QQ，師大辦的比賽真的不靠譜)

接著再次去上廁所，又突然想到可以矩陣快速冪優化到$O(\log n)$
隨後就開始刻矩陣乘法
寫出來丟上去，0分
想了一下，不對啊，連$n \leq 5$的case都沒有過
把剛剛的$O(n)$ DP抓下來對拍
結果發現...矩陣乘法的乘號打成加號
然後...又燒了半個小時qqqqq

到這裡265分，只剩一個小時
pA還是一直想不出數學公式，決定跑去撈DE的子題
看到pD 33分的子題(存在一個$g_i(x)$為一次多項式)
突然有點心動
於是又去上個廁所想說可以想到什麼
結果廁所的魔力沒了qqqq

眼看時間不多
我決定邊實作邊想作法
結果卻卡住了，原因：
若$ax = b$則$x = \frac{b}{a}$
可是$\frac{b}{a}$可能是分數欸...這樣要怎麼辦...?
然後...就沒有然後了，又浪費了40分鐘QwQ

剩下20分鐘，開始火力全開寫pE的子題
結果15分鐘後bfs是寫出來了，可是我發現我對題目理解錯誤...
因為他們又發公告要改題目然後我沒看到._.

剩下5分鐘，靜坐，然後系統就關掉了

## 賽後
1. 突然知道為什麼pD卡住
因為我忘記這是同餘方程QwQQQQQ
所有東西都是在模運算底下做的，根本不會有我想到的問題啊啊啊
應該是
$ax \equiv b (mod p)$
$x \equiv b \cdot a^{-1} (mod p)$
$a^{-1} = a$的模逆元
所以做個模逆元就可以了啦qwqqq我在幹嘛
(不過就算是這樣我應該也還是會debug到崩潰)
(實作能力真的有待加強)

2. 跟其他人討論後，發現pA其實可以$O(2 * nm)$ DP
我被$n, m$的範圍騙去想數學的解QAQ
(數學是解之一，但是我排列組合真的爛到爆炸)
感謝盧沛宏的教學<(_ _)>