2024牛客寒假算法基础集训营6
title: 2024牛客寒假算法基础集训营6
categories:
- ICPC
tags:
- null
abbrlink: db08c90f
date: 2023-12-31 00:00:00
I题:要求矩阵的最大子矩阵和,其中第i行第j列是ai*bj。
经过代数变形问题等价求:a的连续子段和b的连续子段和.
考虑到有负数存在,我们四个dp数组分别记录a的最小子段和a的最大子段,b同理。
答案就是最值最值(4种可能)
j题:给出一个有根树,1为根。给出节点颜色,要求红节点的子树点权和是3的倍数。
每个点的点权为1或2,给出任意一种构造方案。
解法:分析可知两种情况下无法构造
- 红叶子没有子节点,子树和无法到3.
- 红节点的儿子不存在白节点
本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来源 爱飞鱼的blog!