needna

摘要： 題意： 給定一棵 \(n\) （\(n\le 5\times 10^5\)）個點的樹 一下給出 \(m\) 條路徑（以\(u\to v\) 形式） 第 \(i\) 條路徑要求詢問前 \(i-1\) 條與他有多少相交的（點相交即為相交） 題解 妙題 考慮怎么計算答案，我們分類討論： 1.之前路徑的 l 閱讀全文

摘要： 題意： 有一棵 n 個節點的無根樹（\(n\le 1.6\times 10^5\)），樹上第 i 個節點有一個正整數 \(A_i\) 作為點權。有趣的是，這棵無根樹度數為 1 的節點不超過 10 個。 請求出一條樹上的路徑，使得路徑上包含的節點個數乘以路徑經過點權的最大公約數最大。 題解： 方法一： 閱讀全文

摘要： P5339 [TJOI2019] 唱、跳、rap和籃球 很好的一道題，先考慮容斥至少有 i 個討論cxk的組，然后你發現你缺了一個剩下人的組合數 現有一個樸素的方法，就是分別枚舉有 i 個人在做第一個運動，j個在做第二個運動…… 這是一個n^4方的，可以用前綴和優化到 n^3 現在有一種用meet- 閱讀全文

摘要： 我主要想搞好的方面 比賽中的觀察/思維能力 (1 對題目的見識 (2 彌補自己的短板 (3 能熟練運用/實現自己應該會的題 (4 對此的idea 刷題結合自己能力： 1.找到大量 (1),(2),的藍即以下題目(和新的比賽題，創新題)。 2.找到大量 (3),(4),難題/典題/大佬做過或寫過題解的 閱讀全文

摘要： 簡單貪心題（greedy） 注意：題面有誤，應該為 \(n+1\) 層樓，否則數據有誤，但題解中視為一共有 \(n\) 層樓的情況。 題目描述 你有 \(k\) 個一模一樣的雞蛋，一共有 \(n\) 層樓，雞蛋有一個碎裂值 \(x\)。代表在超過(包含) \(x(1\leq x\leq n)\) 層 閱讀全文

摘要： usaco24openG2. Grass Segments 題意 有一些區間 \([l_i,r_i]\)，現在每一個區間有一個值 \(k_i\)。 對每一個區間詢問：和這個區間重合了超過長度 \(k\) 的區間有多少個。 題解 我們考慮抽象化對重合的表達，設現在有兩個區間 \([l_i,r_i]\) 閱讀全文

摘要： t1 火車站 貪心，題意是：有一堆二元組，你可以把它分成很多組，滿足每一組有有 \(a_i>a_{i+1}\) 和 \(b_i<b_{i+1}\)，問最少能分成多少組。 我們按照 \(b_i\)排序，然后答案就是最長上升子序列（lis）。 t2 Desire 神題。我們先考慮對每個點枚舉，發現會有重 閱讀全文

摘要： t1 騎行 運氣比較好，想到了 kruskal重構樹，然后就想到了從小到大枚舉點，然后計算貢獻，這下就簡單了（主要是做過類似的題 也是先對點排序然后計算相鄰點貢獻，那道題是對聯通快做主席樹然后線段樹合并做這道題）。 t2 有向圖刪點 比較巧妙，我們把所有點拍到序列上，一個點會被計入貢獻當且僅當其所有 閱讀全文

摘要： t1 分蛋糕 打表題，我用了 25 min 來發現規律，發現是組合數就寫完了。 t2 膜法 這一道是原題，用插頭 dp 中的經典優化 就寫完了。 t3 木棍 分類討論 分成 \(3~1~1~1\) 和 \(2~2~1~1\) 兩種情況，都能枚舉得到答案 t4 計數 高妙題，首先我們把限制當成一條 \ 閱讀全文

摘要： \(A~xor ~B=C~xor~D\to A~xor ~C=B~xor~D\to A~xor ~C~xor~D=B\) 閱讀全文