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)
\]