做题记录

2023/9/21

• 关于选择策略题目算法选用的思考
  对于一个有着策略选择的模型，如果有确切的最优选择，就使用贪心，如果有确切的最劣选择，就使用反悔贪心
  而当可以在当前的空间大小存储下每个唯一的状态而且每个状态有着确定可以向下更新的状态集\(G(a)\)以及\(G(b)\)且\(G(a) \cap G(b) = \phi\)
  即状态图为一个DAG时，就可以使用DP

• 关于树剖的两点间操作会不会影响两者LCA的祖宗的思考
  我们假设\(\exists\)一个合法操作使我们的\(fa_{top_{x}}\)第一次为LCA的祖宗
  \(\therefore\)此时\(y\)必然是\(fa_{top_{x}}\)的祖宗，否则我们不会操作\(x\)（如果为自身那么两点在操作前必然已经在一条链上不会有下一次操作的出现）
  \(\because y\)必然不是LCA的祖宗，而是操作得到的
  \(\therefore\)必然存在一次操作使得\(fa_{top_{x}}\)为LCA的祖宗（我们操作的变量一律为\(x\)）
  \(\therefore\)与前文“第一次为LCA的祖宗”矛盾，故原命题为伪命题
  证毕

• 关于区间DP状态选择的思考
  要将转移相关的所有变量都存储进状态
  一个区间的贡献不一定是整个区间的贡献，而是区间内元素可以确定的贡献

• 关于割边的使用的思考
  割边有非常优秀的性质，即割边两边的元素若要连接，那必然会取这条割边
  这个优秀的性质可以快速地处理存在割边的图中边权相关的问题
  树中有大量的割边，所以可以大量地运用此性质