zr 2020 0504 T3 and 0505 T2【神奇排序题 (构造)】

0504 T3：

题目描述：

$n\le15000,m\le30$n≤15000,m≤30

题目分析：

因为这个题只需要在限制次数内排好，而不要求最小次数，所以我们要通过上面这个方式构造出一个可行解。
记每个数字 $i$i 对应上面的位置为 $rank[i]$rank[i]。为了方便理解，我们先用比较简单的情况$n=8$n=8举例：
待排序的序列为：$0~3~5~1~2~4~7~6$0 3 5 1 2 4 7 6
我们想要把它排成：$0~4~2~6~1~5~3~7$0 4 2 6 1 5 3 7，这样只需要将$1~3$1 3放到前面，$2~4$2 4放到后面就排好了。
我们求出每个数字在想要的排列中对应的$rank$rank数组：$0~3~2~1~1~2~3~0$0 3 2 1 1 2 3 0 （对于奇数，用$7$7减去原本的$rank$rank，后面会解释）
首先将偶数放到前面，奇数放到后面，$s[1\sim n]=0$s[1∼n]=0，得到：$0~2~4~6~3~5~1~7$0 2 4 6 3 5 1 7
然后按照$rank$rank的二进制表示从低位到高位基数排序：
第一轮：
对于$rank[i]>>0\&1$rank[i]>>0&1的$i$i，则$s[i]=1$s[i]=1，否则$s[i]=0$s[i]=0。并把对应的偶数放到后面，奇数放到前面。
要移动的偶数为$4~6$4 6，要移动的奇数为$1~3$1 3。得到：$0~2~3~1~4~5~6~7$0 2 3 1 4 5 6 7
然后将偶数放到前面，奇数放到后面，得到：$0~2~4~6~3~1~5~7$0 2 4 6 3 1 5 7
这一轮的效果是：偶数奇数已经分别按照最终rank的二进制第0位有小到大排好了！
第二轮：
对于$rank[i]>>1\&1$rank[i]>>1&1的$i$i，则$s[i]=1$s[i]=1，否则$s[i]=0$s[i]=0。并把对应的偶数放到后面，奇数放到前面。
要移动的偶数为$2~6$2 6，要移动的偶数为$1~5$1 5。得到：$0~1~4~5~3~2~6~7$0 1 4 5 3 2 6 7
然后将偶数放到前面，奇数放到后面，得到：$0~4~2~6~1~5~3~7$0 4 2 6 1 5 3 7

然后就发现已经得到我们想要的排列了！
这样做的原理是：对于偶数$rank[i]>>j\&1$rank[i]>>j&1的 $i$i 我们将它放到右边，然后再按顺序放回来，相当于就是基数排序。并且可以解释为什么上面要令7减去奇数的$rank$rank，这样原来为0的就会被放到左边。
这里有一个细节，就是必须要保证每次奇偶rank对应位等于1的个数是相同的，并且$rank$rank数组的求得也有点讲究（要使的最后能一步排好），总共有$4$4种情况分类讨论，可以列举$n=7,8,9,10$n=7,8,9,10来看一看。

二进制位总共是$\log n$logn位，最开始要奇偶分开，最后加1步，总共$1+13*2+1=28$1+13∗2+1=28步。
基数排序真是太强辣！

Code：

#include<bits/stdc++.h>
#define maxn 15005
using namespace std;
int T,n,m,rk[maxn],a[maxn];
void put(string s,bool t){
	printf("%d %s\n",t,s.c_str());
	vector<int>x[2];
	for(int i=0;i<n;i++) if(s[i]=='1') x[(a[i]&1)^t].push_back(a[i]);
	x[0].insert(x[0].end(),x[1].begin(),x[1].end());
	for(int i=0,j=0;i<n;i++) if(s[i]=='1') a[i]=x[0][j++];
}
int main()
{
	for(scanf("%d",&T);T--;){
		scanf("%d%d",&n,&m);
		for(int i=0;i<n;i++) scanf("%d",&a[i]);
		puts("28");
		int k=(n+1)/2,x=0;
		for(int j=0;x<k;j+=2,x+=2) rk[x]=j;
		for(int j=1;x<n;x+=2,j+=2) rk[x]=j;
		x=(n|1)-2;
		for(int j= n&1 ? 2 : 0; x>=k ; j+=2,x-=2) rk[x]=j;
		for(int j=1;x>0;j+=2,x-=2) rk[x]=j;
		put(string(n,'1'),0);
		for(int i=0;i<13;i++){
			string s(n,'0');
			for(int j=0;j<n;j++) if(rk[a[j]]>>i&1) s[j]='1';
			put(s,1);
			put(string(n,'1'),0);
		}
		string s(n,'0');
		for(int i=0;i<n;i++) if(a[i]!=i) s[i]='1';
		put(s,1);
	}
}

---

0505 T2

题目描述：

$n\le5*10^4$n≤5∗104

题目分析：

模仿上面的做法，很容易让人想到基数排序，但是这道题要求最少的操作次数，subtask一下基数排序就会获得0分的好成绩（比如我）。

首先我们要证明答案的下界，然后构造达到这个下界的操作方法。

令$q=p^{-1}$q=p−1，即$q[p[i]]=i$q[p[i]]=i，把$q$q中极长的连续、递增的区间称之为一段。考虑任意两段的最后一个数$x,y$x,y，我们可以证明它们的操作序列不同（在某一轮中$w[x]\neq w[y]$w[x]​=w[y]）。
使用反证法，若$q_x>q_y$qx​>qy​那么最后$x$x在$y$y之后显然不行。若$q_x<q_y$qx​<qy​则存在$x<z<y$x<z<y使得$q_x>q_z$qx​>qz​，此时无论怎么操作$z$z都不能变到$x$x和$y$y之间。得证
假设存在$k$k段，则至少存在$k$k种不同的操作序列，如果答案为$ans$ans，则$2^{ans}\ge k$2ans≥k，这给出了答案的下界$\lceil\log_2 k\rceil$⌈log2​k⌉。
为了构造得到这个下界，每次操作中把段从左到右编号（从$1$1开始），并选出所有奇数段放到偶数段之
前，这样第 $2i-1$2i−1 段和第 $i$i 段合并，于是段数变为$\lceil\frac k2\rceil$⌈2k​⌉，不断这么做就构造完了。具体实现时在第$i$i轮选择所在段的二进制减1后第$i$i位为0的数令它的$w=1$w=1即可，可以看出操作次数恰为$\lceil\log_2 k\rceil$⌈log2​k⌉。

Code（stable_partition表示将一个序列中布尔表达式为0的数放到左边，为1的放到右边，并且同一边的不改变原来的相对位置）：

#include<bits/stdc++.h>
#define maxn 50005
using namespace std;
int n,T,a[maxn],q[maxn],id[maxn],ans,d;
bool cmp(int i){return (id[i]>>d&1)==0;}
void write(){for(int i=1;i<=n;i++) printf("%d%c",a[i],i==n?10:32);}
int main()
{
	scanf("%d%d",&n,&T);
	for(int i=1;i<=n;i++) scanf("%d",&a[i]),q[a[i]]=i;
	int k=0;
	for(int i=1;i<=n;i++) id[i]=q[i]>q[i-1]?k:++k;
	for(ans=0;1<<ans<=k;ans++);
	printf("%d\n",ans);
	if(T){
		write();
		for(d=0;d<ans;d++) stable_partition(a+1,a+1+n,cmp),write();
	}
}