推 dannyko: 大師 02/05 00:31
推 pandix: 大師 02/05 01:33
這次又爆炸了
好像只要是剛睡醒的狀態都不太行
https://i.imgur.com/4UlCldZ.png
這次沒有 hard 也能被我搞到破一個小時
太苦了
1. Separate the Digits in an Array
轉成字串再一個一個字元轉回整數
2. Maximum Number of Integers to Choose From a Range I
因為挑比較小的數字一定不會更差
所以可以由小挑到大，看最多能挑幾個
如果遇到在 banned 裡就跳過
我是直接把 banned 轉成 set 來做比較好寫
3. Maximize Win From Two Segments
debug 了好久才發現是沒有更新到目前的最佳解
浪費了 30 分鐘
令 M[i] 是考慮以 1 <= x <= i 的某個值為尾端時，選一次的最佳解
則到 i 為止選兩次的最佳解 ans_i 為
ans_i := M[i-k-1] + (prizePositions 裡 <= i 且 >= i-k 的個數)
用 lower_bound 搜一搜即可
如果想用 two-pass 要考慮好 k=0 的情況
4. Disconnect Path in a Binary Matrix by at Most One Flip
首先我們先把不能形成路徑的挑掉
能形成路徑若且唯若有路能從起點到達且有路能到達終點
把不能形成路徑的挑掉之後
能藉由砍掉一個節點使得到不了的條件是：
所有路徑都會經過這個點
因為對於任意一個點，他和起點的所有路徑的長度都一樣
所以所有路徑都會經過這個點的條件就會是：
用 BFS 時，到這一層時只有他這個節點
所以只要用 BFS 發現某一層的人數 <= 1 即可成功
總覺得有更好的作法就是了
忘了檢查有沒有加入過這個節點吃了一次 penalty
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 140.112.16.175 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1675526424.A.0F9.html