A、查詢區間眾數出現次數

莫隊的板子題，不多贅述，(建議直接百度題名，看其他巨佬博客)

B、PC玩游戲

(CF1700分的題 為啥沒人寫)
解法一：二分答案，
解法二：set容器，把每次查詢當成一次插入操作，維護可以存放的玩偶數量，

C、PC買禮物

DAG上dp

d p [ i ] [ j ] dp[i][j] dp[i][j] 表示在第 i i i間店，花了 j j j元錢的方案數
設有 ( u , v ) (u,v) (u,v)這條單向邊，則 d p [ v ] [ j ] = d p [ v ] [ j ] + d p [ u ] [ j ] + d p [ u ] [ j ? w i ] dp[v][j] = dp[v][j] + dp[u][j] + dp[u][j - w_i] dp[v][j]=dp[v][j]+dp[u][j]+dp[u][j?wi?]
因為無環，且所有邊都滿足 u < v u<v u<v，按序號從小到大dp就行，

D、game

簽到題，無論如何整個圖最后都能被走完，判斷奇偶就行

E、median

題意：給你一個 [ 1 , n ] [1,n] [1,n]的排列，有多少個長度為奇數的連續子序列滿足中位數是 v v v，

因為長度是奇數，就保證了 v v v必須是連續子序列從小到大排序后處于中間的數，
即我們只要滿足在子序列中，比 v v v小的個數等于比 v v v大的個數，并且有 v v v存在，
預處理將所有比 v v v小的數改為 ? 1 -1 ?1，比 v v v大的數改為 1 1 1，把 v v v改為0，并標記位置為 p o s pos pos，
轉化為求有多少經過pos的奇數長度區間，其和為 0 0 0，
利用前綴和就可以解決本題

F、重建網路

貪心+最大生成樹

本題要讓最小邊權等于 k k k，可以先跑最大生成樹，
如果最大生成樹中出現比 k k k小的數，則對于每個比 k k k小的數都計算貢獻，
若未出現，則答案為 m i n ( a b s ( k ? w i ) ) min(abs(k - w_i)) min(abs(k?wi?))

解釋未出現的情況：
給你一顆樹和一條 ( u , v ) (u,v) (u,v)邊，你可以從樹上將 ( f a [ u ] , u ) (fa[u],u) (fa[u],u)邊替換，這樣保證替換后，仍然是一顆樹，
因此我們得到最大生成樹后將邊權最接近k的直接替換進樹就行，

G、最大得分

三維dp (可滾動陣列)

d p [ i ] [ j ] [ k ] dp[i][j][k] dp[i][j][k] 表示第 i i i個數，當前部分的 g c d gcd gcd為 j j j，已經分到第 k k k部分了
g = g c d ( j , a [ i ] ) g = gcd(j,a[i]) g=gcd(j,a[i])
d p [ i ] [ g ] [ k ] = m a x ( d p [ i ] [ g ] [ k ] , d p [ i ? 1 ] [ j ] [ k ] ) dp[i][g][k] = max(dp[i][g][k],dp[i - 1][j][k]) dp[i][g][k]=max(dp[i][g][k],dp[i?1][j][k]) 即仍然放在第k部分
d p [ i ] [ a i ] [ k ] = m a x ( d p [ i ] [ a i ] [ k ] , d p [ i ? 1 ] [ j ] [ k ? 1 ] ) dp[i][a_i][k] = max(dp[i][a_i][k],dp[i - 1][j][k - 1]) dp[i][ai?][k]=max(dp[i][ai?][k],dp[i?1][j][k?1]) 即放在新的部分
(注意減少gcd的使用次數，否則可能會T 或者 預處理也行)

H、PC要出題

思維簽到題

用 s u m [ i ] sum[i] sum[i] 表示數字 i i i出現個數

對 a i a_i ai?取模后得到 v v v，
ans = ans + sum[(k - v) % k] (注意這個%k，漏了就會wa)
然后更新 s u m [ v ] sum[v] sum[v]