考虑一个函数\(f(a)\),它的返回值是一个二维数组\(b\),接受值是一个数组\(a\)。
对于所有\(i=1\to n-1\)的\(i\),把\(b_{a_i}{a_{i+1}}++\),然后返回\(b\)。
\(f(a)!=f(b)\)且\(a_1=b_1,a_n=b_n\)是无解的充要条件,因为显然对于数组的每次翻转操作它的\(f\)返回值都不会变。\(f(a)!=f(b)\)则无论怎么操作\(a\)它的返回值都不会变。并且无论怎么翻转数组的首末项都不会变,\(a_1!=b_1\)或\(a_n!=b_n\)就无解,充分性得证。
考虑证明必要性,使用归纳法,考虑现在的数组\(a\),\(a_1=b_1\),让\(a_2=b_2\)
分若干种情况讨论:
1.如果存在\(j\)使得\(a_{j}=b_{2}且\)a_{j+1}=b_1$,则进行操作\(1,j+1\)即可,删除\(a\),\(b\)数组的首项。
2.如果不存在\(j\)使得\(a_{j}=b_{2}且\)a_{j+1}=b_1\(,则显然存在\)j\(使得\)a_{j}=b_{1}且\(a_{j+1}=b_2\)
2.1 假设存在$$