传送门：http://www.lydsy.com/JudgeOnline/problem.php?id=4104
【题解】
脑洞+找规律做出来的。。
我用样例作为说明吧
样例给了我们这个
AAAC.A B
看起来没啥用
这是那个矩阵的最后一列对吧。
第一列是什么呢？我们都知道，按字典序排列。
.AAAAB C
由于这是一个环，所以第一个字母和最后一个字母是相邻的。换句话说，我们只要知道第一个字母和最后一个字母的对应关系，我们就能知道环长什么样了。
问题在于。有很多个重复的数，我们怎么知道对应的顺序呢？
如果我要比较A的顺序，我们不妨画个图
_ _ _ _ _ _ A_ _ _ _ _ _ A_ _ _ _ _ _ A_ _ _ _ _ _ C_ _ _ _ _ _ ._ _ _ _ _ _ A _ _ _ _ _ _ B
如果我把第一个A作为首位，和第二个A作为首位，哪个字典序大？
要明确的是，第一个A的前面6个位置组成的字符串一定小于第二个A前面6个位置组成的字符串。
所以把A提前，仍然是第一个A作为首位的字符串<第二个A作为首位的字符串。
我们就可以把A标号，然后进行对应了。
. _____A1A1_____A2A2_____A3A3_____CA4_____.B _____A4C _____B
这样就非常好了，然后我们从"."开始，把"______"看成边，沿着边走一遍就得到了这个环。
稍微看下就知道要从那个方向开始走了。
然后就解决了这道题了。
# include <stdio.h> # include <string.h> # include <iostream> # include <algorithm> // # include <bits/stdc++.h> using namespace std; typedef long long ll; typedef long double ld; typedef unsigned long long ull; const int M = 5e5 + 10; const int mod = 1e9+7; # define RG register # define ST static int n, m, v[M], nx[M], beg; struct pa { int x, pos; pa() {} pa(int x, int pos) : x(x), pos(pos) {} friend bool operator < (pa a, pa b) { return a.x < b.x || (a.x == b.x && a.pos < b.pos); } }p[M]; int main() { cin >> n >> m; for (int i=1; i<=n+1; ++i) { scanf("%d", &v[i]); p[i] = pa(v[i], i); if(v[i] == 0) beg = i; } sort(p+1, p+n+2); for (int i=1; i<=n+1; ++i) nx[i] = p[i].pos; int cur = beg; while(nx[cur] != beg) { cur = nx[cur]; printf("%d ", v[cur]); } return 0; } View Code
转载于:https://www.cnblogs.com/galaxies/p/bzoj4104.html
相关资源：JAVA上百实例源码以及开源项目