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

認為今天考的不太好

估分100+100+20=220

實際20+100+27.5=147.5

第一題：

貪心

按照積分從小到大排序，直接按此順序模拟買的過程。

注意t[ i ]表示總共買了t[ i ]個物品後積分倍率+1，要開longlong。

第二題：

打标找規律

ans=24*(2^n+2^m-1)%MOD

第三題：3046. 【NOIP2012模拟10.23】遊戲

DP

設f[i][j]表示第一個數列取了前i個，第二個數列取了前j個的最小得分（正着做和倒着做是一樣的）。f[i][j]=f[k][l]+sum(s[i]-s[k]-(i-k))*(s[j]-s[l]-(j-l))。時間複雜度O(n^4)。

其實可以發現因為數列中的數都是正整數，是以（a+c）*(b+d)>a*b的，其中a、b分别為第一列，第二列選的數，c、d為下一次選的數，由此我們知道一個一個選是最優的。至此F[ i ] [j ]={ F[ i-1 ][ j-1 ], F[ i-1 ][ j ] ,F[ i ][ j-1 ] }+(a[ i ]-1)*(b[ j ]-1)。

讀題一定要仔細，若了解題目出了問題再會做也沒用。

總體來說還有進步的空間。繼續加油