- CF1815B Sum Graph 考虑肯定要把图建成一个特殊形态,考虑链。指定x分别为\(n+1,n+2\)即可做到,这个时候链的实际形态已经确定下来(这里预处理出来链的实现没有想到)。有了链查询n-1次与\(p_1\)的距离,最长的肯定是一个链顶。但注意到是无向图,所以是哪个链顶都有可能,对应了猜两种方案,最后一一确定链上位置就行。code
- CF1815C Between 先考虑怎么求出长度。每两个a中包含一个b可以转化为个数限制,b的个数不大于a的个数+1.这个形式类似于差分约束,但是边权为1,bfs就能做到。无解就是有点连不到1。现在已知出现次数,手模发现次数一样的放一起成固定顺序的一串,不管其中内部有什么限制都可以解决,然后在每个i串前面加入的i+1的串,整个串末尾再加一个。递归实现。code
- CF1816B Grid Reconstruction 被创飞。想到的话考虑整个走的过程,保证当前相同步数下最大最小差值尽可能小,发现可以构造成1。严谨证明考虑左上右下两段,较小段的上界为其和/2(这里是较小段,如果不是最优相较于确切上界是偏大的,最小段上界的限制应该更严一些),这个东西刚才的构造取得到,所以严格一些也得证。