Aly_

1.动态规划 DP

​ 状态；状态的转移。

你应选择红色。

题意简述

​ $N$ 点 $M$ 边无向图，形态未知。每个点有状态：关 / 开。现需通过如下四种操作确定图的形态：

分析

​ 先考虑怎么算 $R(i)$。

树上背包 + Max 卷积

初步分析

​ nemo 肯定走直线。

​ SAM + 虚树 + 主席树。基本不需要动脑子但码量有点大。

​ 本方法不要求很熟悉 SAM 的相关内容。

解题报告

D1T1 卡牌游戏

​ 考虑二分答案 $X$，枚举最小值 $mi$，于是确定最大值 $mx$。在 $a_i$ 中找出最小值最大值的位置，则中间的都不用翻，两边的都要翻。判断翻后是否合法以及翻的张数是否小于 $m$ 即可。