12月月赛题解

smxp 2020-12-07 18:25:18 2020-12-15 1:43:01

第一题:签到题

直接计算即可

第二题:签到题

直接比较即可

第三题:暴力题

扫描数组,记录下当前出现过的最大值即可。

第四题:单调栈

单调栈来维护出现过的最大值即可。

第五题:二分

对于每一个敌人,二分找到第一个比它大的伤害即可。

第六题:动态规划

鸡蛋问题的另种版本。

对于样例二的解释:

一共进行了100次攻击,能够遭受2次bug

所以必须在2次出现bug之内找出暴击点,在最坏情况下,第一次bug机会应该让第二次试验的区间尽可能小,才能得到最优解

由此可以得出,需要每隔14次攻击测试一次,即测试第14次攻击、第28次攻击。。。。依次下去,是否出现过暴击

若出现暴击,则再依次枚举此区间。 比如,若第14次攻击软件返回出现过暴击,则应当枚举1-13,此时最坏情况下枚举了14次。每个区间都是如此。

假设如果每十次(而非14次)攻击实验,那么如果在第100次试验出现暴击的话,就是91-99,此时一共实验了 10 + 9 = 19次。

此题有两种状态转移方程:

第一种:时间复杂度:O(n^2m)

f[i, j]表示i次攻击,j次的测试中最坏情况的最小值

j次测试可以不用全部用完

状态转移:

不使用第j次测试,方案数为f[i, j - 1]

使用第j次测试,则有1~i次共i种情况可以测试,假设在第k次攻击测试:

出现致命bug,搜索区间变成1~k-1,致命bug次数减一,方案数为f[k - 1, j - 1]

没出现致命bug,搜索区间变成k+1~i,第j次测试可重复利用,方案数为f[i - k, j]

枚举攻击次数k,在所有可行方案中选择最大值即为最坏情况,答案就是这些情况的最小值

状态转移方程: f[i][j] = min(f[i][j], max(f[k - 1][j - 1], f[i - k][j]) + 1);

但由于此题数据较大,此方法会超时。

第二种:时间复杂度:O(nm)

f[i, j]表示用j次致命bug测量i次能测量的区间长度的最大值

枚举攻击次数k,类似dp1,没出现致命bug则测k次攻击以上,否则测k次攻击以下,那么能测的最大攻击次数就是上下两部分加上第k次攻击这一层

状态转移方程: f[i][j] = f[i - 1][j] + f[i - 1][j - 1] + 1;

并且当f[i][m] >= n 时,即可输出i为结果。

恭喜以下选手

共 1 条回复

Leiyuxuan

T4 > T6(确信

AMAZE UI
Hello world!