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)。

读题一定要仔细，若理解题目出了问题再会做也没用。

总体来说还有进步的空间。继续加油