[CF] #353(Div2)

#353 Div2



A. Infinite Sequence

給你一個等差數列問有沒有某個值


注意一下0的問題應該就沒問題了



B. Restoring Painting

給n,a,b,c,d

在3 x 3的矩陣下 每一格都只能填1~n 每一個2x2的子矩陣的和都是相同的


算出4個角落的最大最小差 因為差是固定的 且所有的值都是1~n

假設k=max-min 那(1,1+k)~(n-k,n)就是4個角落可能放的數字 最後中間直接*n



C. Money Transfers

給一個環狀的數列 合為0

定義操作為移動任意的值到旁間

問全部變成0的最少操作數


前墜和 只有和一樣的邊界才會不需要操作其他都要

所以ans= n-max(相同的前墜和個數)

D. Tree Construction


給一個二元搜尋樹的插入順序


問除了第一個點的父節點是誰



因為n到100000 直接建樹 一條鍊會變成n^2


對於每一個節點的插入 他的父節點只會有兩個可能


就是比他小或比他大的第一個 需要做的就是去尋找他的上一個和下一個數


哪個比較晚就是父節點 map的++-- 可以輕鬆找




E. Trains and Statistic

現在有一條n個站的路 對於每一站 i (除了最後一站)都有一個值ai表示他可以用一步走到i+1站到ai站

p(i,j)表示從第i站到第j站最少用的步數

問p(1 <= i < j <= n)的總和




dp

從最後面dp回來

dp[x]=min(dp[k]+n-i-(ax-k)) for ax>=k (可以一步到的就一步到 不行的就先到k)

輕鬆炸裂TLE

需要維護一個stack 我們知道跳愈大步愈好

所以stk存(i,a[i]) 且保證 stk[u].a[i] > stk[u+1].a[i]

因為放的方式從n-1->1 所以i是遞增 去二分搜 ax 搜到就是最接中繼站

nlogn解完