因為沒甚麼在用這個了，也比較喜歡 hackmd 的 markdown 語法，所以移動到了這裡 :

https://hackmd.io/@r1cky/Sk2hKzga6

希望大家繼續關注，謝謝!

(繼續閱讀...)

En Chi Tsung 發表在 痞客邦 留言(0) 人氣()

  • 個人分類：
▲top

AtCoder Beginner Contest 255 pG - Constraint Nim 解題心得 (題目)

解題概念: grundy number

解題方法:這題如果去掉限制，就是一個經典的 Nim 問題，我的解題策略和原本一樣，是求出 grundy number，和本來的 nim 差在被限制的地方需要少轉移 ，可以用離散化的方式算出，求出後再 xor 起來，時間複雜度為 O((N+M)log(N+M))。

Java solution code: 
https://atcoder.jp/contests/abc255/submissions/41875338
(繼續閱讀...)

En Chi Tsung 發表在 痞客邦 留言(0) 人氣()

  • 個人分類：
▲top

AtCoder Beginner Contest 288 pE - Wish List 解題心得 (題目)

解題概念: 2d DP

解題方法:這題的解題策略是利用動態規劃(DP)，發現一個性質是如果先拿掉後面的其實不會影響到前面的cost，所以我們的狀況可以定義成 dp[i][j] =做到第 i 個時的時候拿了 j 個物品，透過區間最小去選順序，求區間最小的方法用建表就可以，時間複雜度為O(N^2)。

Java solution code: 
https://wtools.io/paste-code/bJ8e
(繼續閱讀...)

En Chi Tsung 發表在 痞客邦 留言(0) 人氣()

  • 個人分類：
▲top

AtCoder Beginner Contest 256 Ex - I like Query Problem 解題心得 (題目)

解題概念: SGB(Segment Tree Beats, 吉老師線段樹)

