Codeforces Round #576 (div.2)

codeforces

D Welfare State

题目大意：

给出n个人（1≤n≤2*1e5），每个人初始有ai块钱（0≤ai≤1e9）。所有人的钱都会有以下两种操作：第一种：改变一种一个人的钱为一个数字。第二种：将所有少于x块钱的人手里的钱变为x。输出进行q（1≤q≤2*1e5）次操作后，所有人手里的钱的数量。

解题思路：

因为第二种操作是会被第一种操作或比它大的第二种操作所覆盖的，那么，我们可以把所有进行过第一种操作的位置标记出来，然后找出它和这个操作后面的所有的第二种操作进行比较，取最大值。当然，这个题也可以用线段树，第一种是单点更新，第二种是区间修改，最后再是区间查询，很裸的板子。

E Welfare State

题目大意：

给出一个由3n个点和m条边组成的图，你需要找出一组大小为n的边的匹配或找到一组大小为n的独立集。
一组边的匹配表示不存在两条边共用一个点。
一组独立集表示不存在两个点被同一条边相连。
如果能找到一组边的匹配，输出Matching和方案，如果能找到一组独立集，输出IndSet和方案。否则输出Impossible。

解题思路：

首先考虑，一共3n个点，如果存在一组不小于n的边的匹配，即这组匹配有对应的不小于2n个点，那么我们能够找到一组匹配。如果找不到一组大小为n的匹配，那么，剩下的点一定是多余n个且两两没有边相连的，那么，我们可以找到一组独立集。因此，不会存在无解的情况。

F Rectangle Painting 1

题目大意：

给出n*n的网格，其中一些为黑，一些为白，将一块w*h的区域全部涂成白色的花费是max（w，h），问将整个区域图白的最小花费是多少？（1≤n≤50）

解题思路：

这个题很明显是一个DP，一开始可能会想到设方程为dp[i][j]表示从（1,1）到（i，j）全部涂白的花费，但是想到后面会发现状态无法转移。那么，我们看到数据规模只有50，可以设这个方程为dp[x1][y1][x2][y2]表示将（x1，y1）到（x2，y2）全部涂白的花费，方程转移时直接枚举横纵坐标进行记忆化搜索，最后得到答案。