zhangxyhp

摘要： A. [NOIP2015 普及組] 推銷員 首先考慮一個明顯假的貪心，選擇前 \(X\) 大的疲勞值計算答案。 它假就假在，可以選擇一個（或幾個）疲勞值更小，但更遠的位置，使總貢獻更大。 略經思考后發現，如果要更換，那么一定要滿足距離比當前的所有都遠，而且更換掉的一定是當前最小的疲勞值。 同時，如果 閱讀全文

摘要： A. [CCO2015] 路短最 設 \(dp[i][S]\) 表示走到 \(i\) 點，經過的點集為 \(S\) 的最長路，用類似于 spfa 的方式轉移即可。 復雜度是一個 bfs，具體不太會證。 Code #include<bits/stdc++.h> #define ll long long 閱讀全文

摘要： 高維前綴和（SOSDP）解決這樣的問題： 給定 \(f_i\)，其中 \(i\in[0,2^n-1]\)，求解 \(\sum\limits_{j\subseteq i}f_j\)。 考慮一維前綴和： for(int i=1;i<=n;i++){ sum[i]=sum[i-1]+a[i]; } 二維前 閱讀全文

摘要： A. [USACO13NOV] No Change G 設 \(dp[S]\) 表示取的硬幣狀態為 \(S\) 時最多買多少東西。給 \(n\) 個物品做前綴和，轉移二分即可。時間復雜度 \(O(2^kk\log n)\)。 Code #include<bits/stdc++.h> #define 閱讀全文

摘要： A. Promises I Can't Keep 題目意為求以每個點為根時的期望得分的最大值，換根DP即可。 式子不太難推，半個小時就出來了。太長了不往這寫了。 Code #include<bits/stdc++.h> #define ll long long #define il inline # 閱讀全文

摘要： A. 「MXOI Round 1」城市 首先推個小式子，把讓求的答案中和 \(n+1\) 有關的分出來： \[\begin{align*} &\sum_{i=1}^{n+1}\sum_{j=1}^{n+1}cost(i,j)\\ =&\sum_{i=1}^{n+1}\sum_{j=1}^{n}cos 閱讀全文

摘要： AC自動機是以trie結構為基礎，結合KMP算法思想構建的，用于解決多模式串匹配問題。 它的構建方式分為以下幾步： \(1.\) 建立trie樹 \(2.\) 構建失配（fail）指針 其中 fail 指針指向的是當前節點的狀態的后綴所對應的狀態。 這里明確一下，trie樹中的每個節點表示的是一個狀 閱讀全文

摘要： 實際上是第二篇。 閱讀全文

摘要： 前言 NOIP也是考完了，過去的那個賽季也是過去了。 還是不甘，還是意難平。模擬賽明明考的不錯，為什么結果卻那么不盡如人意？ 中考后 沒休息幾天，就直接被叫到機房了。一整個暑假都在打模擬賽，現在翻翻每一場比賽的排行榜，名次從最下面一點點往上爬的過程記錄著自己的堅持。 后來中考成績出分了，考的不錯。新 閱讀全文