======2020/05/09——2020/05/15周报======

=====团队训练=====

2020.5.9 [[ctuopencontest2016|CTU Open Contest 2016]] ''prob:5/6/10'' ''rank:5/89''

=====林星涵=====

====专题====

暂无

====个人练习====

[[codeforces641div2|Codeforces Round #641 (Div. 2)]] ''prob:5/6'' ''rank:170''

=====陶吟翔=====

====专题====

[[tarjan|Tarjan]]

====题目====

  * Codeforces641Div2-E（同本周推荐）
  * Codeforces642Div2-D
    * 题目大意：给出一串数，每次可以把区间$[l,r]$中得数变成其中得中位数（若长度为偶数则取小的），问能否在有限次把所有数变成$k$。
    * 解题思路：首先数列中一定要有$k$，然后发现只要能够找到一个大于等于$k$的数并且是其与$k$相邻即可，所以任意相邻的三个数中只要有两个数大于等于$k$，我们就可以变化出一个大于等于$k$的数，然后我们一步一步扩展到一个$k$旁边即可。

=====郭衍培=====

====专题====

[[Burnside引理和Polya定理|置换群论]]

=====本周推荐=====

陶吟翔：Codeforces641Div2-E，题目大意是有一个$n \times m (n,m \le 500)$的矩阵，每个格子要么是黑色要么是白色。现在在每一轮里，如果与一个格子相邻的四个格子都与这个格子颜色不相同，那么下一轮这个格子的颜色就不会改变，否则这个格子的颜色就会从黑变白或从白变黑。有$T(T \le 10^6)$个询问，每次询问格子$(i,j)$在第$p$轮的颜色。乍一看会想找循环节，但是仔细分析会发现如果一个格子的颜色会变，那么说明有和它相邻的格子和它颜色一样，那么那个格子也会变，这说明某一个格子一旦会发生变化，一定是黑白交替。然后就是变化是会传递的，就是说一个点如果一开始不会发生变化，但是它旁边的点会变化，那么下一轮它就会开始变化。所以我们找到一开始会变得点，然后从它们开始BFS处理出每个点会开始发生变化得轮数，在根据这个信息来判断某一个点在某轮式什么颜色。由于一个点最多入队一次出对一次，询问复杂度$O(1)$，总时间复杂度$O(nm+T)$，[[http://codeforces.com/problemset/problem/1349/C|这里是网址]]。

郭衍培：一棵树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]。[[https://nanti.jisuanke.com/t/A1362|这里是网址]]

林星涵：Codeforces642Div3-F,$n\times m$的格子，每个格子给定一个高度。要从(1,1)走到(n,m)，只能往下或右走，且只能走到比当前高1的格子。花费1的代价可以让一个格子高度减1，问使得存在合法路径的最低花费。思路:最优策略下，最终的合法路径上，一定有一个格子没有更改高度。枚举每个格子，要求不更改其高度且强制走过这个格子。对每种情况，可以dp求出最小花费（或不存在这种可能）。[[https://codeforces.com/contest/1353/problem/F|这里是网址]]