# APCS 21/09/05
總之立個flag，提早交卷出來跑出來整理一下題目好ㄌ
上次已經考過實作5了
主要是想要單張成績單上面寫5/5加上400分
所以才來再考一次，應該不會出事ㄅ
:::info
結果直接睡過頭，觀念題沒考到QQ，馬上出事
:::

update:感謝Ginorz支援subtask範圍

---
題目的部分

## P1
給你 $t$ 個七言對聯的平仄
然後有三條規則
A:二四字平仄要相同，二六字要不同
B:仄起平收(第一句的末字要仄，第二具的末字要平)
C:兩句的二四六字平仄要不同

然後輸出違反了那幾條規則，或輸出沒有違反
$t \leq 30$

## P2
在一個 $n \times m$ 的棋盤上
有 $k$ 個魔王，這些魔王都有起始位置跟移動向量
剛開始棋盤上沒有任何炸彈
接著每回合開始時
若有炸彈跟魔王在同一格，則炸彈引爆並殺死同一格上的所有魔王
接著所有魔王在所在位置放一顆炸彈
然後沿著他們位置向量走到下一個
(若魔王原始位置為 $(x,y)$，該魔王的方向向量為 $(r,c)$，則魔王位置變為 $(x+r,y+c)$)
若超出棋盤則魔王也會死掉

當所有魔王都死掉時，遊戲結束，求結束時棋盤上有幾個位置有炸彈

$1 \leq n,m \leq 100, 1 \leq k \leq 500$

Subtask 1:陣列只有一維（50分）

## P3
有一個大小為 $n$ 的正整數序列$a$，每個數都相異
現在要找出整個序列的幸運數

對於一個區間 $[l,r]$ 的幸運數 $f([l,r])$，考慮以下過程

若 $l = r$，幸運數為$a_l$

否則
1. 找出區間中最小的數，假設位置為m
2. 比較區間 $[l,m-1],[m+1,r]$ 總和的大小 ($l > r$的區間和視為0)
3. 若左側區間和較大，則回傳 $f([l,m-1])$，否則回傳 $f([m+1,r])$，

$n \leq 3\times10^5$

Subtask 1:$a$ 是一個 $1\sim n$ 的排列 （40分）

## P4
有一個大小為 $n$ 的正整數序列 $a$
現在可以選 $k$ 個區間，使的每一個選定的區間中都不能有重複的數字，區間之間可以重疊
求這 $k$ 個區間的聯集最大可以是多少

$n \leq 10^6, k \leq 20, n\times k \leq 5\times 10^6, \forall a_i \leq 10^5$

Subtask 1:$k = 1$（50分）