2019.08.04【NOIP提高組】模拟 B 組總結

這次又被坑了。。。

估分：60+30+30=120

實際得分：60+0+0=60

T1：

我們把一次操作定義為一段的頭移到尾，那麼總操作次數為n / 2 + n / 3 + ... + n / n <= nlogn。我們發現，對于某一段長k，第一段的頭恰好移動到第二段的頭，第二段的頭恰好移動到第三段的頭，依此類推，故每次操作時間複雜度O(1)。時間複雜度O(nlogn)。

T2：

小Y隻有攻擊型卡牌（共50%）：貪心政策一（不消耗對方的防禦型卡牌），把小X的卡牌從大到小排序，小Y的攻擊性卡牌從小到大排序，然後依次對應用到不能用為止。時間複雜度O(nlogn + mlogm)。

30%：DFS，搜尋小X的每張卡牌的使用對象是小Y的哪張卡牌。時間複雜度O(n^m)。

100%：貪心政策二（消耗完對方的防禦型卡牌），對于小Y的每張防禦型卡牌，都選小X的比其力量值大的力量值最小的卡牌來消耗，接下來同貪心政策一。将貪心政策一、二結合即可。時間複雜度O(nlogn + mlogm)。

事實證明，題解是錯誤的。怎麼做呢？小X的大的牌比對小Y的大的牌？

T3：

30%：DFS，每秒隻有用魔法或不用魔法兩種可能。時間複雜度O(2^n)。

60%：DP，f[x][y][t]表示t時刻到位置(x, y)的最長滑行路程，決策隻有t時刻使用或者沒使用兩種情況。時間複雜度O(nmt)。

100%：DP，f[x][y][k]表示第k段時間結束時到位置(x, y)的最長滑行路程，那麼決策區間就是在該段時間對應的方向上在該位置之前長度為該段時間長的一段，可以使用單調隊列把轉移時間複雜度優化到O(1)。時間複雜度O(nmk)。

對于單調隊列可以維護一個f[i][j][k-1]+i/+j的形式的單調不升的隊列

例如上升，我們可以從f[i+l][j][k-1]+l 轉移過來（1<=l<=r-l+1），是以從n到1維護一個f[q[h]][j][k-1]+q[h]單調不升的隊列然後即可O（1）轉移。

 後兩題都0分的原因是即用getchar讀入有用scanf讀入，于是就GG了。。。

據說這兩種讀入方法是不能同是使用的。。。

以後必須要多加注意了。