摘要：
update 2024/12/28 題目描述 給定一棵樹，每次詢問區間 \([l,r]\) 的 \[\max_{l \le l' \le r' \le r \land r' - l' + 1 \ge k}\text{dep}_ {\text{LCA*}(l', r')} \]引理證明 先來證兩個區間 閱讀全文
posted @ 2025-01-18 17:34
keysky
閱讀(213)
評論(0)
推薦(1)
摘要：
傳送門 前言 本題是筆者keysky與同學yangbaich討論+推式子一整個晚上以及討論前ybc的一整個下午做出來的，綜合起來是 \(34\) 個轉移方程，對于整道題來說，貢獻大抵為我 \(2\) 他 \(8\) 。 我們的做法不一定是最優解，甚至可以說是較劣且復雜的，但時間是穩定能過且沒卡常的， 閱讀全文
posted @ 2025-01-17 21:17
keysky
閱讀(32)
評論(0)
推薦(0)
摘要：
題目大意 給定一顆 \(N\) 個節點以 \(1\) 為根的有根樹，每次給以 \(u\) 為根的子樹每點加 \(1\) 的值或給路徑 \(u - v\) 上每點加 \(1\) 的值，每次修改后查詢一個點 \(u\) 使得 \(\sum_{v = 1}^N dis(u, v)\) 最小。 題目轉換 首 閱讀全文
posted @ 2025-10-28 21:34
keysky
閱讀(10)
評論(0)
推薦(0)
摘要：
題目大意 給定一個序列，定義其權值為劃分序列的方案數，使得劃分出來的每個區間 \([l, r]\) 有 \(\max_{i = l}^r {a_i} \leq r - l + 1\) 。對于每個 \(1 \leq i \leq n\) 求只將 \(a_i\) 修改為 \(1\) ，序列的權值。 做法 閱讀全文
posted @ 2025-10-27 17:01
keysky
閱讀(6)
評論(0)
推薦(0)
摘要：
思路&做法 先將題目變換一下，對于每個卷軸 \((r_i, b_i) \leftarrow (n - r_i, m - b_i)\) ，要求從 \((0, 0)\) 走到 \((n, m)\) 的所有路徑的權值之和除以 \(\binom{n + m}{n}\) 。 設路徑 \(p\) 經過的卷軸依次 閱讀全文
posted @ 2025-08-18 22:25
keysky
閱讀(16)
評論(0)
推薦(0)
摘要：
題目大意 求長度為 \(N\) 的排列使得 \(\sum_{i = 1}^{N - 1} |A_{p_{i + 1}} - A_{p_i}| \leq L\) 有多少個，對 \(10^9 + 7\) 取模。 \(1 \leq N \leq 100\) ，\(1 \leq L, A_i \leq 10 閱讀全文
posted @ 2025-08-13 21:43
keysky
閱讀(12)
評論(0)
推薦(0)
摘要：
題目大意 給定一棵 \(N\) 個點的無根樹，對于所有 \(1 \leq k \leq M\) 求出滿足以下條件的點集 \(S\) 個數。 \(\forall u, v \in S\) ，\(u\) , \(v\) 在樹上不相鄰 \(\sum_{u \in S} a_u = k\) \(\sum_{ 閱讀全文
posted @ 2025-08-12 22:10
keysky
閱讀(25)
評論(0)
推薦(0)
摘要：
「ABC 406 G」Travelling Salesman Problem 前言 本題筆者使用了兩種方法來做，一是 \(\text{Slope trick}\) ，二是線段樹，皆有講解，各位讀者按需食用。 準備工作 對于該題，我們首先會有一個 \(O(NV^2)\) 的暴力 \(\text{dp} 閱讀全文
posted @ 2025-06-09 21:27
keysky
閱讀(30)
評論(0)
推薦(0)
摘要：
/* address://codeforces.com/problemset/problem/407/E AC 2025/2/4 20:18 */ #include<bits/stdc++.h> using namespace std; const int N = 1e6 + 5; in 閱讀全文
posted @ 2025-02-12 11:36
keysky
閱讀(38)
評論(0)
推薦(0)
摘要：
題目概述 給定 \(a, b, n\) ，\(a, b \in \{0, 1, 2, 3\} ，n \leq 10^{12}\) ，求 \[(\sum_{i = 1}^{n} \sum_{d|n} d^a \oplus \sum_{i = 1}^{n} \sum_{d|n} d^b) \]思路&&做 閱讀全文
posted @ 2025-02-08 15:33
keysky
閱讀(12)
評論(0)
推薦(0)
摘要：
題目概述 對一棵樹維護兩種操作：翻轉某個點的顏色，求 \(max\{ dist_{u, v} \}\) 且滿足 \(u\) 的顏色和 \(v\) 的顏色都是白色（ \(u,v\) 可以相同）。 思路 首先考慮若沒有修改，給定帶顏色的 \(N\) 個點怎么查詢。 經典辦法是樹形 \(\text{dp} 閱讀全文
posted @ 2025-01-23 17:39
keysky
閱讀(101)
評論(0)
推薦(4)
摘要：
題意描述 有 \(N\) 座城市，第 \(i\) 座坐標為 \(a_i\) ，有 \(M\) 輛卡車，第 \(i\) 輛卡車要從城市 \(s_i\) 前往城市 \(e_i\) ，每單位長度耗油量為 \(c_i\) ，可以在中途城市加滿油 \(r_i\) 次，求讓所有卡車都能到達目的地最小的油箱容積。 閱讀全文
posted @ 2025-01-21 12:56
keysky
閱讀(21)
評論(0)
推薦(0)