---
title: SWERC 2021-2022 紀錄
tags: solo, ICPC
---
# SWERC 2021-2022

慘..

[statement](https://codeforces.com/contest/1662/attachments/download/15998/problemset.pdf)

## pA solved - 00:04

開個陣列$arr$維護每個difficulty的max beauty即可
如果沒有某個difficulty的題目則無解, 否則輸出$sum(arr)$

## pD upsolved

觀察1: 在操作前後, 每種字出現次數的parity都不變

觀察2: 因為所有操作都是可逆的, 所以可以檢查$u, v$能不能變成某個字串$s$即可

觀察3: 對於字串"AB", 可以變成"AABABB"再變成"BA", 即'A'和'B'的相對順序是可以任意改變的, "BC"同理

解法: 先判掉parity不同的狀況, 接下來把$u, v$中的'B'全部刪掉, 再看$u, v$的bracket sequence是不是一樣即可

## pF upsolved

觀察: 以一個源點$i$去看可以往左走到哪些點(往右同理), 可以發現只需滿足

$$j + p_j \ge i, i - p_i \le j < i$$

所以可以開兩棵RMQ線段樹分別維護$j + p_j, j - p_j$, 在BFS時, 不斷查詢區間$[i - p_i, i), (i, i + p_i]$直到沒有新的點可以走, 因為每次找到新的點的時候才會多query一次, 總體複雜度是$O(nlgn)$

## pH solved - 00:38

bitmask枚舉每個角落應該屬於哪條邊上就好了

## pI solved - 03:13

裸的帶權線段交集, 可以用掃描線$O(mlgm + nlgn)$做掉

ps. 賽中卡半天才發現丟進set的東西會重複, 要開multiset...

## pL upsolved

觀察1: 如果要從$a_j$轉移到$a_i$的話, 要滿足

$$|a_i - a_j| \le (t_i - t_j)v$$

拆絕對值後會變

$$t_i v - a_i \ge t_j v - a_j \text{ if } a_i \ge a_j \\t_i v + a_i \ge t_j v + a_j \text{ if } a_i < a_j$$

因此對於一個合法的序列, $t_i v - a_i$, $t_i v + a_i$和$t_i$都要是非嚴格遞增的

觀察2: 觀察到$t = \frac{(tv - a) + (tv + a)}{ 2v}$, 所以當$t_i v - a_i$和$t_i v + a_i$是非嚴格遞增時, $t_i$一定是非嚴格遞增

解法: 所以可以對$t_i v + a$ sort, 把起點走不到的點刪掉後找LIS即可, 總體複雜度$O(nlgn)$

## pM solved - 00:18

當$max(r_i) + max(w_i) > n$時明顯無解, 然後只要連續放$max(r_i)$瓶紅酒再連續放$n - max(r_i)$瓶白酒就可以滿足所有的條件

## pO upsolved

首先對半徑離散化(假設離散化之後剩$m$個座標), 然後把圓形迷宮切成$360$等分的$m + 1$個圓環, 再好好維護牆壁的位置, 做Flood Fill即可, 總複雜度$O(nlgn + 360n)$

## 檢討

賽中在pD跟pI分別卡了快兩個小時, upsolved完之後發現有些題目其實我是會做的, 可是就因為在那兩題耗太久導致根本沒時間去看別題, 下次要記得不要卡在同一題太久, 差不多半個小時沒什麼想法的話就要交互想想看別題了