“范式杯”2023牛客暑期多校训练营1

A Almost Correct

题意

给定一个 $01$ 串 $s$，长度为 $n$。要求构造一个长度不超过 $120$ 的排序网络，使得该网络恰好能排序除给定串以外的所有长度为 $n$ 的 $01$ 串。保证 $s$ 是未排序的。

其中，排序网络指的是数组 $\{(x_1,y_1),(x_2,y_2),\cdots,(x_m,y_m)\}$。依次遍历数组，若 $a_{x_i}>a_{y_i}$，则交换 $a_{x_i},a_{y_i}$。

数据范围：$2\leq n\leq 16$。

题解

记 $s$ 中所有 $1$ 的位置为集合 $S$，其中最左边一个 $1$ 的位置记为 $pos$。

1. 交换 $(i,pos)$，$i$ 为集合 $S$ 内的所有元素。
2. 对除 $pos$ 以外的位置进行冒泡排序。
3. 交换 $(1,pos),(2,pos),\cdots,(pos-1,pos),(pos,n-|S|),(pos,n-|S|-1),\cdots,(pos,pos+1)$。

下面证明这种做法的正确性：

首先，考虑它的最大交换次数（即排序网络的长度）：当 $n=16$ 时，交换次数为 $|S|-1+\dfrac{(n-2)\times(n-1)}{2}+n-|S|-1=119<120$。

然后，考虑它的有效性：首先，集合 $S$ 一定非空，因为 $s$ 是未排序的，所以里面一定含有 $1$。我们分析每一步后的排序结果：

第一步：容易发现第一步对 $s$ 是没有意义的。对于其它的串，如果 $S$ 中含有 $0$，那么它一定会被放到 $pos$ 上，否则说明该串的这些位置也都是 $1$。但由于该串和 $s$ 不同，所以该串的 $1$ 的个数更多。

第二步：我们对除 $pos$ 以外的位置进行排序后，这些部分一定是相对有序的，即构成了 $00\cdots11$ 的形式。如果该串未被排序，说明 $a_{pos}$ 在最终排完的序列当中和目前的元素一定不同。即若 $a_{pos}=0$，那么目前的串一定形如 $0\cdots01\cdots1`0`1\cdots1$。或者 $a_{pos}=1$，形如 $0\cdots 0`1`0\cdots 01\cdots 1$。（用引号引起来的就是 $a_{pos}$）

第三步：我们先交换 $pos$ 和前面的位置，解决了前一种情况。而对于给定的 $s$，它必然也是形如后一种情况。但是，注意到我们在第一步中得到的结论，非 $s$ 的串 $1$ 的个数一定比它多，所以在 $s$ 的最后一个 $0$ 处，其余串一定是 $1$。所以，我们将该位置以前的所有位置与 $pos$ 交换，最终一定仅有 $s$ 未被排序。

代码

#include <bits/stdc++.h>
using namespace std;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t;cin>>t;
    while(t--)
    {
        int n;cin>>n;
        string s;cin>>s;
        int pos;
        vector<int> v;
        for(int i=0;i<n;i++)
            if(s[i]=='1') v.push_back({i+1});
        pos=v.front();
        vector<pair<int,int>> ans;
        for(auto i:v)
            if(i!=pos) ans.push_back({pos,i});
        for(int i=1;i<=n;i++)
        {
            if(i==pos) continue;
            for(int j=i+1;j<=n;j++)
                if(j!=pos) ans.push_back({i,j});
        }    
        for(int i=1;i<pos;i++) ans.push_back({i,pos});
        for(int j=n-v.size();j>pos;j--) ans.push_back({pos,j});
        cout<<ans.size()<<'\n';
        for(auto i:ans) cout<<i.first<<' '<<i.second<<'\n';
    }
    return 0;
}