#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解完
