2023 牛客暑期多校
7.17
我正开，D
gjk 倒开，AHJKLM
A - Almost Correct
设 \(s\) 中 \(0\) 的下标集合为 \(S_{0}\)，\(1\) 的为 \(S_{1}\)，最右边的 \(0\) 的下标 \(r\)，最左边 \(1\) 的下标 \(l\)。\(s\) 没有排好序所以 \(l\le|S_{1}|<r\)
- \(\forall i\in S_{0},(i,r)\)
\(\forall i\in S_{1},(l,i)\) - 把 \(\{1,2,\cdots n\}\setminus\{l,r\}\) 排序
- \((|S_{0}|+1,r),(|S_{0}|+2,r),\cdots,(r-1,r),(r,n),(r,n-1),\cdots,(r,r+1)\)
\((l,|S_{0}|),(l,|S_{0}|-1),\cdots,(l,l+1),(1,l),(2,l),\cdots,(l-1,l)\)
操作次数 \(n-2+\frac{(n-2)(n-3)}{2}+n-2=119\)
证明：
- 对于 \(s\)：第二步后 \(\{1,2,\cdots,|S_{0}|\}\setminus\{l\}\cup\{r\}\) 为 \(0\)，其余位置为 \(1\)。第三步会 \(swap(|S_{0}|+1,r),swap(l,|S_{0}|)\)，形成 \(00\cdots01011\cdots1\)
- 对于 \(t\ne s\)，\(|T_{0}|\ge |S_{0}|\)：\(S_{1}\) 中一定有一个位置为 \(1\)，第一步会使 \(t[l]=0\)。第二步后前 \(|S_{0}|\) 个位置都为 \(0\)，\(t[1,r-1],t[r+1,n]\) 分别有序。第三步若 \(t[r]=0\)，会与最左边的 \(1\) 交换，若 \(t[r]=1\)，会与最右边的 \(0\) 交换
- 对于 \(t\ne s\)，\(|T_{1}|>|S_{1}|\)：同理
D - Chocolate
假设先手拿 \((1,1)\)，若后手拿 \((i,j)\) 必胜则先手可以第一次就拿 \((i,j)\) 抢走必胜态
\(n=m=1\) 后手胜