本文主要是介绍HDU 4162 Shape Number，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
大意：原串通过相邻的数字相减得到的差或8减该差得到一个新串，然后输出新串（看成环）
如果仅仅只是求最小的字母序的排列，那么就可以直接用字符串的最小表示法直接解决，可以得到最小排列的第一个字符在该字符串的那个位置。
但是题目要求了，必须要规范normalize。 所以要求一阶差分链码，求了一阶差分链码之后，然后对这链码用最小表示法直接求解。
循环字符串的最小表示法的问题可以这样描述：
对于一个字符串S，求S的循环的同构字符串S’中字典序最小的一个。
就是对于一个字符串s，设两个变量i, j, 分别指向该字符串的第一个和第二个，即i=0,j=1,然后一起往后比对，假设往后已经比对了k个字符，
如果s[i+k] == s[j+k] 那么k++，往后继续比对
如果s[i+k] > s[j+k],那么 我们就要移动i的位置，使得i = i+k+1
如果s[i+k] < s[j+k] ，那么我们就要移动j的位置， 使得 j = j+k+1
如果i == j就让 j++
同时如果s[i+k] != s[j+k] 那么 k就要置0
最后返回 i<j?i:j 即可
始终保持i<j，因为如果i == j的话事实上就在比较同一个串。。。。没意义，而最后返回的就是i == j时
的指针，而这个指针极小可能是想要的结果。。。。。最后为什么返回小的那个呢？因为到达该位置就不在动了。。
而另外一个指针已经后移到出界了（即该指针 == l）
这里还有个问题，就是一阶差分链码，一阶差分链码必须是 s[i] = s[i+1] - s[i]， 但是这样s[i]就可能不在[0,7]的范围呢，于是因为循环的原因要这样写
s[i] = (s[i+1] -s[i] + 8)%8;
中字典序最小的
// whn6325689
// Mr.Phoebe
// http://blog.csdn.net/u013007900
#include <algorithm>
#include <iostream>
#include <iomanip>
#include <cstring>
#include <climits>
#include <complex>
#include <fstream>
#include <cassert>
#include <cstdio>
#include <bitset>
#include <vector>
#include <deque>
#include <queue>
#include <stack>
#include <ctime>
#include <set>
#include <map>
#include <cmath>
#include <functional>
#include <numeric>
#pragma comment(linker, "/STACK:1024000000,1024000000")using namespace std;typedef long long ll;
typedef long double ld;
typedef pair<ll, ll> pll;
typedef complex<ld> point;
typedef pair<int, int> pii;
typedef pair<pii, int> piii;
typedef vector<int> vi;#define CLR(x,y) memset(x,y,sizeof(x))
#define mp(x,y) make_pair(x,y)
#define pb(x) push_back(x)
#define lowbit(x) (x&(-x))
#define MID(x,y) (x+((y-x)>>1))
#define eps 1e-9
#define PI acos(-1.0)
#define INF 0x3f3f3f3f
#define LLINF 1LL<<62template<class T>
inline bool read(T &n)
{T x = 0, tmp = 1; char c = getchar();while((c < '0' || c > '9') && c != '-' && c != EOF) c = getchar();if(c == EOF) return false;if(c == '-') c = getchar(), tmp = -1;while(c >= '0' && c <= '9') x *= 10, x += (c - '0'),c = getchar();n = x*tmp;return true;
}
template <class T>
inline void write(T n)
{if(n < 0){putchar('-');n = -n;}int len = 0,data[20];while(n){data[len++] = n%10;n /= 10;}if(!len) data[len++] = 0;while(len--) putchar(data[len]+48);
}
//-----------------------------------char c[333333], c1[333333];//最小表示法
int Minp(char *c, int l)
{int i = 0, j = 1, k = 0, t;while (i < l && j < l && k < l){t = c[(i+k)%l] - c[(j+k)%l];if (t == 0)k++;else{if (t > 0)//以i开头的串较大，所以i移动，j不变（因为求最小串的下标）i += k + 1;else//i处小j += k + 1;if (i == j)j++;k = 0;///}}return i < j ? i : j;
}int main()
{int n;int i, j;int l, k;while (~scanf("%s", c)){l = strlen(c);for (i = 0; i < l; i++)c1[i] = (c[(i+1)%l] >= c[i] ? c[(i+1)%l] - c[i] + '0' : 8 - (c[i] - c[(i+1)%l]) + '0');//puts(c1);k = Minp(c1, l);//cout << k << endl;for (i = 0, j = k; i < l; i++, j = (j+1)%l) printf("%c", c1[j]);puts("");}return 0;
}
这篇关于HDU 4162 Shape Number的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
