[整理]qbxt集訓10場考試 大 雜 燴 （後篇）
Contest 6
A
兩個數，第 \(i\) 輪從較大數（如果相等就是第一個）里減去 \(i\) ，問操作不能進行時兩數分別為多少。
首先把大數減到和小數差不多，然後我們會發現接下來兩數會輪流減，所以剩下的部分兩數各減去的都是奇偶性相同的數。這樣的話對兩個階段分別二分答案即可。
B
已知數列 \(\{a_n\}\) 的每個數乘上權重 \(\{c_n\}(\sum c_i=1)\) 後的和（設為 \(f(a,c)\) ），求數列 \(\{b_i\}\) 乘上權重之後的和（設為 \(f(b,c)\) ）的最大值。
我們把它們的式子寫出來會發現， \(f(b,c)\) 與 \(f(a,c)\) 是有線性關係的，這時我們在每兩個點之間連邊，答案就轉化成了對於一個給定的 \(x_0\) ，求與 \(x=x_0\) 相交的線段里最大的 \(y\) ，然後枚舉即可。
C
初始有 \(n\) 個集合，每個集合里只有一個數，現在需要你依次合併相鄰的兩個集合，合併的代價是兩個集合里大於另一個集合最小值的元素個數，求全部合併的最小代價。
原題體面比較噁心，這個大於另一個集合最小值是轉化出來的。首先可以想到一種空間換時間的做法：預處理出最小值和小於某個值的個數，然後直接 \(O(1)\) 轉移區間 \(dp\) 。但是這樣空間會炸得飛起（雖然可以改成short避免炸空間但還是數據再大一絲絲就炸了），我們需要考慮一種不需要預處理過多東西的做法。對於一個區間 \([l,r]\) ，我們換一種方式枚舉分界點，從區間最小值開始向右走，顯然此時右側的貢獻就是右區間長度，左側區間可以維護一個堆，分界線每移動一格就將右側的新數加入，然後將小於右側最小值（預處理出來）的彈出，此時堆的大小就是左側的貢獻。這樣正著做一遍，反著做一遍就可以統計出答案了。還有一個小trick：對於此題數據範圍，把堆換成桶可以優化掉一個 \(\log n\) 。
D
給出一個被刪去一些數的排列，求使得填數後排列的逆序對數在 \([l,r]\) 中的方案數。
直接搜索不行，考慮折半搜索：預處理出左右兩邊分別的逆序對個數，然後狀壓求出右邊選不同數時和左邊形成的逆序對數，然後在左邊搜索。
Contest 7
A
一個 \(n\times n\) 的矩陣里取不在同行同列的 \(m\) 個數，問這些數和的最大值。
原題的 \(m\) 非常小，直接枚舉即可。
B
求 \([l,r]\) 之間，是 \(7\) 的倍數，不是 \(2,3,5\) 的倍數的數的個數。容斥。
C
給一張圖上的點染色， \([1,a]\bigcup [b+1,n]\) 染成藍色， \([a+1,b]\) 染成紅色，請你選擇合適的 \(a,b\) 使得雙色邊最少。
令 \(f_{i,j}\) 為 \(a=i,b=j\) 時的答案，我們考慮每條邊的貢獻：對於一條邊 \((u,v)\) ，只有 \(i,j\) 恰有一個數被包含，這條邊才是雙色邊。也就是說，這條邊會對以下部分做出貢獻：
於是就轉化成了一個掃描線求最小覆蓋次數的問題。
D
給出一個序列 \(\{a_n\}\) ，一個數 \(x\) 初始為0，每輪從數列里抽取一個數 \(a_i\) 並將這個數變為 \((x+a_i)\%n\) ，問有多少種玩法，使得 \(t\) 輪之後 \(d|x\) 。
\(t\) 很小的時候可以考慮這樣一個 \(dp\) ：設 \(f_{i,j}\) 表示 \(i\) 輪之後 \(x=j\) 的方案數。這時我們發現這個狀態有一個性質： \(f_{i_1,j_1}\times f_{i_2,j_2}=f_{i_1+i_2,(j_1+j_2)\%n}\) 。於是可以直接卷出來答案。
Contest 8
A
給出全集和三個全集子集的元素個數，求恰被兩個集合包含的數的最小個數。式子很簡單不放了。
B
有 \(n\) 個任務，第 \(i\) 個任務需要耗費 \(t_i\) 的時間並要求在 \(d_i\) 之前完成，同一時間只能做一個任務。如果要求完成任務的順序是按照 \(d_i\) 從小到大排序（相等的取編號小的），請你求每個作業的開始時間使得第一個作業開始時間盡量晚。
從後往前貪心做即可。
C
定義約數鏈為後一個數是前一個的倍數的數列。請問用不超過 \(m\) 的數組成的 \(n\) 個數的約數鏈共有多少種？
數據小的話可以 \(dp\) ：設 \(f_{i,j}\) 為前 \(i\) 個數，最後一個數是 \(j\) 的答案。轉移就直接枚舉倍數即可。但是如果 \(m\) 比較大，就不能直接暴力 \(dp\) 了。我們把第一位滾掉後枚舉一下可以發現當 \(\gcd(j,k)=1\) 時， \(f_{j\times k}=f_j\times f_k\) ，即 \(f\) 是一個積性函數。然後對於每個 \(p\) ，求出 \(p^j\) 的答案就可以線性篩了。
D
求刪去三條邊使得圖不連通的方案數。
直接求三條邊不好求，枚舉一條邊的複雜度是可以接受的，所以我們只需要求剩下兩條邊的方案數。圖不連通都要記上，所以我們主要來看圖連通的情況。既然涉及到了連通，我們就往生成樹上想一想，分幾種情況討論。
- 刪一條樹邊，一條非樹邊：
1.樹邊不被任何非樹邊覆蓋；
2.樹邊僅被刪去的非樹邊覆蓋。 - 刪兩條樹邊：
1.至少一條樹邊不被任何非樹邊覆蓋；
2.所有覆蓋這兩條邊的非樹邊都同時覆蓋這兩條邊。
想求出這些，我們需要先知道每條樹邊被哪些非樹邊覆蓋。可以利用哈希來做，給非樹邊隨機一個權值然後異或（其他有逆運算的也行）。為了方便處理權值，我們可以直接將dfs樹（利用其只有返祖邊的性質）作為生成樹。這樣走到的時候記錄上，回溯的時候再異或一下（或者其他運算的逆運算）。最後我們將權值排序或者map一下，就可以求出來權值為0或相同的方案數。
Contest 9
A
給出一個數列，求出兩兩之間 \(\gcd\) 的最大值、滿足此條件的 \(i,j\) 的個數和滿足此條件的 \(\sum a_ia_j\) 。
不能直接枚舉兩個數，我們就枚舉 \(\gcd\) ，然後統計 \(\gcd\) 的倍數。
B
有 \(n\) 個樓梯，現在在每兩個樓梯之間貼上箭頭，問有多少種貼法，使得兩邊箭頭都不指向自己的樓梯恰好為 \(m\) 個。
倍增優化dp。
C
有 \(n\) 隊選手合影，每隊3人，要求每隊的3人不能全挨在一起，求方案數。
可以容斥做：有一隊不滿足要求的 \(-\) 有兩隊不滿足要求的 \(+\cdots\)
D
請你在一棵樹上實現：刪除某條帶權路徑、修改某條帶權路徑的權值和不與某節點相交的路徑的最小權值。
首先可以二分答案轉化成判定小於等於某個權值的路徑交集是否與該節點相交。判斷兩條路徑相交可以分類討論，然後對兩條路徑的四個端點交叉求LCA。對於求交，我們可以按照權值排序，然後我們發現每次算的是一個前綴的交，我們就可以預處理出沒有修改和刪除的答案。在此基礎上加一個線段樹可以實現刪除操作。對於修改操作，我們把它們離線下來，然後在線段樹上實現刪除和撤銷刪除。
Contest 10
A
一個長度為 \(n\) 的僅包含012的字元串，每輪操作對字元串中所有 \(\ge2\) 的數 \(-=2\) 並將其兩側的數 \(+=1\) 。求出無法進行操作時的字元串。
首先可以猜證明出操作順序對答案沒有影響，於是可以開始亂搞：我們考慮一個前綴一次執行完所有操作後再對下一個元素執行，發現帶來的影響是將最後一個0向後移動，於是可以用棧維護。
B
\(m\) 個店鋪， \(n\) 種商品，每種商品在一個區間內出售， \(m\) 個人，每個人會買自己倍數的商店裡的商品，求每個人能買到的商品數。
對於一個標號為 \(i\) 的人，我們發現所有長度 \(\ge i\) 的區間都會取到，只需要處理長度 \(<i\) 的區間即可。此時相當於一個區間加一，可以用樹狀數組/線段樹維護。
C
\(n\) 個交易所，在一個交易所可以花費一定權值買一個物品，也可以以此權值賣出。同一時間只能持有一個物品，問最大收益和此條件下最小交易次數。有區間修改操作。
只有查詢比較簡單，如果加上修改就需要線段樹來維護，要加上幾個標記。
D
咕
