本文于 github 博客同步更新。
远古题，放现在强度不高。
A：
处理出每日融化积雪的前缀和，设第 \(i\) 天，则向二分查找的数组中添加 \(sum[i-1]+a[i]\) ， 之后查找第 \(j\) 天的 \(sum[j]>=sum[i-1]+a[i]\)， 进行差分，\(ans[j]+=sum[i-1]+a[i]-sum[j-1]\)，来处理不完全部分，最后，\(ans[i]+=num[i]*t[i]\) 即为所求。
B：
可以先转化一下，黑白染色后对黑格翻转，求最大全 1/0 矩阵。
不难想到悬线法，\(n^2\) 预处理后做 \(n^2\) dp，正方形的情况取宽的最大值即可。
C：
首先不难想到状压，记录前两列的状态，这样做是 \(\mathcal O(4^m\times n)\)的，比较极限。
观察状态，我们发现 \(01\) 与 \(11\) 造成的影响是相同的，这样我们就可以将状态数优化到 \(3^m\)，进行三进制状压。
三进制直接递推计算比较麻烦，且枚举的无用状态较多，不好维护，考虑转化为 dfs 写法，按列递归搜索，在极限数据下跑了 500ms 左右，相当快。
今天体测了捏，引体向上还是只能做 10 个捏，1000m 和初中一样捏，跳远和中考一样捏，50m 还是六秒大几捏，鉴定为没长进捏。
标签：总结,状态,2024.10,17,sum,状压,ans From： https://www.cnblogs.com/Mitishirube0717/p/18472239