10-20 Extra-Problem 总结
AtCoder abc280_g
发现点 \((x,y)\) 的距离实际上是 \(\max(|x|,|y|,|x-y|)\)。由于坐标是可平移的，所以 \((x_1,y_1),(x_2,y_2)\) 的距离为 \(\max(|x_1-x_2|,|y_1-y_2|,|(x_1-x_2)-(y_1-y_2)|)\)，等于 \(\max(|x_1-x_2|,|y_1-y_2|,|(x_1-y_1)-(x_2-y_2)|)\)。
令 \(z_i=x_i-y_i\)，所以原问题相当于三维空间上选出 \((x_i,y_i,z_i)\) 使得在一个 \(D\) 边长立方体内。
依次枚举 \(x_i,y_i,z_i\) 的最小值分别是哪个点，这里的最小值指序列上的最小值，排序后只与下标有关，这样就不用容斥。
还要处理 \(x_i,z_i\)、\(y_i,z_i\)、\(x_i,y_i,z_i\) 的最小值是同一个点的情况。
AtCoder abc271_h
考虑分讨，先去掉没有用的情况，然后合并本质一样的情况。
发现最多选出三种操作，因为不能同时选相对的，而且不能同时选 \(1,2,3\) 之类。这样发现选三种当且仅当选 \(2,4,6,8\) 中两个，再选 \(1,3,5,7\) 中一个。
接下来分讨时要合并本质一样的情况，即不考虑旋转同构的情况。有以下几种：
- 不选。
- 1。
- 2。
- 1、2。
- 1、3。
- 1、4。可以考虑先走到对应的 \(y\) 坐标。
- 1、6。可以考虑先走到对应的 \(y\) 坐标。
- 1、8。
- 2、4。
- 2、3、4。发现只会走一次 3。
- 2、1、4。发现只会走一次 1。
- 2、5、4。发现只会走一次 5。
- 2、7、4。发现只会走一次 7。
AtCoder abc291_g
可以卷积，把 \(a\) 复制一遍，\(b\) 翻转过来卷积，需要求
\[\sum _{i+j=k} a_i\lor a_j
\]
可以先把每一位单独考虑，然后转化成用 \(n\) 减去：
\[\sum _{i+j=k} (a_i=0)\times(a_j=0)
\]