解題思路(要看解法的讀者可略過):一開始想到的是線段樹+懶標，但操作一就讓我停止了這個想法，接著想到利用莫隊的離線演算法來實現，但是區間這兩種操作還是很難搞定，加上這樣時間複雜度至少是O(N.sqrt(Q))，也許因為需要甚麼資結後面再多個log之類的(?，雖然這題有8s，但感覺就不可能過。

解題方法:這題的解題策略就是類似使用線段樹+懶人標記，只是因為這題的操作1並沒有一個規律性，沒辦法直接用懶人標記達成效果，但這裡可以使用的是Segment Tree Beats，就是我們暴力執行操作1，但是記得做到一塊數字都一樣的節點就停止，這裡看似時間複雜度會退化成O(NQ)，但是因為操作1有個性質: 做最多 log A_i 次 (約等於17)全部數字都會變成1，所以其實時間複雜度會接近於O(NlogN+QlogNlogA)，因此能通過。

Java solution code:
(繼續閱讀...)

En Chi Tsung 發表在 痞客邦 留言(0) 人氣()

  • 個人分類：
▲top

AtCoder Beginner Contest 268 Ex - Taboo 解題心得 (題目)

解題概念: AC自動機 (Aho-Corasick Automaton)

解題方法:這題的解題策略其實不難，主要是先推得出一個貪心的想法，只要找到完整的字串就把最後一格畫上*號，這樣greedy會是好的，而找字串的地方直接暴力或是用KMP的話複雜度不夠好(考慮到這題可能會有很多字串)，這裡可以使用 AC自動機 ，時間複雜度為 O(26*sum+N+sum)。

Java solution code: 
https://wtools.io/paste-code/bEUb
(繼續閱讀...)

En Chi Tsung 發表在 痞客邦 留言(0) 人氣()

  • 個人分類：
▲top

ZeroJudge i629 - 序列操作問題  解題心得 (題目)

解題概念: Trie

解題方法:首先最直觀的方法是直接暴力，但那樣是O(N^2)，這題N = 2*10^5顯然不會通過，所以要想想別的方法。

可以發現這題前面的三個操作似乎用類似 set 的資料結構就可以完成，但是這裡需要 xor ，我們可以把數字轉成二進位，並把他視為一個序列，用 trie 來儲存，使用 trie 的話，對於被  xor 1的那個 bit，就等價於把兩個子節點交換，而我們可以透過維護子樹大小來查詢，最終時間複雜度為O(NlogC)。

給讀者額外的挑戰:  N<=80000、把題目操作4改成"and"，其他不更動，那要怎麼做呢? (提示:O(N^2)的話大概會炸)

(繼續閱讀...)

En Chi Tsung 發表在 痞客邦 留言(0) 人氣()

  • 個人分類：
▲top

CodeForces Round 782. pC  解題心得 (題目)

解題概念:掃描線

解題方法:聽說這題可以三分搜，不過其實從左到右掃過去一次即可。

Java solution code: 
https://wtools.io/paste-code/bDNU
(繼續閱讀...)

En Chi Tsung 發表在 痞客邦 留言(0) 人氣()

  • 個人分類：
▲top

CodeForces Round 805 pG2. Passable Paths  解題心得 (題目)

解題概念:Heavy-Light Decompositon 

解題方法:題目要求的就是檢查集合他們是否在同個路徑，可以把他轉成要求樹上區間sum的問題(因為如果點全部在一條路徑上，就代表應該要有一組(x,y)他的那條路徑加起來等於集合點的數量，枚舉有O(N^2)個，但是因為樹的性質代表一個可以選最低點(dfs較深的)，枚舉變成N個，利用Heavy-Light Decompositon每次查詢為O(logNlogN)

Java solution code: 
https://wtools.io/paste-code/bDtG
(繼續閱讀...)

En Chi Tsung 發表在 痞客邦 留言(0) 人氣()

  • 個人分類：
▲top

ZeroJudge i510 尋找子字串 解題心得 (題目)

解題概念:KMP

解題方法:利用KMP演算法尋找，時間複雜度O(N)

Java solution : https://paste.ofcode.org/wvmWhs8SSGTjdNMM9vNfpM
(繼續閱讀...)

En Chi Tsung 發表在 痞客邦 留言(0) 人氣()

  • 個人分類：
▲top

ZeroJudge h901 電橘子與電耗子 解題心得(題目)

解題概念:二分搜、二分圖匹配、匈牙利演算法

小故事:第六屆簡單的小競賽是我參加第一次becaido的小競賽，理所當然的被打爆，只解出很模板的pC，當時和朋友花了很多時間在解這題，但由於圖論知識不足，一直在原地打轉。最近剛好翻到這題，想說花點時間想一下，馬上就有了突破，也順利AC，算是彌補了當時的遺憾。

解題方法:其實和i179有點像，就是二分圖匹配，但是這題的概念也很像g598，就是可以二分搜最小cost，每次對於可使用(低於mid)的邊們做二分圖匹配，看能不能配好。

Java solution : https://hackmd.io/@r1cky/ByL9GIl95
(繼續閱讀...)

En Chi Tsung 發表在 痞客邦 留言(4) 人氣()

  • 個人分類：
▲top

AtCoder Beginner Contest 247 G - Dream Team  解題心得(題目)

解題概念:Min cost flow

解題方法:本來是max flow，加個負號，變成min cost，可使用SPFA找最短路徑(這題無負環不會worst case)，所以時間複雜度是好的。

//Author:En Chi Tsung(欉恩祁)
//Date:2022/06/22
(繼續閱讀...)

En Chi Tsung 發表在 痞客邦 留言(0) 人氣()

  • 個人分類：
▲top

AtCoder Regular Contest 142 C - Tree Queries 解題心得(題目)

解題概念:樹

解題方法:首先利用2n-4個查詢得到1、2和其他點的距離，接著利用這些資訊討論答案。

//Author:En Chi Tsung(欉恩祁)
//Date:2022/06/22
(繼續閱讀...)

En Chi Tsung 發表在 痞客邦 留言(0) 人氣()

  • 個人分類：
▲top
1 2 3 4 5
Blog Stats
⚠️

成人內容提醒

本部落格內容僅限年滿十八歲者瀏覽。
若您未滿十八歲，請立即離開。

已滿十八歲者，亦請勿將內容提供給未成年人士。