题目链接:
题意:
求给定字符的一阶差分链的最小表示。
题解:
先求一阶差分链,再求一阶差分链的最小表示法。
代码:
跑了670MS
#include #include #include using namespace std;const int maxn = 3e5 + 10;char s1[maxn],s2[maxn];int solve(char *s) { int i = 0, j = 1, k = 0,len=strlen(s); while (i < len&&j < len&&k 0) i = i + k + 1; else j = j + k + 1; if (i == j) j++; k = 0; } } return i < j ? i : j;}int main() { while (scanf("%s", s1) == 1) { int len = strlen(s1); for (int i = 0; i < len; i++) { s2[i] = (s1[(i + 1) % len] - s1[i] + 8) % 8 + '0'; } s2[len] = '\0'; //cout << s2 << endl; int pos = solve(s2); for (int i = 0; i < len; i++) { printf("%c", s2[(pos + i) % len]); } printf("\n"); } return 0;}
贴个后缀数组的解法:
跑了2527MS
#include
VI;typedef pair
PII;typedef vector > VPII;const int INF=0x3f3f3f3f;const LL INFL=0x3f3f3f3f3f3f3f3fLL;const double eps=1e-8;const int maxn = 3e5 + 10;char s1[maxn],s2[maxn];struct SuffixArray{ char s[maxn]; int sa[maxn],t[maxn],t2[maxn],c[maxn]; int n,m; void init(int n,int m){ this->n=n; this->m=m; } void build_sa(){ int i,*x=t,*y=t2; for(i=0;i =0;i--) sa[--c[x[i]]]=i; for(int k=1;k<=n;k<<=1){ int p=0;// for(i=n-k;i =k) y[p++]=sa[i]-k; for(i=0;i =0;i--) sa[--c[x[y[i]]]]=y[i]; swap(x,y); p=1; x[sa[0]]=0; for(i=1;i =n) break; m=p; } }}mysa;int main() { while (scanf("%s", s1) == 1) { int len = strlen(s1); mysa.init(len,256); for (int i = 0; i < len; i++) { s2[i] = (s1[(i + 1) % len] - s1[i] + 8) % 8 + '0'; } s2[len] = '\0'; strcpy(mysa.s,s2); mysa.build_sa(); for(int p=mysa.sa[0];p