2022/04/18 做题记录

[CQOI2012]局部极小值

考虑容斥，钦定一些位置为局部极小值，因为 4*7 的格子中最多有 8 个局部极小值，可以考虑状压 dp 。

从小到大填数，局部极小值的要求就是它是它相邻格子中第一个填的，设dp[i][s]为填了 i 个数，局部极小值中有 s 这些被填了，对于一个 s 容易计算有多少个非局部极小值的格子可以填，而i-popcount(s) 就是已经填了的非局部极小值的格子数，可以直接转移。

code: /code/2022.4.18/P3160.cpp

两双手

因为这两个向量不平行，所以平面上每一个点都可以被这两个向量用唯一的方法表示（实际上就是基变换）。

我们把每个障碍按照变换后 x,y 的坐标和排序，保证后面的一定到不了前面设 dp[x] 表示遇到的第一个障碍是 x 的方案数，那么 dp[x] 也就等于所有走到这的方法减去遇到的第一个障碍是 y(y<x) 并从 y 走到 x 的方案数。

把终点也当成一个障碍就行。

code: /code/2022.4.18/bz4767.cpp