【考前冲刺Day4】关于我不开long long见祖宗这桩事

T1 增援前线

实锤乱搞题,考试的时候写了一个错误的dp,只拿了一半的分。
实际上这一题应该属于贪心吧
我们用f[i]表示i号点能站多少人。
显然,前l个点的f[i]=a[i];
对于其他情况,f[i]应由i-l到i-1这段区间内的点更新而来。
具体来说,就是“能跳则跳,满员为止”
我们优先选择距离当前点较远的点来更新,下面将证明这一结论。

我们每次只能在\(i-l\)到\(i-1\)这段区间内选择点来更新答案,每次我们可选的状态空间都会变动(整体右移),如果我们优先选择左边的点来更新的话,右边的点的可选方案数不会改变,而左边的点的可选方案显然是比右边的少的(因为左边的点会先退出可行方案),根据决策包容性我们可知该贪心方案正确。

代码中的3个if是优化枚举(可行性),否则时间复杂度将达到\(O((N-L)\times L)\) 然而数据太水不加也能过


T2 进化序列

QAQ QAQ QAQ QAQ,就是这一题!!!!我可不是什么邪恶的史莱姆
考场上先写了一个暴力,然后写了线段树+二分(Binary Segment Tree简称BST),对拍发现答案不一样,最后发现是暴力写错了orz
然后自己造了好多大数据,都是暴力跑得快(但是暴力还是被卡了)
然后没开long long 或运算起来可能会爆int,见祖宗了


为什么用线段树?我们要查询的区间或值是满足区间可加性的。
为什么二分?可以发现越多的数或起来不会变小。

发表评论

电子邮件地址不会被公开。 必填项已用*标注