【游记】ZROI 21noip赛前20天 day15

比赛链接（正睿）

	T1	T2	T3	T4
得分	100	20	0	0
估分	100	20	0	0

T1用\(O(n^2m)\)模拟题意，之后发现\(m\)只有\(64\)，可以把状态压成一个unsigned long long之后用位运算判断边的状态，最后用__builtin_popcountll()统计即可将复杂度降到\(O(n^2)\)，还带一个\(\frac{1}{2}\)的常数，可以通过。

T2在数列上枚举端点，搜索出所有情况，预处理数列前缀和，最后统计最小值。复杂度大约\(O(2^n)\)。

此时剩的时间不多，T3没有思路，去看T4。T4推出了\(\text{dp}\)的式子，但因为二维前缀和写错没有得分。