CSP-S2考前綜合強化刷題 Day1

阿克掛 240 /dk

A

有 n n n 張牌，奇數屬于第一個人，偶數屬于第二個人，兩個人輪流按撲克規則進行游戲，指定一個先手，求誰能獲勝，

以后看見這些簡單的找規律題，一定要從下邊界開始一個個手玩，不然爆零兩行淚，

n = 2 n = 2 n=2 時顯然誰先手誰獲勝，這是一個特殊情況，下面默認 n > 2 n > 2 n>2，

當 n n n 為奇數時

1 2 3 4 5
A 1 3 5
B 2 4

當 A? 先手時，他可以選 1 1 1，之后去蓋 B?，

當 B 先手時，它可以選 2 2 2，之后去蓋 A，

當 n n n 為偶數時

1 2 3 4 5 6
A 1 3 5
B 2 4 6

當 A 先手時，它隨便選一個數，B 都可以用最大的數去蓋他，之后主動權就是 B 的了，一直壓著打就行，

當 B 先手更不用提了，

不需要高精，偶數奇數直接看最后一位，

B

給 n × m n \times m n×m 的網格刷顏色，初始都是紅色，每次可以把一行或一列染成紅色或藍色，問最后藍色的個數，

套路題，顯然對于同一行或列的操作，只有最后一次有用，那么記錄一下最后一次的操作和操作的時間，這樣我們通過前綴和，可以求出在某一個對行染色操作之后，有多少個對列染色，列舉行求貢獻，討論一下

• 如果當前行是紅色，那么求有多少個成藍色，貢獻是 m ? m- m? 在它之后藍色的列數，
• 如果當前行是藍色，貢獻是在它之后的紅色列數，

std 是倒序求，這樣不用前綴和了，

有一個拓展

先明確一點，那個 p p p 和 q q q 是為了減少輸入量的，直接看成一個給定的區間就行了，還有，區間覆寫不能差分，

直接說一個有點像暴力的做法，還是倒著處理，我們把每個位置看作一個并查集，初始老大都是自己，對于一個區間 [ l , r ] [l,r] [l,r] 找到里面的并查集進行修改，這樣你記錄一下每個點為左端點有沒有并查集就行，然后你將之間所有的并查集合并到 r + 1 r + 1 r+1 所歸屬的并查集中，手玩一下正確性也沒問題，復雜度呢就是你每個點算一次就被合并了，不會重復的，所以是線性的，

C

給你 n n n 個人的初始位置和速度，和 m m m 個形如 t k t \ k t k 的詢問，求 t t t 秒后排名為 k k k 的人的編號，位置相同編號小優先，

做過一道類似的題，所以開始想偏了，最后竟然暴力碾壓標算，

分 t > 1 0 5 t > 10^5 t>105 和 t ≤ 1 0 5 t \leq 10^5 t≤105 討論，這樣 > 1 0 5 > 10^5 >105 初始位置的影響就微乎其微了，直接以 v v v 為第一關鍵字， a a a 為第二關鍵字， i d id id 為第三關鍵字排序， k = 1 k = 1 k=1 的直接求最大值，這是 O ( n ) O(n) O(n) 的，

對于其它的資料，可以呼叫 stl 的強大函式 nth_element，它可以 O ( n ) O(n) O(n) 求第 k k k 大，我的做法就是想 sort 暴力沖不過去，所以我離線，對于相同時間的一個 sort 搞定，然后直接沖，

ppt 中給了另一個做法，說是將詢問離線，因為兩個人之間追趕只有一次，因為不同一次函式只有至多一個交點，先按 t = 0 t=0 t=0 排序，然后按時間順序從小到大，冒泡一下，注意，冒泡看上去是 O ( n 2 ) O(n^2) O(n2) 的，但我們只交換相鄰兩個數，你考慮把一個數往前移動，肯定是連著移動的，如果某一個位置不行了就直接退出回圈，所以不是立方，

類似的題是讓你回答前若干次的追趕，

先按 t = 0 t = 0 t=0 排序，數學建模一下，把每個人看成一條直線，那么你求出相鄰兩個追趕的時間，也就是聯立方程，那么用堆維護一下，注意這里追趕一定先在相鄰兩個人之間發生，所以加進堆中的是配對，

翟佬的話如醍醐灌頂，其實暴力能過很大原因在于你上一次排好序了，這一次只是微微調整，

D

這個四次方暴力海星，就是一個區間 dp 吧，顯然先把序列倒序，每個元素都減去 1 1 1，這樣價值是前綴的乘積，我賽時到這，就沒往下想了，臻可惜，

然后應用一個結論，你選的一定是一段長為 1 1 1 的和另一段長為任意值的，那么就是個 O ( n m ) O(nm) O(nm) 的，

略證一下，你考慮 A 選了 x x x 和 y y y， B B B 選了一堆數是一個 k k k，有
( x + y ) × k = x × k + y × k (x + y) \times k = x \times k + y \times k (x+y)×k=x×k+y×k
那么把 x x x 和 y y y 拆開都相等了，給別的數用何樂而不為呢，

閑話

出題人：這道題我設定了兩個沒有 n = 2 n=2 n=2 的點，我多涼心，

wyz：這比賽除了寫掛還有人能不阿克？

戚哥 rk 1