szhqwq's blogs

摘要： CF1610E AmShZ and G.O.A.T. 最少刪除元素個數轉化為最多保留元素個數。考慮不合法序列的性質。 發現嚴格大于平均數的元素個數與嚴格小于平均數元素個數的關系可以與該序列中點位置的數聯系在一起，顯然的，對于 \(\{c_k\}\)，該序列是不合法的，則有 \(c_{\left \l 閱讀全文

摘要： 倍增優化 floyd。 常見可以解決限制經過有限數條邊的最短路問題。 構造初始矩陣，矩陣上 \((u,v)\) 表示點 \(u\) 到點 \(v\) 有一條權值為 \(w\) 的邊，即 Floyd 中的 \(f\) 數組。 將進行一次矩陣乘法后的矩陣拿來繼續平方，每次得到的是經過 \(2^k\) 的 閱讀全文

摘要： 0.前言 去年 10 月底學了一遍，當前再次學習并記錄。 wqs 二分，也稱帶權二分，一般用于優化決策單調性優化 DP。 1.wqs 二分 對于此類問題：給定 \(n\) 個物品，現要求將其分為 \(m\) 段，每段存在相應的代價 \(w\)，求代價最值。 如果沒有限制段數，可以考慮使用決策單調性優 閱讀全文

摘要： 中考完了，兩個月沒碰電腦，那我問你，是不是殘廢了。 6.20 ~ 7.24 還上綜合，上七休零，都放暑假了還 7:00 ~ 10:30，你要赤石嗎。 CQ 40多度還不放高溫假，你要燒烤學生嗎。 這五周也沒干個啥，接下來就做做題單，做做 CF。 從 2025.7.28 起開始詳細記錄 CF 做題情況 閱讀全文

摘要： 0.前言 若干年前會過一次，然后就不會了。 現在又會了。 1.虛樹 存在這樣一類問題，多次詢問，每次給你 \(k\) 個特殊/關鍵點，要求有關這 \(k\) 個點的某種信息，并且題目保證了或隱含了 \(\sum k \le lim\)，那么可以考慮使用虛樹解決。 虛樹，即將這 \(k\) 個點提出， 閱讀全文

摘要： dsu on tree. 樹上啟發式合并 對于一個點 \(u\)，需要計算其子樹內的答案。 先遍歷 \(u\) 的輕子樹并計算其答案，計算答案過程中會統計一些信息，不保留其信息。輕子樹計算完后進入重子樹計算答案，并保留其信息。 然后對于以 \(u\) 為根的子樹，再次遍歷其輕子樹并加入答案。若 \( 閱讀全文

摘要： 0.前言 這種東西不知道是怎么發明出來了的。感覺很 nb。 但是應該比 KMP 簡單些吧。 oi-wiki 1.概念 SAM，即后綴自動機，是對于一個字符串 \(s\) 來說能夠表示其所有子串/后綴的 DFA。實際上 SAM 是一個 DAG，上面有若干點代表若干狀態，其中有一個初始狀態 \(t_0\ 閱讀全文

摘要： 0.前言 參考文獻：胡伯濤《最小割模型在信息學競賽中的應用》 本文總結了上書最大權閉合圖一章節核心內容及其應用。如有錯誤請指出。 1.最大權閉合圖 對于有向圖 \(G = (V,E)\) 的一個子圖，如果其點集 \(V_1\) 中點的后繼都還在 \(V_1\) 中，則稱其為原圖的一個閉合圖。 而最大 閱讀全文

摘要： 經典題。 \(\tt{Link}\) 題意 你手中有 \(n\) 張牌。每張牌上都寫著一個介于 \(1\) 和 \(m\) 之間的整數。要贏得游戲，需要組成一定數量的三元組。每個三元組由三張牌組成，這樣寫在牌上的數字要么全部相同，要么連續。例如， \(7, 7, 7\) 和 \(12, 13, 14 閱讀全文

摘要： 人類智慧題。harmis_yz 不會。 題意 \(\tt{Link}\) 給定一個序列 \(\{a_n\}\)，可以進行若干次操作，每次可以選擇 \(i,j(1 \le i < j \le n)\)，將 \([i,j]\) 之間的數全部變為 \(|a_i - a_j|\)，問進行若干次操作后序列之和 閱讀全文