Cyan0826

摘要： 題目：給以一個點 \(Q(x,y)\)，問在一條直線 \(l: y=kx+b\) 的哪一邊。 這個是非常經典的問題，我們只需要在直線上取兩個點 \(F_1(x_1,y_1)\) 和 \(F_2(x_2,y_2)\)，然后求出 \(\overrightarrow{QF_1}=(x_1-x,y_1-y) 閱讀全文

摘要： 這是什么神仙題啊。 本題主要思路：優化轉移決策，減少 dp 狀態。 我們發現減一層盾其實就是給自己加攻擊，所以我們將初始生命值（攻擊力） \(C_H\) 和 \(C_G\) 重新表示為 \(A_1 = C_H - f_G S\)，\(A_2 = C_G - f_H S\)，讓 \(F_1 = f_G 閱讀全文

摘要： 評價：感覺還是過于神秘了，暴力寫的群魔亂舞，正解返璞歸真。 暴力做法太多了，就不記錄了。 我們考慮一個貪心，由于邊權互不相同，我們把邊按照邊權從大到小排序，然后依次嘗試滿足當前邊，這樣顯然是極其優秀的，因為你滿足了當前邊，后面的邊的最小值仍未確定，也就是可以繼續解決的。 而唯一可能影響情況的，就是當 閱讀全文

摘要： Pollard-Rho 還是很容易理解的，其作用就是找一個數 \(n\) 的一個非平凡約數。(非平凡約數即不是 \(1\) 也不是它本身的約數)。 復雜度大致是 \(n^{\frac{1}{4}} \log n\)。 首先引入生日悖論：一年 \(365\) 天，當一個房間中的人數至少為 \(23\) 閱讀全文

該文被密碼保護。 閱讀全文

摘要： 線性基很好理解，可以理解成 \(n\) 維的向量。 我們先考慮 \(n=2\)，這是我們最熟悉的，可以在平面直角坐標系上表示出來。 眾所周知，在一個平面內，兩個不共線的向量 \(e_1\) 和 \(e_2\)，可作為基底，即所有可在原坐標系上表示的向量 \(x\) 均可被 \(e_1\) 和 \(e 閱讀全文

摘要： 耳分解 耳分解能極好地維護連通性問題。 很形象的說法，設最初的子圖為 \(G_0\)，原圖為 \(G_N\)，滿足 \(G_0\) 是一個邊雙連通分量。 每一次加一條“耳”，由圖 \(G_i\) 轉到圖 \(G_{i+1}\)。“耳”就是一條形如 \((x_1 \to x_2 \to x_3...\ 閱讀全文

摘要： 題意：有 \(n\) 個講師，對于講師 \(i\)，他可以在 \([l_i,r_i]\) 中選一天講課，問對于 \(x \in [1,n]\)，有多少連續的 \(x\) 天可以做到都有講師講課。 先考慮區間的 \(l\) 互不相同時如何解決。 對于已知的 \([l,r]\) 是否存在完美匹配，判斷是 閱讀全文

摘要： 1.邊連通度 有向圖： 直接將邊換成流找任意一個點做原點 \(S\)，然后把除了與 \(S\) 相連的點做為匯點 \(T\)，做 \(O(n)\) 遍最大流求最小割即可。 無向圖類似 2.點連通度 有向圖： 將點拆成入點和出點，然后就差不多了。 無向圖類似 代碼常數較大，只作參考 點擊查看代碼 #i 閱讀全文

摘要： 最后的轉化太妙了 題意：一個 \(2n\) 個點的無向圖，判斷將任意 \(n\) 個點染成黑色，另外的 \(n\) 個點染成白色是否都存在完美匹配。 \(N(S)\) 表示與在 \(S\) 這個點集中的點存在連邊且不在 \(S\) 中的點的點集 考慮 hall 定理，取一個大小 \(\le n\) 閱讀全文