---
title: NERC 2021-2022 紀錄
tags: solo, ICPC
---
越打越爛, 怎麼會這樣...

[statement](https://codeforces.com/contest/1666/attachments/download/15867/nerc2022-statements.pdf)

## pC solved - 00:49

按照x座標sort, 如果y座標沒有逆序就連$point_1 -> point_2 -> point_3$, 否則就從$(point_2.x, yMid)$連到三個點

## pD solved - 00:32

倒著找subsequence, 如果$t$不是$s$的subsequence或遇到一個字元$X$可以match $t$但不是第一個還沒match到的字元則無解

## pF upsolved

observation1: 由上往下考慮偶數項$b_{2i}$的時候, 可以發現小於等於$b_{2i}$的數字在之後都只能放在奇數項, 且一定可以放在奇數項

解法(偽): 考慮$dp[n][last]$代表當前最後一個偶數項的值是$n$, 小於等於$n$且還沒被用到的數字有$last$個, 每次轉移的時候從$last$裡面拿一個數字放在奇數項, 再枚舉下一個偶數項的值, 總體複雜度會是$O(n^3)$, 顯然不夠快

因此我們試著改變一下dp的定義, 如果能變成把數字從小到大考慮的話, 轉移的時間應該會變$O(1)$, 所以我們可以得到以下的dp狀態

$dp[n][last]$代表考慮數字$1$到$n$, 小於等於$n$且還沒用到的數字有$last$個, 當我們從$dp[i]$轉移到$dp[i + 1]$的時候, 要馬把$i + 1$放在下一個偶數項, 要馬不放, 留著給奇數項使用

可是這樣轉移的話, 在放奇數項時需要知道前一個偶數項是多少, 似乎不太好做, 所以我們試著修改一下放東西的方式

observation2: 在由上往下放東西的時候, 如果同時放$b_{2k}, b_{2k + 1}$的話, 就不用知道前項的資訊了

解法:

由於$max(a_i)$只能放在最後一項, 所以我們先把$max(a_i)$拔掉, 如果有出現兩個以上的$max(a_i)$就無解, 且先決定$b_1$應該要放誰(這會是dp的base case)

$dp[n][last]$代表考慮數字$1$到$n$, 小於等於$n$且還沒用到的數字有$last$個的fancy stack種類數, 並定義$cnt(i)$是數字$i$在$a$中出現的次數

至於算組合數的方式, 可以發現只有奇數項會有重複數字, 所以可以在每次考慮數字$i + 1$時, 除上$i + 1$在奇數項的個數, 且每次放奇數項的時候乘上$last$

那我們會有以下的base case

$$dp[i][\sum_{j = 1}^{i} cnt(j) - 1] =
\begin{cases}
\frac{1}{\prod_{k = 1}^{i - 1} cnt(k)!} & \text{ if } cnt(i) > 0 \\
0 & \text{ else} \\
\end{cases}$$

以及以下的轉移式

\begin{cases}
dp[i + 1][j + cnt(i + 1)] \mathrel{+}= \frac{dp[i][j]}{cnt(i + 1)!} & \\
dp[i + 1][j + cnt(i + 1) - 2] \mathrel{+}= \frac {dp[i][j] * j}{(cnt(i + 1) - 1)!} & \text{ if } j > 0 \text{ and } cnt(i + 1) > 0\\
\end{cases}

看起來可能有點恐怖, 不過只是上面的概念加上一點排組而已, 最終答案是$dp[n][0]$, 總體複雜度$O(n^2)$

## pI upsolved

假設兩個寶藏的$x$座標分別是$r_1, r_2(r_1 \le r_2)$, $y$座標是$c_1, c_2(c_1 \le c_2)$, 那在知道這四個變數之後, 至少要花3次的query才能做完(有可能是放在$(r_1, c_1), (r_2, c_2)$或是$(r_1, c_2), (r_2, c_1)$), 所以我們只有4次$SCAN$的機會, 而每次$SCAN$會得到一組方程式, 所以我們只要弄出4個independent的方程式就做完了

我是選擇$SCAN(1, 1)$和$SCAN(1, m)$可以得到$r_1 + r_2$以及$c_1 + c_2$, 接下來做$SCAN(\lfloor \frac{r_1 + r_2}{2} \rfloor, \lfloor \frac{c_1 + c_2}{2} \rfloor)$和$SCAN(1, \lfloor \frac{c_1 + c_2}{2} \rfloor)$就可以分別算出$r_1, r_2, c_1, c_2$

最後再$DIG(r_1, c_1)$, 如果有寶藏那剩下的那個就在$(r_2, c_2)$, 否則在$(r_1, c_2)$和$(r_2, c_1)$

## pJ upsolved

寫dp的題解好麻煩, 先開溜

## pL upsolved


## 檢討

我好爛, upsolved完發現那幾題我根本會做, 只是又被前面的題卡住了, 是不是卡題的時候該多開幾題會比較好