davidwang's Blog

首先对于一个按行向量排序的循环矩阵，任意两列都是一一对应的关系，于是我们只需要找到每行第一列和最后一列的对应关系就行了

结论1 : 第一行就是最后一行排序的结果

结论2 ：这个关系是一一对应的，而且对应后的逆结果便是原序列按照字典序第一关键字，位置第二关键字排序之后的位置

这样暴力sort可以解决，然后还可以高大上的用基数排序搞到O(n)

//coder: davidwang
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#define X first
#define Y second
using namespace std;
#define LL long long
inline int read(){
	int ret=0,f=1; char ch;
	for (ch=getchar();ch<'0' || ch>'9';ch=getchar())
		if (ch=='-') f=-f;
	for (;'0'<=ch && ch<='9';ch=getchar()) ret=ret*10+ch-48;
	return ret*f;
}
const int N = 200010;
pair<int,int>a[N];
int b[N],n,m;
int main()
{
	n=read(); m=read(); n++;
	for (int i=1;i<=n;i++) b[i]=read(),a[i]=make_pair(b[i],i);
	sort(a+1,a+n+1);
	for (int now=a[a[1].Y].Y;b[now];now=a[now].Y){
		printf("%d ",b[now]);
	}
}

//coder: davidwang
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#define X first
#define Y second
using namespace std;
#define LL long long
inline int read(){
	int ret=0,f=1; char ch;
	for (ch=getchar();ch<'0' || ch>'9';ch=getchar())
		if (ch=='-') f=-f;
	for (;'0'<=ch && ch<='9';ch=getchar()) ret=ret*10+ch-48;
	return ret*f;
}
const int N = 200010;
int n,m,a[N],cnt[N],next[N],now;
int main()
{
#ifndef ONLINE_JUDGE
	freopen("a.in","r",stdin);
	freopen("a.out","w",stdout);
#endif
	n=read();
	m=read();
	for (int i=1;i<=n+1;i++){
		a[i]=read(); cnt[a[i]]++;
		if (a[i]==0) now=i;
	}
	for (int i=1;i<=m;i++) cnt[i]+=cnt[i-1];
	for (int i=m;i;i--) cnt[i]=cnt[i-1]; cnt[0]=0;
	for (int i=1;i<=n+1;i++) next[++cnt[a[i]]]=i;
	int i=1;
	for (now=next[now],i=1;i<=n;i++,now=next[now])
		printf("%d ",a[now]);
	puts("");
	return 0;
}

发现刚才头文件比代码要长好多不科学，然后就缩减了一下……当时这么简单的题目都没能做出来.......