Atcoder abc336
https://atcoder.jp/contests/abc336
F - Rotation Puzzle
h行w列, 数字$[1,hw]$每个出现一次
一次操作 选取$(h-1)\cdot(w-1)$的矩形 旋转180度
问是否能让20次操作内，所有数字 变成 从小到大 从左到右从上到下 的样子
1 | 1 2 3 4 |
h,w [3,8]
5s
1024mb
我的思路
如果单独考虑x的变化
从中线划分
那么左侧的x，在左侧矩形选择翻转时，它变为右侧，且和边界距离+1
那么右侧的x，在左侧矩形选择翻转时，它变为左侧，且和边界距离-1
感觉 有用但又没有用
另一个想法就是meet-in-middle + 暴力搜索, 因为一个操作立刻反向操作 等于没操作，所以除了首次操作 后续的操作都 3分叉，数据量看起来是能接受的
$3^{10}\cdot 8\cdot 8=3779136$
哎, 本来以为什么神奇性质题，结果无聊的meet-in-middle
题解
代码
总结
F: meet-in-middle 没啥难的