生活 x 程式筆記

Difficulty:

⭐️⭐️⭐️

🌟 滿喜歡這題，給他 special 星

# Problem Description 題敘:

Link

給一個單向圖，有 $N$ 條邊，以及 $M$ 個點，每造訪一個點有 $\large s_i \in \mathbb{N}$ 的美麗值，每造訪一個道路也有 $\large w_{u \longrightarrow v} \in\mathbb{N}$ 的美麗值。

可任選一個景點出發並停留在任意可以抵達的點，若採取最佳的策略，求可以得到總和多大的美麗值。

請注意，重複造訪某個已經到過的點或道路並不會得到額外的任何美麗值。

<br/>

$N,M(1\le N\le 5\times 10^5,0\le M\le 5\times 10^5)$

$s_1,\cdots,s_N(0\le s_i\le 10^9)$

$u_i,v_i,w_i(1\le u_i,v_i\le N,u_i\ne v_i,0\le w_i\le 10^9)$

Difficulty:

⭐️⭐️⭐️

# Problem Description 題敘:

謠言問題 Link

給你一張無向圖，有 $N$ 個點以及 $M$ 條邊，再給定一個點 甲，甲 在收到消息後會傳給跟他有邊關係的點，而得到消息的點 也會把消息繼續傳播給跟他有關係的點，要求你選定一個點 乙 ，使得最後傳遞到消息的人數最少。乙 若收到消息便不會再繼續傳遞下去。

# 輸出:

請輸出 乙 的編號以及最後獲得消息的人數。若不管有沒有選擇 乙，最後會的知消息的人數皆相同，那麼請輸出 $0$.

Difficulty:

⭐️⭐️⭐️⭐️

# Problem Description 題敘:

Link

Easy Version - Link (單調對列優化)

1. 由下而上給你 $n$ 隻烏龜，你可以挑選一些烏龜，把他們融合起來成一隻，如此，他們的違和度也會相加。
2. $x$ 個烏龜合出的大烏龜會有強度 $x$ 的違和光芒。(斜率優化版才有)
3. 一隻違和度 $c$ 的烏龜如果放在烏龜塔的第 $m$ 層 ，看起來會有 $c\times(m-1)$ 的違和度。(層 = 融合後，由下而上的數第 $m$ 隻烏龜)
4. 烏龜塔的違和度是所有烏龜的違和度減掉所有違合光芒的強度。(斜率優化版才需考慮光芒)
5. 為了避免烏龜塔太矮，每個要融合的連續區段不能包含超過 $k$ 隻烏龜。

• 簡易版與困難版唯一的不同就是 "光芒的有無"。

Difficulty:

TCGS-b027: ⭐️⭐️

T​IO​J-1603: ⭐️⭐️⭐️

# Problem Description 題敘:

TCGS-b027 Link
TIOJ-1063 Link

兩題類似題，放在一起。

TCGS-b027: 給一個二維陣列，求全部由 $0$ 組合成的正方形區域的最大面積有多少？

TIOJ-1063: 給一個二維陣列，求全部由 $1$ 組成的最大矩形面積有多少？