A - Almost Correct 另一种相似的构造

Link

题意

给定 $0101$ 串 $a_1{a}_2\dots a_{n}a\_1a\_2\backslash dots\; a\_n$ 长度为 $nn$ $(n\le 16)(n\; \backslash le\; 16)$。构造一个排序网络，使其能恰好能排序除给定 $0101$ 串外的所有长度为 $nn$ 的 $0101$ 串。排序网络所需的步骤 $m\le 120m\; \backslash le\; 120$。其中，排序网络指的是：给定 $\{(x_m,y_m)\}\backslash \{(x\_m,\; y\_m)\backslash \}$，$ii$ 按照 $11$ 到 $nn$ 进行遍历，若 $a_{xi}>a_{yi}a\_\{xi\}>a\_\{yi\}$ 则交换 $a_{xi},a_{yi}a\_\{xi\},a\_\{yi\}$ 。

这不比官方题解写的清楚

一种构造方案

• 记所有 $0101$ 串 $aa$ 中 $11$ 所在位置下标的集合 $SS$ 。找到 $SS$ 的最小值（即 $0101$ 串中 $11$ 所在的最左侧位置），记为 $curcur$。记 $SS$ 的元素个数（即 $11$ 的个数）为 $\mathrm{\mid }S\mathrm{\mid }|S|$。

• 交换 $curcur$ 和 $SS$ 中的其他元素，即 $\mathrm{\forall }x\in S,(x,cur)\backslash forall\; x\backslash in\; S,\; (x,\; cur)$。

• 对剩下的 $0101$ 串 $\{1,2,3,\dots ,n\}\mathrm{-}\{cur\}=\{1,2,\dots cur\mathrm{-}1,cur+1,\dots ,n\}\backslash \{1,\; 2,\; 3,\backslash dots,\; n\backslash \}-\backslash \{cur\backslash \}=\backslash \{1,\; 2,\backslash dots\; cur\; -\; 1,\; cur\; +\; 1,\backslash dots,\; n\backslash \}$ 正常进行排序（参照冒泡排序），即去掉下标 $curcur$ 后对其他元素排序。

• 依次交换 $(1,cur),(2,cur),\dots ,(cur-1,cur),(cur,n-(\mathrm{\mid }S\mathrm{\mid }-1)-1)),(cur,n-(\mathrm{\mid }S\mathrm{\mid }-1)-2)),(cur,n-(\mathrm{\mid }S\mathrm{\mid }-1)-3)),\dots ,(cur,cur+1))(1,cur),(2,cur),\backslash dots,(cur-1,cur),(cur,n-(|S|-1)-1)),(cur,n-(|S|-1)-2)),(cur,n-(|S|-1)-3)),\backslash dots,(cur,\; cur+1))$

面向萌新的解释与说明

以下内容，为方便理解，将争对给定串 $a=001010110a=001010110$ 进行举例说明。

• 记所有 $0101$ 串 $aa$ 中 $11$ 所在位置下标的集合 $SS$ 。找到 $SS$ 的最小值（即 $0101$ 串中 $11$ 所在的最左侧位置），记为 $curcur$。记 $SS$ 的元素个数（即 $11$ 的个数）为 $\mathrm{\mid }S\mathrm{\mid }|S|$。

  • 首先，$\mathrm{\mid }S\mathrm{\mid }≠0|S|\backslash not=0$；若 $\mathrm{\mid }S\mathrm{\mid }=0|S|=0$，则 $0101$ 串全由 $00$ 组成，已经被排好序了。

  • 对于给定串 $a=001010110a=001010110$ ，$cur=3,S=\{3,5,7,8\},\mathrm{\mid }S\mathrm{\mid }=4cur=3,\; S=\backslash \{3,5,7,8\backslash \},|S|=4$。

