摘要： 一、上指標求和 雖然很簡單，但還是寫一下吧，加深印象。 要證明的是 $\sum_{i=0}^n{i \choose k}={n+1\choose k+1}$ $OI\ Wiki$ 給出了提示，往 $n+1$ 個元素中選 $k+1$ 的子集方面想。 枚舉第 $k+1$ 個元素是在第 $i$ 個位置被選 閱讀全文

摘要： 一、題目描述： 給定一個長度為 $n$ 的序列 $B$，和一個長度為 $n-1$ 的序列 $C$。 保證 $b_i>=0$。令$S=\sum_{i=1}^n b_i$。 一個長度為 $n$ 的且 $\sum_{i=1}^n a_i=S$ 序列 $A$ 的代價按照如下計算： 你可以若干次任意選擇一個 閱讀全文

摘要： 一、題目描述： 設 $\pi (x)$ 為全排列 $x$ 的逆序對數。 給定 $n,m$，求有多少對長度為 $n$ 的排列 $p,q$，使得 $p$ 的字典序小于 $q$，且 $\pi (p)>\pi (q)$ 答案對 $m$ 取模。數據范圍：$1\le n\le 500,1\le m\le 10^ 閱讀全文

摘要： 數學還是缺得太多了，今天寫一發二項式定理的證明。 二項式定理：$(a+b)^n=\sum_{i=0}^n{n \choose i}\times a^{n-i}b^i$ 證明： 考慮歸納證明，當 $n=0$ 時，$(a+b)^0=1,{0\choose 0}=1,a^0=1,b^0=1$，顯然滿足。 閱讀全文

摘要： 一、題目描述： 給定一個序列 $A$，$A$ 的每一個元素形如 $+x$ 和 $-$，其中 $x$ 為一個整數（$1\le x< 998244353$）。 對于 $A$ 的一個子序列 $S$，按如下方式計算 $S$ 的權值： 你需要依次遍歷 $S$ 中的元素，并且按照序列維護一個小根堆 $T$。 特 閱讀全文

摘要： \(md\) 怎么今天寫一個題就遇到一個沒學過的知識點？我真的什么都沒學過嗎？？？ 最短路徑樹是一棵樹，滿足 \(dis(u,root)\) 等于在原圖中源點到 \(u\) 的最短路長度。 求這個很簡單，也是直接 \(dij\) 就行了。 但是又要求這棵樹邊權和最小，于是有了一個貪心算法，即時地更新 閱讀全文

摘要： 今天寫一個最短路題邊權為 \(0\) 或 \(1\)，我說這不一眼 \(dij\) 么？結果題解區全部寫的 \(O(n+m)\) 的 \(01bfs\) 。 好家伙我居然一直不知道這么個東西，花了一個小時看會了，寫一下原理。 實現的方法很簡單，就是一個雙端隊列，去 \(nm\) 的 \(deque\ 閱讀全文

摘要： 一、題目描述： 給你一個長度為 $n$ 的序列 $a_1\sim a_n$，$0 \le a_i \le 1\times 10^9$。 現在有 $m$ 次操作，第 $i$ 次操作將位置 $p_i$ 的數變為 $v_i$，$1\le v_i\le 1\times 10^9$。 操作僅對本次有效，并不會 閱讀全文

摘要： 之前我并沒有感覺到分塊的暴力屬性 今天卡常的時候莫名其妙的感覺到了 我甚至覺得自己經歷了分塊的誕生歷程 今天本來在對一個分塊題卡常 但是我直接寫的純暴力，一直差一點卡過 于是我想到了各種優化： 加 \(inline\) (別說還真有用)，加 \(register\) (感覺這個沒用)... \(bi 閱讀全文

摘要： 一、題目描述： 給你一個長度為 $n$ 的序列 $a_1\sim a_n$，$0 \le a_i \le 1\times 10^9$。 求有多少種 $1\sim n$ 的全排列 $b$，使得對于 $i\in [2,n],a_{b_i}\times a_{b_{i-1}}$ 不是完全平方數。 本題中完 閱讀全文