一念行空の幻想空間

摘要： 可以說幾百年沒去練過的東西了。但事實證明還挺有用的。 Meet in the Middle 以前一直沒想通過雙向搜索是怎么優(yōu)化復(fù)雜度的。 例題 1 我稱其為合法子集計數(shù)問題。 雙向搜索就是把集合劈成兩半，兩邊分別枚舉子集，然后再記兩兩匹配的合法關(guān)系。 當(dāng)后者可以快速統(tǒng)計時，雙向搜索就優(yōu)化了復(fù)雜度。 閱讀全文

摘要： 差分約束 處理一類不等式限制諸如 \(x_i - x_j\le c_{i,j}\) 的限制。 移項過后就是 \(x_i\le x_j+c_{i,j}\)，與最短路的松弛類似。于是建圖，連邊，然后跑最短路，有負環(huán)就退出。不保證有解的情況下使用 SPFA，否則使用 Dij。 同余最短路 同樣是將一類問題 閱讀全文