2022 2.8-2.11学习笔记

用作个人记录。
2021.12.18
C1766 【插头DP】
过程:换行时舍去不合法的状态；实质是维护轮廓线的状态。对接下来要连线的地方进行预判（表现为插头有或无）。初状态：dp[0][m][0]=1末状态：此题为完成填充，即最后一个格子（可以打标记，也可以障碍格转移）转移：可以正推，也可以逆推 都要判断当前格子是否合法

C1767【插头DP】
延续了模板的思路，多了一种状态 用四进制会更快
-进制怎么处理好？
-如何快速写出下一个状态？

C1769【连通性】
引进了连通性的概念，如何维护？

2022.2.8 数据结构
P4681[THUSC2015]平方运算  【线段树】【复杂度分析】
思路：由于平方后产生的数具有周期性（我的理解：因为这是有穷个，哪怕多，最终一定会落回来），所以对于数据，可以分两步处理：
第一步，暴力走完周期前面的路；
第二步，批量处理周期后面的路。
对于第一步，暴力打表发现其不会超过常数级别的步数。故复杂度为O(11n)左右
对于第二步，同样打表找环取最小公倍数，得最大的最小公

2022 2.8-2.11学习笔记最先出现在Python成神之路。