AtCoder做题记录1

自己做的时候觉得异常困难，但其实自己的思路比较正确，但还是有些地方想不清楚。两种方法：

1.选出已知权值最小且还没遍历过的点，把相邻的还没有更新过的点更新为该点的权值加1。最后check即可，正确性显然，但是过于人类智慧了一点。

2.考虑到二分图同一个部中的点奇偶性相同，考虑根据形态DP求出每个点的取值范围，然后从根节点往下边赋值边check即可。

感觉这题非常简单啊，大概放现在也就只有 *2200 的水平。首先一个 $O(n^2)$ 的做法比较显然，注意到数牌组配置数量等价于数操作序列，操作序列定义为每次出的牌组成的序列。

然后设最后一次出牌是第 $k$ 次，推推式子就行了，然后你会得到一个 $O(n^2)$ 的式子，暴力算就是 $O(n^2)$ 的做法了。考虑优化：

发现瓶颈在于处理式子中前 $k$ 张牌的枚举时产生的组合数求和，从化式子的角度进行考虑过于困难，试试递推，其实也还是要化个式子，只不过是换成递推形式而已。

银牌题。相当的困难，需要相当集中的注意力。

Two Key Observations：

1.观察到操作等价于从原矩形中选一个周长最大的矩形满足矩形内部没有给出的 $(x,y)$

2.观察到最后形成的矩形必过 $x=\frac{H}{2}$ 或者 $y=\frac{W}{2}$ 这两根线之一。

至此，就是套路题，枚举右端点，单调栈维护上下界，线段树求答案。代码其实还好，上面两个观察确实比较逆天。

为什么这个题能评到这个分？考虑去重，什么时候会有重复呢？只有循环同构回文串才会算重，枚举循环节长度，容斥计算方案数，然后乘上贡献即可。若循环节长度为奇数，贡献就是循环节长度，偶数就是除以二。

这种东西是人 15 min 能想清楚的？数排列又多了一种套路，**DP排名

发现把树黑白染色后如果钦定了一种顺序，那么整个排列的偏序关系就确定了。设计DP状态 $dp_{i,j,0/1}$ 表示 $i$ 这个点在子树内排名为 $j$ 这个点是黑点还是白点。

黑点就是周围的点都大于它，否则是小于它。方程是困难的，组合系数的推导要点功底。

厉害的。先去挖掘一下那些 $S$ 是有用的，发现只有 $|S| \le 3$ 的集合是有用的。然后考虑按 $S$ 的大小分别计算。注意要容斥掉一些东西，这些东西就只能用CDQ分治进行计算。

确实是基础DP，不多讲了。

这种数轴上走来走去的题就是不会做！这种题真的就是找性质加转化成一个形式化一点的东西。

比如该题注意到答案就是一段区间，并且可以直接从左走到右，于是：

$ans=\max_{[l,r]\subseteq [1,n]} (\sum_{i=1}^{m} \max_{j=l}^{r}B_{j,i} - \sum_{i=l}^{r-1}a_i)$

为什么有人可以十分钟AC？？？？？太困难了！

以后积累一个小套路：以后看到这种二元对立一样的题目描述就给我想异或相关的东西。

Key Observations

1.不会走回头路。

2.每一次操作可以理解为异或一段区间并且代价为 $|X_s - X_t|$

3.把异或操作放在差分数组上进行观察，就是起点和终点异或1。

至此就可以设计一个 $O(n^2)$ 的DP了。