这是一个并不简单的背包类树形dp……

很自然地想到状态定义：$f[u][k][0/1][0/1]$表示以$u$为根的子树中，总共选择$k$个结点，其中除了$u$以外的所有结点均被监听到，$u$结点选或不选，$u$结点是否被覆盖的情况下，一共有多少种方案。

状态转移看似十分麻烦。每个结点$u$都有许多子结点，很难统计出每个子结点的所有情况（似乎在组合数学的范畴）。但是我们可以用十分巧妙的树形背包来进行状态转移。树上背包的转移套路是：

$$
f[u][i+j]=combine(f[u][i],f[v][j])
$$

相当于每递归访问完一个子结点，就把子节点上的状态与当前已经处理的状态一一配对，保证不重不漏且兼顾效率。具体的转移方程为：

$$
f[u][i+j][0][0]=\sum f[u][i][0][0]*f[v][j][0][1]
$$

$$
f[u][i+j][1][0]=\sum f[u][i][1][0]*(f[v][j][0][0]+f[v][j][0][1])
$$

$$
f[u][i+j][0][1]=\sum (f[u][i][0][1]*(f[v][j][0][1]+f[v][j][1][1])+f[u][i][0][0]*f[v][j][1][1]
$$

$$
f[u][i+j][1][1]=\sum (f[u][i][1][0]*(f[v][j][1][0]+f[v][j][1][1])+f[u][i][1][1]*(f[v][j][0][0]+f[v][j][0][1]+f[v][j][1][0]+f[v][j][1][1]))
$$

具体实现时还应注意：因为阶段（即扫描子结点个数）的划分，在每次转移前都要先记录原始的$u$结点上的数据，否则会导致混乱。

题目链接

不难发现，每个方格会与其上下左右四个方格产生矛盾。编程的任务即找到一种不产生矛盾的选择方案，并且使得取出的数总和最大。

首先对图进行黑白染色，目的是使产生矛盾的两个位置分别位于不同的色块中，方便建图。

源点与所有白色位置相连，权值为该位置上的数字；所有黑色位置与汇点相连，权值也为该位置上的数字；所有白色位置与其上下左右（注意边界情况）的黑色位置相连，权值为无穷大。

如此建图后，可以发现存在源点到汇点的增广路，这也意味着原图中存在产生矛盾的两个位置。假设一开始选取M*N网格中的所有方块，我们的任务是割掉网络中的一些边（即删去一些方块），使得割去的边权最小。割去网络中的边就相当于删掉两个矛盾位置中的其中一个，因此当网络中不再有源点到汇点的增广路，就意味着矛盾全部消除。

问题便转化为求解最小割（最大流）的问题。输出答案为全局和减去最小割。

题目链接

高精度怎能少了Python3题解。。。

贪心策略一楼dalao已经讲得很清楚了，上一发超短代码（学Python就是为了水高精）

题目链接

本题是一道非常漂亮的模拟。只要能理清思路，代码并不会特别复杂。

首先分析题目。解一元一次方程最简单的方法就是移项，把常数移到等号右侧，把一次项系数移到等号左侧，用常数除以系数即为答案。那么在读入字符串的过程中，便可以进行操作。

对于字符串中的数据，我们可以用类似快读的方法读入。然而，要判断这些数据从哪里来，到哪里去，便是本题的关键所在。

对于每个数据，要想清楚地辨别它的身份，我们只需解决三个问题：

1.该数据是正数还是负数？

3.该数据在等号左侧还是在等号右侧？

2.该数据是常数还是系数？

第一个问题看似十分无脑，用一个变量f1来存储符号即可（将f1赋值为1或-1，在读入数据结束时将得到的数据乘以f1）。但需特别注意，在一个表达式的开头（等号左侧和等号右侧的表达式）不会有‘+’、‘-’符号，所以在程序的开头和读入‘=’号是，要将f1赋值为1。

第二个问题也非常简单，可以用变量f2来存储。因为这个问题与移项运算的符号有关，因此也可以将f2赋值为1或-1，并约定在等号左侧时f2为1，在等号右侧时f2为-1。（当然你也可以反着约定）

第三个问题同样不难解决。在读入数据结束后（即读入了一个符号），判断这个符号是运算符还是字母即可。如果是字母，则将得到的数据移到等号右侧，否则将数据移到等号左侧。但是还有一个注意点：如果一个未知数的系数为1，我们会将系数省略。因此在读入数据为0时，我们要将其更改为1。

经过分析，你会发现本题一点也不难实现。其关键在于对数据状态的准确描述。用清晰、简洁的变量描述状态，根据不同的状态采取不同的措施，这便是编程学习的一大基本素养。

代码如下：

题目链接

介绍一种本题的贪心解法。

本题要求读入一些挤牛奶的时间段，求最长至少有一人在挤牛奶的时间段和最长没有人在挤牛奶的时间段。把读入的区间视作线段，则题意转变为求至少有一条线段覆盖的最大区间和没有线段覆盖的区间。

假设读入数据如下：

首先按照4条线段的起点位置排序（具体原因后面解释）。将begin设置为第一条线段的起点，将end设置为第一条线段的终点。

然后从第二条线段开始判断。如果该线段的起点小于end，则说明这两条线段有重合部分，将end更新为max{end,该线段的终点位置}。如果该线段的起点大于end，则说明该线段及以后的线段再也不会与前面的线段产生任何重合部分（这也就是排序的作用），那么可以更新ans1和ans2的值：ans1更新为max{ans1,end-begin},ans2更新为max{ans2,该线段的起点位置-end}。具体参见图中第4条线段，ans1被更新为1200-0，ans2被更新为1400-1200。

程序已经基本成型，但要注意在输出答案前更新一遍ans1的值，这是为了避免所有线段均有重合部分而无法判断的情况。另外，ans1和ans2要初始化为0。

程序如下：