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

阿克掛 240 /dk

A

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

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

$n=2$ 時顯然誰先手誰獲勝，這是一個特殊情況，下面預設 $n>2$。

當 $n$ 為奇數時

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

當 A​ 先手時，他可以選 $1$，之後去蓋 B​。

當 B 先手時，它可以選 $2$，之後去蓋 A。

當 $n$ 為偶數時

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

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

當 B 先手更不用提了。

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

B

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

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

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

std 是倒序求，這樣不用字首和了。

有一個拓展

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

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

C

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

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

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

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

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

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

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

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

D

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

然後應用一個結論，你選的一定是一段長為 $1$ 的和另一段長為任意值的，那麼就是個 $O(nm)$ 的。

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

閒話

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

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

戚哥 rk 1