题目
【题解】2024牛客寒假算法基础集训营4
来点每日一题
思路:先考虑定义 d p ( i , j , k ) dp(i,j,k) dp(i,j,k) 表示区间 [ i , j ] [i, j] [i,j] 中匹配了若干组的最大值,且当前匹配到了第 k ( k ∈ [ 0 , 6 ] ) k(k\in[0, 6]) k(k∈[0,6]) 位。发现这样需要维护两个变量,干脆修改定义为匹配最多一组,当 k = 6 k=6 k=6 时表示成功匹配了一组。最后统计答案时再 dp 一下。
如何求?枚举左端点,向右匹配即可。注意两点:1. 因为是有负数的,因此 决策点 不仅取决于转移者的最大值,同时依赖于最小值。需要维护最大值和最小值。 2. 初始化问题,
f
m
a
x
=
−
1
0
15
,
f
m
i
n
=
1
0
15
f_{max}=-10^{15},f_{min}=10^{15}
fmax=−1015,fmin=1015 大概可以。在这道题我没有进行初始化,而是学习了一下 optional<Type>
表示状态的有效性。
AC代码(使用 optional):https://www.luogu.com.cn/paste/jnh1v7pn
AC代码(使用动态长度 vector):https://www.luogu.com.cn/paste/71letred
数三角形(hard)
题解:链接
思路:对每一行,从左到右枚举右腰,同时用树状数组维护前缀中还存活着的左腰。左腰 ( ( i , j , l e n ) , i , j 为左下角坐标) ((i,j,len),i,j为左下角坐标) ((i,j,len),i,j为左下角坐标) 的存活区间是 [ j , 2 × ( l e n − 1 ) ] [j, 2\times (len-1)] [j,2×(len−1)] ,存到 vector 中定时删除。
维护出了当前存活的左腰,对于右腰,与其能匹配上的左腰区间为 [ j − 2 × ( l e n − 1 ) , j ] [j-2\times(len-1),j] [j−2×(len−1),j] ,在树状数组中查询。
注意奇偶性,可以开两个树状数组。
AC代码:https://www.luogu.com.cn/paste/j5haso7r
方块掉落
思路:线段树动态维护区间矩乘板子题。在这道题踩了结构体套 vector的坑,这样常数会很大,一度导致超时,优化了其他部分的常数才卡线通过。
正确写法:对于这种长度固定的矩阵,最好使用静态的结构,比如结构体套静态数组或 std::array
。前者初始化不是很方便,需要在定义时使用花括号初始化,否则需要枚举赋值;且不能直接赋值,需要 memcpy。后者比较方便初始化。
示例:
#include<bits/stdc++.h>
using namespace std;
using mat = array<array<int, 3>, 3>;
int main()
{
mat a = {{{1, 0, 0}, {1, 2, 0}, {1, 1, 1}}};
mat b;
b = {{{1, 0, 0}, {1, 2, 0}, {1, 1, 1}}};
return 0;
}
AC代码:https://www.luogu.com.cn/paste/po8gu7hr
heltion代码:https://ac.nowcoder.com/acm/contest/view-submission?submissionId=67399140