• 交换 $curcur$ 和 $SS$ 中的其他元素，即 $\mathrm{\forall }x\in S,(x,cur)\backslash forall\; x\backslash in\; S,\; (x,cur)$。

  • 此步骤中，对于任意给定 $0101$ 串没有发生变化，例如给定串 $a=001010110a=001010110$ 进行了 $(3,5),(3,7),(3,8)(3,5),\; (3,7),\; (3,8)$ 的交换。

  • 而对于非给定串 $bb$ ：

    情况 $11$：若对于任意位置 $x\in S,b_x=1x\; \backslash in\; S,\; b\_x=1$，例如 $b=001010111b=001010111$ ，则非给定串 $bb$ 没有发生变化。而非给定串 $bb$ 又与给定串 $aa$ 不完全相同，即 $bb$ 中 $11$ 的个数 $>\mathrm{\mid }S\mathrm{\mid }>|S|$。

    情况 $22$：若 $b_{cur}=0b\_\{cur\}=0$，例如 $b=010010110b=010010110$ ，由于$x\in S,x\ge curx\; \backslash in\; S,\; x\; \backslash ge\; cur$，所有交换都与 $curcur$ 右边的数进行交换，此时 $bb$ 也没有发生变化。

    情况 $33$：若 $b_{cur}=1b\_\{cur\}=1$，存在$x\in S,b_x=0x\; \backslash in\; S,\; b\_x=0$，例如 $b=001010101b=001010101$ ，由于$x\in S,x\ge curx\; \backslash in\; S,\; x\; \backslash ge\; cur$，所有交换都与 $curcur$ 右边的数进行交换，且有 $b_x=0b\_x=0$，故此时 $bb$ 中 $b_{cur}=0b\_\{cur\}=0$。

    总结：经过此操作后，要么 $b_{cur}=0b\_\{cur\}=0$，要么 $b_{cur}=1b\_\{cur\}=1$ 且 $bb$ 中 $11$ 的个数 $>\mathrm{\mid }S\mathrm{\mid }>|S|$。

  • 此过程中用了 $\mathrm{\mid }S\mathrm{\mid }-1|S|-1$ 步。

