NHOI 总结

Little_corn · 2023-12-23 20:31:50 · 个人记录

T1:

其实就把题意转化为把第 i 位及后面的数全部搞成 0 ，双指针就好了。但是考场我直接一波下饭操作，死活调不出来，重构了一遍，心态趋近崩塌啊！！！共用时 1h！！！

T2 一道排列组合乱搞题，但是我只写了一种情况（（（

用时 10min ,但是预计挂 25pts

看完题直接 bfs 乱上，但是考后说需要更新，原因是队列元素不满足单调性，并且还需要玄学剪枝。

正解就是 dis[x][y]=dis[sx][sy]+1，并且当遇到障碍物或者 dis[x][y]<=dis[sx][sy]+1 直接 break

用时 35min，但是预计挂 25pts

直接把前 t+1 大的数加到答案里，然后直接 n-t-1 个数跑一个 01 背包，记录最大值即可。

用时 20min。

直接上两个单调队列即可。

用时 30min。

想到做法，可惜没时间打了。

主要思路是 dp 套 dp

先通过预处理算出第 i 个人分数为 j 的方案数 c_{i,j}，前缀和优化即可。

再设 f_{i,j} 为考虑前 i 个人，第 i 个人分数为 j 是的方案数。

则：

f_{i,j}=c_{i,j}\sum^{j-1}_{k=1} f_{i-1,k}

再来一个前缀和优化即可。