zhangxyhp

摘要： A. 十年之約 發現 \(f(n)\) 很小，考慮計算每個值 \(x\) 是多少個數的 \(f\) 值。顯然要求 \(f(i)=x\)，必定滿足 \(\operatorname{lcm}[1,x-1]\mid i\land\operatorname{lcm}[1,x]\nmid i\)。因此貢獻就是 閱讀全文

摘要： A. 序列問題 首先有一個 DP，設 \(f_i\) 表示前 \(i\) 個位置，當前子序列長度為 \(a_i\)，結尾也為 \(a_i\) 的最大價值。那么我們有: \[f_i=\max_{j<i\land a_j<a_i\land i-j\ge a_i-a_j}\{f_j+1\} \]考慮這三個 閱讀全文

摘要： A. 光 首先有一個貪心，每次選擇需要電量最大的位置加上 \(4\)，給相鄰的兩個位置加上 \(2\)，再給對角位置加上 \(1\)。 這樣不正確的原因是最后一些位置可能剩不下 \(4\) 個電量了，而我們四個四個放，就會產生浪費。那么我們之間暴力枚舉最后每個位置都剩下多少（\(0\) 到 \(3\ 閱讀全文

摘要： 首先計算在紅綠燈 \((a,b)\) 處期望的等待時間。記 \(a+b\) 為一個周期（即先有時長為 \(a\) 的紅燈，再有時長為 \(b\) 的綠燈），設我們在 \(x\) 時刻到達了這個紅綠燈，那么我們需要等待的時間顯然為 \(\max(a-x,0)\)。 要求出期望，就要用上面那個函數的和再 閱讀全文

摘要： 看到 \(n\le 18\)，基本上是要做狀壓的。考慮進行預處理，然后在較小的復雜度內回答詢問。設 \(f_{S,u}\) 表示當前走完了 \(S\) 中的點，現在在 \(u\) 點（\(u\in S\)），走完剩下的點的期望步數。于是有方程： \[f_{S,u}=1+\frac{1}{d_u}\s 閱讀全文

摘要： A. 「NOI2015」壽司晚宴 考慮一個 \(500\) 以內的數，頂多有一個大于 \(19\) 的質因子。那么對于所有數按照這個大質因子分類，同一個大質因子只能分給同一個人。對于剩下 \(8\) 個質因子狀壓 DP 即可。 Code #include<bits/stdc++.h> #define 閱讀全文

摘要： 要求結果為整數，我們將所有 \(a_i\) 分解質因數，對于每個質數分別考慮。 考慮對于一個左端點 \(l\)，能滿足要求的右端點一定在從 \(l\) 開始的一段連續區間中。于是我們得對于每個 \(l\) 求出 \(ans_l\) 表示那個最遠的右端點。 對于一個質數 \(p\)，假設 \(a_i\ 閱讀全文

摘要： 首先有一個 \(O(n^2)\) 的 DP：設 \(f_{i,j}\) 表示前 \(i\) 分鐘，當前朝上的面煎了 \(j\) 分鐘的最小翻面次數。于是有方程： \[f_{i,j}=\min(f_{i-1,j},f_{i-1,i-j}+1) \]其中第二種轉移是翻面的，即僅當 \(\exist k, 閱讀全文

摘要： 一、概念 有一些題要求我們統計某些點對的數量，限制一般和點間的路徑有關，\(O(n^2)\) 的時間復雜度無法承受。我們考慮首先選定一個根，此時路徑分為兩類： 經過根 不經過根 其中不經過根的可以在刪掉根后在每個子樹中進行統計，遞歸求解。于是只用處理經過根的情況。那么可以將這條路徑拆成從一個點到根和 閱讀全文

摘要： A. Cashback 設某一個子串的大小為 \(k\)。 \(k<c\)，要刪掉 \(0\) 個最小值，等價于 \(k\) 個長為 \(1\) 的區間。 \(k=c\)，就是這個區間之和減掉這個區間最小值。 \(c<k<2c\)，等價于 \(1\) 個長為 \(k\) 的區間和 \(k-c\) 個 閱讀全文