• 对剩下的 $0101$ 串 $\{1,2,3,\dots ,n\}\mathrm{-}\{cur\}=\{1,2,\dots cur\mathrm{-}1,cur+1,\dots ,n\}\backslash \{1,\; 2,\; 3,\backslash dots,\; n\backslash \}-\backslash \{cur\backslash \}=\backslash \{1,\; 2,\backslash dots\; cur\; -\; 1,\; cur\; +\; 1,\backslash dots,\; n\backslash \}$ 正常进行排序（参照冒泡排序），即去掉下标 $curcur$ 后对其他元素排序。

  • 此步骤中，对于给定串 $a=001010110a=001010110$，除下标为 $curcur$ 的元素外进行冒泡排序后，得到 $a^{\mathrm{\prime }}=001000111a\text{'}=001000111$。

  • 对于非给定串 $bb$ ：

    情况 $11$：$b_{cur}=0b\_\{cur\}=0$；此时要么 $b^{\mathrm{\prime }}b\text{'}$ 已经是排好序的，例如： $b^{\mathrm{\prime }}=000011111b\text{'}=000011111$；要么 $b^{\mathrm{\prime }}b\text{'}$ 是形如$010111111010111111$，第 $curcur$ 位两边均为 $11$ 且除了下标为 $curcur$ 已经是排好序的。

    情况 $22$：$b_{cur}=1b\_\{cur\}=1$ 且 $bb$ 中 $11$ 的个数 $>\mathrm{\mid }S\mathrm{\mid }>|S|$；此时要么 $b^{\mathrm{\prime }}b\text{'}$ 是形如 $001011111001011111$，其中原来 $a^{\mathrm{\prime }}a\text{'}$ 中最右侧的 $00$ 在 $b^{\mathrm{\prime }}b\text{'}$ 中一定是 $11$ ，即第 $n-(\mathrm{\mid }S\mathrm{\mid }-1)n-(|S|-1)$ 位一定是 $11$ ；要么 $b^{\mathrm{\prime }}b\text{'}$ 已经是排好序的例如： $b^{\mathrm{\prime }}=011111111b\text{'}=011111111$。

    总结： $b^{\mathrm{\prime }}b\text{'}$ 要么是已经排好序的，不继续考虑；要么 $b_{cur}^{\mathrm{\prime }}=0b\text{'}\_\{cur\}=0$ 且 $b_{cur-1}^{\mathrm{\prime }}=1b\text{'}\_\{cur-1\}=1$ ；要么 $b_{cur}^{\mathrm{\prime }}=1b\text{'}\_\{cur\}=1$ 且 $b_{n-(\mathrm{\mid }S\mathrm{\mid }-1)}^{\mathrm{\prime }}=1b\text{'}\_\{n-(|S|-1)\}=1$。

  • 此过程中用了 $\frac{(n-1)(n-2)}{2}\backslash frac\{(n-1)(n-2)\}\{2\}$ 步。

• 依次交换 $(1,cur),(2,cur),\dots ,(cur-1,cur),(cur,n-(\mathrm{\mid }S\mathrm{\mid }-1)-1)),(cur,n-(\mathrm{\mid }S\mathrm{\mid }-1)-2)),(cur,n-(\mathrm{\mid }S\mathrm{\mid }-1)-3)),\dots ,(cur,cur+1))(1,\; cur),\; (2,\; cur),\; \backslash dots,\; (cur-1,\; cur),\; (cur,\; n-(|S|-1)-1)),\; (cur,\; n-(|S|-1)-2)),\; (cur,\; n-(|S|-1)-3)),\; \backslash dots,\; (cur,\; cur+1))$

  • 下标 $n-(\mathrm{\mid }S\mathrm{\mid }-1)n-(|S|-1)$ 表示为 $a^{\mathrm{\prime }}a\text{'}$ 最左侧 $00$ 的位置。对于给定串 $a^{\mathrm{\prime }}=001000111a\text{'}=001000111$ ，最后的结果为 $000010111000010111$，在下标为 $n-(\mathrm{\mid }S\mathrm{\mid }-1),n-(\mathrm{\mid }S\mathrm{\mid }-1)-1n-(|S|-1),\; n-(|S|-1)-1$ 处是乱序的。

  • 对于非给定串 $b^{\mathrm{\prime }}b\text{'}$ ：

    情况 $11$：$b_{cur}^{\mathrm{\prime }}=0b\text{'}\_\{cur\}=0$ 且 $b_{cur-1}^{\mathrm{\prime }}=1b\text{'}\_\{cur-1\}=1$，形如 $010111111010111111$，进行操作 $(1,cur),(2,cur),\dots ,(cur-1,cur)(1,\; cur),\; (2,\; cur),\; \backslash dots,\; (cur-1,\; cur)$ 可将最右侧的 $00$ 移动到最左侧的 $11$ 的左侧，即让结果为顺序的。

    情况 $22$：$b_{cur}^{\mathrm{\prime }}=1b\text{'}\_\{cur\}=1$ 且 $b_{n-(\mathrm{\mid }S\mathrm{\mid }-1)}^{\mathrm{\prime }}=1b\text{'}\_\{n-(|S|-1)\}=1$，形如 $001001111001001111$；进行操作 $(1,cur),(2,cur),\dots ,(cur-1,cur)(1,\; cur),\; (2,\; cur),\; \backslash dots,\; (cur-1,\; cur)$ 对 $b^{\mathrm{\prime }}b\text{'}$无影响；进行操作 $(cur,n-(\mathrm{\mid }S\mathrm{\mid }-1)-1)),(cur,n-(\mathrm{\mid }S\mathrm{\mid }-1)-2)),(cur,n-(\mathrm{\mid }S\mathrm{\mid }-1)-3)),\dots ,(cur,cur+1))(cur,\; n-(|S|-1)-1)),\; (cur,\; n-(|S|-1)-2)),\; (cur,\; n-(|S|-1)-3)),\; \backslash dots,\; (cur,\; cur+1))$ 可将最左侧的 $11$ 移动到最右侧的 $00$ 的右侧，即让结果为顺序的。

    总结：非给定串 $bb$ 经过操作均是顺序的。

  • 此过程中用了 $n-(\mathrm{\mid }S\mathrm{\mid }-1)-1-1=n-\mathrm{\mid }S\mathrm{\mid }-1n-(|S|-1)-1-1=n-|S|-1$ 步。

• 总计用了 $\mathrm{\mid }S\mathrm{\mid }-1+\frac{(n-1)(n-2)}{2}+n-\mathrm{\mid }S\mathrm{\mid }-1=\frac{(n-1)(n-2)}{2}+n-2|S|-1+\backslash frac\{(n-1)(n-2)\}\{2\}+n-|S|-1=\backslash frac\{(n-1)(n-2)\}\{2\}+n-2$ 步，$n=16n=16$ 时最大值为 $119\le 120119\; \backslash le\; 120$

这比官方题解好理解

Code

  int ansx[300]={},ansy[300]={},cnt=0;
  int a[20],n;read(n);
  rep(i,1,n+1)scanf("%1lld",&a[i]);
  int num=0,cur=10000;
  rep(i,1,n+1)num+=a[i];
  rep(i,1,n+1)if(a[i])ckmin(cur,i);
  rep(i,1,n+1)if(i!=cur&&a[i]){
    ansx[++cnt]=min(i,cur),ansy[cnt]=max(i,cur);
  }
  rep(i,1,n){
    rep(j,1,n-i)ansx[++cnt]=(j>=cur?j+1:j),ansy[cnt]=(j+1>=cur?j+2:j+1);
  }
  rep(i,1,cur)ansx[++cnt]=i,ansy[cnt]=cur;
  nrep(i,n-num,cur+1)ansx[++cnt]=cur,ansy[cnt]=i;

后记

写这篇题解，是为了铭记那些犯脑梗的我们。

此题，这是我们的输出（赛时，队友和我分别至少调了 $1.5h1.5h$，还没看出来）：

  if(cnt){
    rep(i,1,cnt+1)print(ansx[i],' ');puts("");
    rep(i,1,cnt+1)print(ansy[i],' ');puts("");
  }

这是要求的输出：

In the $ii$-th of the next $mm$ lines, print $x_{i}x\_i$ and $y_{i}y\_i$ () separated by a space.