2020.09.02-2020.09.05 学习日志
高二开始了。
2020/09/02
第二节晚自习过来，刚坐下发现群里有一道题。
ATCoder-[ABC176]E - Bomber：记录详情
题目意思是在一个网格上有一些点，你可以选择任意一行以及任意一列（十字），要求覆盖的点数量。
因为每个点上的权值要么为0，要么为1，考虑先读完数据后把每行的权值和预处理，然后sort之后找到最大值。把行和列的两个最大权值和加起来显然是不行的，因为一行和一列有一个公共点，那么当这个点为1时，这个点的权值会被重复计算。所以考虑在读入时把有点的地方哈希散列表存起来，然后再判断行和列均最大值时，这个点是否为1。因为行和列中可能有很多个最大值，所以乍一看复杂度为 ，这时我们发现当行和列的公共点上权值为0时我们就可以break跳出循环，所以我们需要判断的公共点一定是权值为1的点，这些点一共只有n个，所以复杂度实际为 。
巨巨 \text{Sunward_z} 现场教会 做法，大概就考虑把最大值的点打下标记，然后重新读数据时直接判标记就好了，只要 ，我还是菜。
今晚想写一道很久之前看过的题目，然而好像并没有什么思路。
洛谷-P1712 [NOI2016]区间：记录详情
巨巨 \text{Sunward_z} 又教会我，我大概想先按照区间长度排完序后依次加入，当对于某一个点被包含的次数等于m时就记录贡献，大概按照一个滑动窗口的思想，然而只是加入并针对于点而言，这样的思想并不好在代码里实现。\text{Sunward_z} 纠正了一个误区就是可以进行全局删除操作，注意全局，而不是针对于某一个点，而这样的正确性是我所没有考虑到的，因为我们是排序后的依次插入删除，所以正确。
2020/09/03
下午1.5个小时就把昨天那道线段树调完了，原因主要是：少了一个+号调一年。
然后又花了0.5个小时帮 调了一下线段树的板子，顺便跟他讲了一些细节处理。
最近想搞下矩阵之类的东西，主要是发现之前矩乘的板子没过，应该是没考虑好矩阵乘法不满足交换律，以及单元矩阵的构造。
洛谷-P3390 [模板]矩阵快速幂：记录详情
洛谷-P3389 [模板]高斯消元法：记录详情
大概观尛了下神仙 的博客，高斯消元法之约旦消法-Nemlit。
由于他的描述非常到位而且代码易懂还设坑，很快就理解了。
首先，你可以对于每一个主元都找到一个未找过的方程与之对应，所以就是一一对应的关系，然后我们把这个方程的主元系数消为1，再拿这个消成1的方程的系数去消掉其他的方程，最后我们就只剩下一个类似于对角矩阵形态的方程，注意到此时我们得到了n个形如 的一元一次方程，此时答案即为 。需要去判断下每个方程中的 是否为0，不然就没有解。
洛谷-P4783 [模板]矩阵求逆：记录详情
求一个矩阵对于单元矩阵的逆矩阵，那么我们考虑将这个矩阵拉长一倍后，把后半个矩阵赋为单元矩阵，然后做一遍高斯消元法，不过这个高斯消元有别于我们通常所为，我们需要在每次操作完一次更新单元矩阵。
证明先留个位置，咕咕，这个需要有时间再手推一下。
CF1399F-Yet Another Segments Subset
胖老师又在群里留了一道题，cfdiv3的f题，2300分，打算回寝室后想下。
2020/09/04
第二节晚自习过来，先帮 调了有一道线段树板子，发现有很多问题，稍微跟他讲解了一下一个大概的线段树写题过程。然后注意一下细节的处理，比如下传标记时的先后顺序，特判，和答案更新。
然后本来想写下昨天那题，原本晚上回寝室后有些思路，先把他写出来后就发现有一个问题，在于如何计算一个区间内最大可以容纳的合法区间数量。
我惊奇的发现我把数据范围看错了，我以为需要一个 的算法，然而数据实际支持 甚至 的算法复杂度。
然而我好像依旧没有什么思路，先咕咕了。
2020/09/05
星期六，整个白天都会在培训室搞OI，想着还是挺舒服的。
上午早上7点25左右到了培训室，然后匆忙吃了早餐。7:30~8:00是日程安排上的培训室早读时间，稍微有把《归去来兮辞》背了会，昨天默写没过关，明几天还要重默。然后8点多一点就到大机房去学习状压dp了，还挺期待的。
状压dp还挺自然地，把状态压成二进制甚至多进制，然后支持位运算予以状态转移。许老师讲了这样一句话，感觉挺赞同的，“状压dp与其称之为状压，不若说是一种集合dp”。的确，我们的状态其实就是一个集合内考虑哪些元素会被选取。同时，因为我们的复杂度通常都是指数级别的，看到一道题的数据范围就可以很快联想到状压dp来。
“我们考虑设计状态，是需要能够完整描述当前信息的节点”。
上午的话，就先写了三道最最基础的状压dp，也算是“哈密尔顿路径问题”的变种。
洛谷-P1433 吃奶酪：记录详情
洛谷-P1171 售货员的难题：记录详情
洛谷-P1278 单词游戏：记录详情
然后就有一道稍微难写的题目。
洛谷-P1283 平板涂色：记录详情
大概考虑选取哪些矩形，然后如果存在某一个矩形上部分为空，或者下部分为实，那么就算是非法转移（因为我们的加入是存在顺序的）。
中午准备吃饭时看了下高一他们考的一套题，XRZ差点AK（居然写挂尛你），第三道题看上去非常简单可做，但是手上没得纸笔，又没有凭空计算的能力，就先搁下了。
下午看到了xiyihan写的一道题目，恰好是一道高斯消元的裸题，正好最近刚学，就写了一发。
洛谷-P2455 [SDOI2006]线性方程组：记录详情
80pts。然而就是一个判断无解和无数解的地方卡壳了。我稍微想了些许，觉得是精度的问题（因为一开始我的精度只开到了1e-6，别问我怎么想的），然而改了精度到1e-9后也有问题。于是再想到无解的情况就是可能出现消元后出现类似0=1或者0=0的情况，然后手写了一个暴力特判的东西发现只能拿90pts。前前后后改了不下6次，然后实在想不出法子，也调了蛮久，就去看了下题解。
“消元时如果存在一些主元的系数全部为0，则将这些主元留到最后消，否则会造成某些主元系数无法消除的情况。”（此处摘自原题解 题解 P2455 [SDOI2006]线性方程组-市之濑莉佳）。大概就是考虑一些调换枚举消元顺序的操作，然后保证消元的过程合法有效。
然后当时看题解还没看完，就到了胖头鱼教练的第一节课。首先我们听了一个关于他的自我介绍，总的来说就是一个AFoier高校毕业后职场失意偶遇知音，占尽天时地利人和，然后刚好到了我们学校欲振兴本校信息学的热血经历（如果换成他的原述可能更加狗血，并且“言语粗鄙”），当然这些也使我更发现了许老师的随和大气的人格特点。
然后就由一道题目开始了他的精彩表演。
ATCoder-[ABC176]F - Brave CHAIN
题目大意：有3n张牌排成一行，面值为1~n。每次操作你可以重新调整最左五张牌的顺序，然后删除最左的三张牌。如果这三张牌面值相同的得一分。操作完最后还剩三张牌如果面值相同也得1分。求最大得分。
我们考虑暴力设计状态，表示第i次操作时此时现有的两张牌为j和k，然后再和剩下的3张牌进行组合，可以做到 的复杂度。然而我们发现对于其中大部分的转移其实都是浪费无用的，这是我们可以考虑再处理完每次状态后维护一下仅对于下一次操作产生影响的可能转移方案的可能值。
然后，我们现在稍加阐述一下胖老师的一套理论：我们所熟知的dp，其实可以看成是在一张 DAG，每个点可以看成维护的状态，而边就是我们可以进行的转移方程。那么，我们首要需要做的，是把这个 DAG 上的转移方向确定，即我们需要对于这些边的枚举顺序有一个拓扑序。那么就会引出诸如扩散型，收集型，甚至是记忆化搜索之类的多种处理方案。而对于每种方案，他们都有他们独特的共性。而我们所需要的，就是通过依赖共性和特性来达到优化算法时空复杂度的目的。