ioid1t2

· · 个人记录

做 70。

排序后匹配，那就枚举排列。

1. h_i=j-i,h_j=k-j,h_k=k-i

变形以后是 j=h_i+i,k=h_j+j，枚举 i 即可确定 3 个，判定合法性即可。

2. h_i=k-j,h_j=j-i,h_k=k-i

变形以后是 i=j-h_j,k=h_i+j，枚举 j 即可确定 3 个，判定合法性即可。注意要保证 k-j\neq j-i，不然会和上面那种情况重复算。

3. h_i=j-i,h_j=k-i,h_k=k-j

变形以后是 j=h_i+i,k=h_j+i，枚举 i 即可确定 3 个，判定合法性即可。

注意要保证 k-j\neq j-i，因为下面一种比较难算，让他自由点。

4. \color{red}h_i=k-j,h_j=k-i,h_k=j-i

不太显然。我转化到在网格图里数 2n 个点围成的矩形数量，其中一个点必须在主对角线上。还不会。

好像可以根号分治，想一想。

暴力应该可以复杂度分析出一个 n\sqrt{n} 的东西。

5. h_i=k-i,h_j=j-i,h_k=k-j

变形后是 i=j-h_j,k=h_i+i，枚举 j 即可确定 3 个，判定合法性即可。

6. h_i=k-i,h_j=k-j,h_k=j-i

变形后是 k=h_i+i,j=h_k+i，枚举 i 即可确定 3 个，判定合法性即可。注意要保证 k-j\neq j-i，不然会和上面那种情况重复算。