总结

今天腊月初九。感觉最近不是很冷。今天是模拟赛，题目有一点多。把 div2 改完了，很有学习意义。

他们期末考试完啦！（怎么不太吉利的样子哈哈），可以象征性地说明一个学期已经结束啦！我的草稿本也刚好用完一个。

题解

简单讲一下。今天 div1 和 div2 都有四道题，有两道一样。简单说一说。

Eighty seven

是个原题，用 bitset 优化背包。

B. 不休陀螺

就是有几个二元组排起。你有一定的能量，每次你会先减去二元组中的第一个数，然后再补充上第二个数，都是非负的。如果某个时刻你的能量小于 0 了，你就挂了。每次会选择一个区间，进行随机排列，如果一轮完后你还没有挂，那么这个区间继续随机。如果无论如何你都不会挂，这个区间就是好的。求好的区间数量。考虑如果是中间时刻挂了，那么一定是这个区间所有正贡献然后加上这里面最大的第二个数或者剩下的最大的第一个数，如果比你的能量大了，那么右端点往后都不行了，就是一个区间内不会中道崩殂，这时候挂的原因就是整个区间是负的了，可以前缀和然后离散化用 BIT 维护。

C. 最大前缀和

一个长度的序列，求所有排列最大前缀和的和。最大前缀和的定义：的最大值。最开始看错最大前缀和的定义了，以为要和取，调了好久。大概就是定义最大的那个分割位置，从这个位置往两边，前面的所有真前缀都非负，后面的所有前缀都要是负数。简单转移一下就行了。

D. 染色

一个大小为的二进制矩阵，，循环相接（即脑壳和尾巴是连着的），最开始都是，每次可以选择一个位置，把这个位置和上下左右数字取反。给出最后的矩阵，求方案。容易想到高斯消元，发现解唯一。进一步想到可以只用设出前两列的变量，然后递推，可以列出更小的方程。但是还是不能过。看到这个大小，容易想到分治。会发现修改一个十字架可以实现修改同奇偶位置的一个十字架，然后就可以分治了，可以使用 bitset 优化。

有一道拓展的原题：CF1270I 。图案是任意的，可以套用到这道题上面。这道题就用的类似于矩阵乘法或者二元多项式的东西，由于发现有阶，所以可以有逆，就能做了。

这道题输出量很大，特别注意 endl 的使用，会超时。

后记

恭喜你发财！期末考试考完了。下周要去重庆了，好期待。明天就大寒了。快快乐乐，快快乐乐。