CuteNess

摘要： 251104A. 圖 給定一個 \(n\) 個點的完全無向圖，求給每條邊定權(quán)在 \([1,V]\) 內(nèi)的方案數(shù)，使得點 \(1\) 到點 \(n\) 的最短路長度等于 \(k\)。對非質(zhì)數(shù)取模。 \[1\le n, k\le 13, 1\le V\le 10^9 \] 考慮按 \(1\) 到 \(x 閱讀全文

摘要： 基環(huán)樹學習筆記 往一個樹上額外添加一條邊，稱得到的圖為基環(huán)樹。 基環(huán)樹點數(shù)和邊數(shù)相同，但是點數(shù)和邊數(shù)相同的圖不一定是基環(huán)樹。 另外，滿足以下性質(zhì)的圖是基環(huán)森林（當聯(lián)通時是基環(huán)樹）： 每個點有且僅有一條出邊，這時候稱得到的圖為外向基環(huán)森林。 每個點有且僅有一條入邊，這時候稱得到的圖為內(nèi)向基環(huán)森林。 對 閱讀全文

摘要： 山月記 給定 \(n\) 個點，\(m\) 條邊的圖 \(G\) 和他的一個生成樹 \(T\)。圖 \(G\) 可能有多個最小生成樹。 詢問是否存在一個點 \(x\) 使得 \(T\) 上所有以 \(x\) 為端點的路徑 \(p\)，至少存在一個最小生成樹包含 \(p\)。 \[n-1\le m\l 閱讀全文

摘要： qoj14457. 缺陷解碼器 有一初始為空的字符串 \(S\) 和大小為 \(m\) 的字符集 \(C\)，一直執(zhí)行以下操作： 從 \(C\) 中隨意一個字符，接在 \(S\) 后面。 分別令 \(S_1,S_2\) 表示 \(S\) 的 前/后 \(\lfloor\frac {|S|}2\rfl 閱讀全文

摘要： qoj14458. 調(diào)色濾鏡 平面 \([1,10^9]\times[1,10^9]\) 上有 \(n\) 個點，點 \(i\) 位于 \((x,y)\)，有顏色 \(c_i\in [0,9]\)。 有 \(q\) 次操作，每次對平面上一個矩形范圍內(nèi)的點的顏色作用映射 \(f:[0,9]\right 閱讀全文

摘要： qoj14453. 網(wǎng)絡(luò)改造 給定一個 \(n\) 個點 \(m\) 條邊的有向圖，你可以： 以 \(a_i\) 的代價翻轉(zhuǎn)一條邊。 以 \(b_i\) 的代價刪去一條邊。 以 \(c_i\) 的代價刪去一個點。 無自環(huán)無重邊，問至少需要多少代價將這個圖變?yōu)闊o環(huán)圖？ \[n\le 22 \] 首先是 閱讀全文

摘要： 251025B. 海嘯 有 \(n\) 個物品，物品 \(i\) 有 \(v_i\) 的價值和 \(2^{w_i}\) 的體積。 以及 \(q\) 次修改，每次給出 \(x\) 并令 \(a_x \leftarrow a_x +1\)。 每次修改后求出當總體積 \(\le V\) 時的最大總價值。 閱讀全文

摘要： 給定一顆無根樹 \(|T|\)。 求兩條點不相交的路徑，使得兩條路徑上邊權(quán)的異或和加起來最大。 \[|T| \le 3\times 10^4 \] 這是一個經(jīng)典 trick: 對于求兩條點不相交路徑，我們可以枚舉點 \(x\)，使得其中一條在 \(x\) 的子樹內(nèi)，另外一條在 \(x\) 的子樹外。 閱讀全文

摘要： Pólya 定理學習筆記 | ABC428G 題解 用來對在若干置換下本質(zhì)不同的方案數(shù)計數(shù)。 （這里會有一些對引理和定理的證明，但是先咕掉（（ 首先是 Burnside 引理： 結(jié)論是，假設(shè)群 \(G\) 作用于集合 \(X\) 上。 令 \(O_x\) 表示 \(x\in X\) 的軌道，即 \( 閱讀全文

摘要： 廣義串并聯(lián)圖定義為不包含同胚于 \(K_4\) 的子圖的圖。 平面圖要求不包含同胚于 \(K_5\) 的子圖，所以平面圖不一定是廣義串并聯(lián)圖。 換句話說，不存在四個點滿足兩兩之間都存在邊不相交的路徑相連。 廣義串并聯(lián)圖的性質(zhì)是，我們可以通過 廣義串并聯(lián)圖方法 將他縮成一個點。 具體來說，有三種不同的 閱讀全文