题意：
一串链码 用差分的最小表示法表示
思路：
其实就是最小表示法的模版题…
代码：
#include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; #define N 600010 #define inf 50000000 int n; int a[N]; int GetMin() { int i, j, k, len = n; for (i = 0, j = 1; i < len && j < len;) { for (k = 0; k < len && a[i + k] == a[j + k]; k++) ; if (k >= len) break; if (a[i + k] < a[j + k]) j += k + 1; else i += k + 1; if (i == j) j++; } return i; } char str[N]; int main() { while (~scanf("%s", str)) { n = strlen(str); for (int i = 0; i < n; i++) a[i] = str[i] - '0'; int t = a[0]; for (int i = 0; i < n - 1; i++) a[i] = (a[i + 1] - a[i] + 8) % 8; a[n - 1] = (t - a[n - 1] + 8) % 8; for (int i = 0; i < n; i++) a[i + n] = a[i]; int i = GetMin(); for (int j = 0; j < n; j++) printf("%d", a[i + j]); printf("\n"); } return 0; }