LG9979 [USACO23DEC] Target Practice S
LG9980 [USACO23DEC] Flight Routes G
sol 1
已知邻接矩阵求路径数奇偶性是容易的，倒着做即可
bitset 实现。时间复杂度 \(O(\frac{n^{3}}{\omega})\)
sol 2
矩阵求逆
LG9981 [USACO23DEC] Minimum Longest Trip G \(\star\)
sol 1
倍增+哈希
sol 2
考虑类似后缀平衡树的做法
DP 完最长路后按长度从小到大处理。设 \(rk[u]\) 为点 \(u\) 开始的字符串在同长度字符串中的排名，利用二元组 \((w,rk[v])\) 即可快速比较字典序
LG9982 [USACO23DEC] Haybale Distribution G
显然最优位置在谷仓上
key observation：设有 \(i\) 个点的坐标 \(\le x\)，则从 \(x\) 移到 \(x+1\) 的增量为 \(ai+b(n-i)=(a+b)i-bn\)，从左到右是递增的
做法很多：
- 三分答案（注意可能有重点，需要离散化或在值域上三分）
- 二分增量变号的位置
- 直接解出增量变号的位置
LG9984 [USACO23DEC] A Graph Problem P \(\star\)
维护的信息等价于哈希，容易合并
题目给的算法是 prim，注意到 MST 唯一且任意时刻点集 \(S\) 都是 MST 的一个子树
考虑 kruskal。用边 \((u,v)\) 合并连通块时，任意 \(u\) 连通块中点的扩展顺序一定是 \(u\) 连通块 \(\rightarrow v\rightarrow v\) 连通块，且扩展 \(v\) 连通块的顺序与 \(v\) 相同