前言

今天是集訓最后一天，也是最后一場比賽了！我也是給了自己這次比賽考得不錯，315分，第13名，雖然沒有上次好，但已經超出我的平均水平了，AC三題，有一道簽到題，好的地方就是沒有再出現提交錯代碼的錯誤了，應得：T1AC,T2AC,T3AC,T4AC，T4WA5，實得：T1AC,T2AC,T3AC,T4WA10，T5WA5，

T1 Daisy Chains

題目大意

有一個集合P，再P里面選一個子集，滿足子集里有一個數等于那個子集的平均值，問有多少個這樣的子集，

正解

簽到題 $O(n^{3})$ 直接過，

賽時情況

要是不AC我早畢業了，

T2 Stuck in a Rut

題目大意

有n頭奶牛在一個無窮大的棋盤上，它們可以一直想北走或向東走，知道碰到其他牛的路徑，問一頭牛最多可以走多少個格子，

正解

和昨天的題一模一樣，只不過換了個問法，排序后列舉向東走的牛和向北走的牛，看看它們會不會阻攔對方，如果向東走的被向北走的阻攔了，則向東走的距離是 $x_{j}-x_{i}$ ，如果向北走的被向東走的阻攔了，則向北走的距離是 $y_{i}-y_{j}$ ，

賽時情況

我要是不AC我能rank13？

T3 交通換乘

題目大意

再數軸軸上標有兩類點：1類 $i$ 點需要花費 $a_{i}$ ；2類點 $j$ 需要花費 $a_{j}$ ，不過如果再比它小45個單位長度之內有一個1類點 $i$ 滿足 $a_{i}\leqslant a_{j}$ ，則 $j$ 不需要花費，但是每一個1類點只能讓一個二類點免費，現在給你這個數軸上的所有點，問總花費是多少，

正解

模擬，不過 $O(n^{2})$ 會爆，我們用一個單調佇列q維護所有時間再當前點45個單位長度以內的點，因為題目保證所有點的位置是升續的，所以我們就每個點更新，因為q是單調的，所以如果有一個元素不行，它之前的元素也都是不行的，我們這樣去更新q，

更新后的q里都是位置允許的1類點，我們遍歷一遍q，找出第一個費用允許的點，花了這張優惠券，如果沒有，那就只能花錢了，

賽時情況

想了大概半個小時，想到了用單調佇列優化，AC，

T4 紀念品

題目大意

你有n個物品，m個位元幣，你可以買或賣物品，但是每天它的物品的價值不一樣，問t天后你獲得的最大位元幣數量，ps：致敬xmring

正解

完全背包問題，物品的買賣只能再兩天之間進行，即昨天買+今天賣，因為前天買今天賣=前天買+昨天賣+昨天買+今天賣，昨天的價格當作重量，今天的價格當做價值，做一遍完全背包，注意每天的初始化 $f_{i}=i (1\leqslant i\leqslant m)$ ，以及答案的更新 $m=f_{m}$ ，

賽時情況

花了太多時間搞T5，沒時間就打了個表騙了10分，

T5 加工零件

題目大意

有n個點，m條邊，如果讓一個點做等級為 $l$ 的零件，和他有邊相連的點要做 $(l-1)$ 的零件，給你Q個任務，問你1要不要做0的零件，

正解

圖論，因為兩個有邊相連的點可以來回跳，所以如果1做了 $l$ 零件，他也要做 $(l-2)$ 零件，所以我們可以分析奇偶性，我們先計算出1到每個點 $i$ 的奇數最短路 $f_{i}$ 和偶數最短路 $g_{i}$ ，如果 $l$ 是奇數并且 $f_{i}\leqslant l$ ,那么輸出Yes；如果 $l$ 是偶數并且 $g_{i}\geqslant l$ ,那么輸出Yes，否則輸出No