2020.5.9 CTU Open Contest 2016 prob:5/6/10 rank:5/89
暂无
Codeforces Round #641 (Div. 2) prob:5/6 rank:170
陶吟翔：Codeforces641Div2-E，题目大意是有一个$n \times m (n,m \le 500)$的矩阵，每个格子要么是黑色要么是白色。现在在每一轮里，如果与一个格子相邻的四个格子都与这个格子颜色不相同，那么下一轮这个格子的颜色就不会改变，否则这个格子的颜色就会从黑变白或从白变黑。有$T(T \le 10^6)$个询问，每次询问格子$(i,j)$在第$p$轮的颜色。乍一看会想找循环节，但是仔细分析会发现如果一个格子的颜色会变，那么说明有和它相邻的格子和它颜色一样，那么那个格子也会变，这说明某一个格子一旦会发生变化，一定是黑白交替。然后就是变化是会传递的，就是说一个点如果一开始不会发生变化，但是它旁边的点会变化，那么下一轮它就会开始变化。所以我们找到一开始会变得点，然后从它们开始BFS处理出每个点会开始发生变化得轮数，在根据这个信息来判断某一个点在某轮式什么颜色。由于一个点最多入队一次出对一次，询问复杂度$O(1)$，总时间复杂度$O(nm+T)$，这里是网址。
郭衍培：一棵树n个点中选m个，要求不能有孤立点（即每个被选的点旁边还有选中的点），求方案数。dp0[i][j]表示i的子树中选j个，且根节点不选的合法方案数；dp1[i][j]表示i的子树中选j个，根节点选中且子树中有与根连接的点被选中的合法方案数；dp2[i][j]表示i的子树中选j个，根节点选中且子树中无与根连接的点被选中的合法方案数。递推的时候，对根节点的每个子节点，类似01背包（取max改为加）。最终答案为dp0[1][m]+dp1[1][m]。这里是网址
林星涵：Codeforces642Div3-F,$n\times m$的格子，每个格子给定一个高度。要从(1,1)走到(n,m)，只能往下或右走，且只能走到比当前高1的格子。花费1的代价可以让一个格子高度减1，问使得存在合法路径的最低花费。思路:最优策略下，最终的合法路径上，一定有一个格子没有更改高度。枚举每个格子，要求不更改其高度且强制走过这个格子。对每种情况，可以dp求出最小花费（或不存在这种可能）。这里是网址