常州培训 day6 解题报告

第一题：

题目大意：

给出一个N*N的矩阵，矩阵元素均为0或1。定义矩阵权值为sum（F[i][j]*F[j][i]）;

给出K个操作：

N<=1000，K<=10^5

解题过程：

一开始看到K的范围有点大，肯定不能模拟，想到前几天N皇后那题大神讲了可以用60位压成一个long long优化，于是就傻乎乎的把每一行每一列都60位压缩。然后各种麻烦的操作，写到最后发现写不下去了，顿时心情糟透了，然后打算写个爆搜算了。结果在写爆搜的时候猛然发现。。这题其实是大水题。。
首先对于不相同的i，j，ans必然要加上F[i][j]*F[j][i]+F[j][i]*F[i][j]; 这个式子必然mod 2为0。所以影响答案的只有对角线的元素。只要一开始计算出ans，然后每进行一次操作2或者操作3，ans就会取反。总的时间复杂度其实是O(N+K)；
没舍得把60位压缩的代码删了，然后脑残的想来练习一下压缩法，于是把对角线的元素放在一起做60位压缩，结果小细节没处理好爆0了。
经过测试证明，60位压缩的效率非常高，所以数据跑完是2146ms，标准算法是2096ms。虽然写起来稍微麻烦了点，还是非常好用的。

第二题：

题目描述：

粉刷N块宽度为1的木板，给出木板的高度，木板与木板紧密相邻且下对齐。

每次粉刷可以用宽度为1的刷子横着刷，也可以竖着刷，但不能刷到木板以外的地方。求最少的粉刷次数。

解题过程：

这一题乍一看以为是NOIP2013 day2第一题换了个背景，但看了半天还是没什么思路。。。只发现一点：如果有一个木板的高度是1，那么必定是横着刷（反正是要刷的，竖着只能刷一个，横着可以刷一排）。第一题花了很多时间，这题就只好随便写个贪心了。每次找到一个高度为1的，刷掉，然后剩下的全部竖着刷。。结果只骗到了10分。
AC算法：先找到一个最矮的，设其高度为h，然后横着刷h行。（想象成底下砍掉h行）然后就分成了左右2个部分，分别递归求解。。当然对于区间[L,R],还是要考虑全部竖着刷的情况，两种情况取个最小值即可。
粗略证明（自己想的，不严密）：只要证明在不考虑全部竖着刷的情况下，先横着刷min（H[i]）行肯定不会比最优解差。。假设第k列的高度最小，那么如果第k列是竖着刷完的，那么在分出来的左右两个部分中，必然不会有横着刷的情况。因为如果有横着刷的情况，那横着刷的时候如果刷到k这行可以更优。。

第三题：

题目描述：

给出N个矩形，求出总的覆盖面积。

N<=10^5, 0<=xi<=10^6,0<=yi<=10^9,1<=ai,bi<=10^6

解题过程：
1.考试时线段树忘得差不多了。。不敢写，直接写了个暴力，骗了30分。

2.AC算法：扫描线线段树。。考虑到x的范围比较小，所以根据x做线段树，先根据线段y坐标排个序，把下边描述成一个开始事件，上边看成结束时间，从下往上扫描累加面积即可。

3.讲课的大神说x，y的坐标即使开到10的18次也可以做，只要用链表的形式存线段树，一个节点只有用到的时候才为它开辟空间。解决了静态存储空间不够的问题。

巴特西