HDU 5442 Favorite Donut

你的名字 2022-08-05 10:27 213阅读 0赞

第一种方法,最小表示法
其实呢,你将每一个字母反转一下,将’a’变成’z’,就是最小表示法。
但是反转之后,我们如果用最小表示法,得到的是,在原串上位置最靠后的情况,与题意不服,所以我这里就强行将之往后硬判,最坏复杂度是当串所以的字符都相同的情况,退化成O(n2)。

  1. // whn6325689
  2. // Mr.Phoebe
  3. // http://blog.csdn.net/u013007900
  4. #include <algorithm>
  5. #include <iostream>
  6. #include <iomanip>
  7. #include <cstring>
  8. #include <climits>
  9. #include <complex>
  10. #include <fstream>
  11. #include <cassert>
  12. #include <cstdio>
  13. #include <bitset>
  14. #include <vector>
  15. #include <deque>
  16. #include <queue>
  17. #include <stack>
  18. #include <ctime>
  19. #include <set>
  20. #include <map>
  21. #include <cmath>
  22. #include <functional>
  23. #include <numeric>
  24. #pragma comment(linker, "/STACK:1024000000,1024000000")
  25. using namespace std;
  26. #define eps 1e-9
  27. #define PI acos(-1.0)
  28. #define INF 0x3f3f3f3f
  29. #define LLINF 1LL<<50
  30. #define speed std::ios::sync_with_stdio(false);
  31. typedef long long ll;
  32. typedef unsigned long long ull;
  33. typedef long double ld;
  34. typedef pair<ll, ll> pll;
  35. typedef complex<ld> point;
  36. typedef pair<int, int> pii;
  37. typedef pair<pii, int> piii;
  38. typedef vector<int> vi;
  39. #define CLR(x,y) memset(x,y,sizeof(x))
  40. #define CPY(x,y) memcpy(x,y,sizeof(x))
  41. #define clr(a,x,size) memset(a,x,sizeof(a[0])*(size))
  42. #define cpy(a,x,size) memcpy(a,x,sizeof(a[0])*(size))
  43. #define debug(a) cout << #a" = " << (a) << endl;
  44. #define debugarry(a, n) for (int i = 0; i < (n); i++) { cout << #a"[" << i << "] = " << (a)[i] << endl; }
  45. #define mp(x,y) make_pair(x,y)
  46. #define pb(x) push_back(x)
  47. #define lowbit(x) (x&(-x))
  48. #define MID(x,y) (x+((y-x)>>1))
  49. #define ls (idx<<1)
  50. #define rs (idx<<1|1)
  51. #define lson ls,l,mid
  52. #define rson rs,mid+1,r
  53. template<class T>
  54. inline bool read(T &n)
  55. {
  56. T x = 0, tmp = 1;
  57. char c = getchar();
  58. while((c < '0' || c > '9') && c != '-' && c != EOF) c = getchar();
  59. if(c == EOF) return false;
  60. if(c == '-') c = getchar(), tmp = -1;
  61. while(c >= '0' && c <= '9') x *= 10, x += (c - '0'),c = getchar();
  62. n = x*tmp;
  63. return true;
  64. }
  65. template <class T>
  66. inline void write(T n)
  67. {
  68. if(n < 0)
  69. {
  70. putchar('-');
  71. n = -n;
  72. }
  73. int len = 0,data[20];
  74. while(n)
  75. {
  76. data[len++] = n%10;
  77. n /= 10;
  78. }
  79. if(!len) data[len++] = 0;
  80. while(len--) putchar(data[len]+48);
  81. }
  82. //-----------------------------------
  83. const int MAXN=20010;
  84. char str[MAXN],rev[MAXN];
  85. int n,ch[30];
  86. int init()
  87. {
  88. int now='z';
  89. for(int i=0; i<26; i++)
  90. ch[i]=now--;
  91. }
  92. int getsmall(string s, bool flag)
  93. {
  94. int i,j,k,l;
  95. int N=s.length();
  96. s+=s;
  97. int ans=0;
  98. for(i=0,j=1; j<N;)
  99. {
  100. for(k=0; k<N&&s[i+k]==s[j+k]; k++);
  101. if(k>=N)
  102. {
  103. if(flag)
  104. {
  105. ans=j;
  106. j++;
  107. continue;
  108. }
  109. break;
  110. }
  111. if(s[i+k]<s[j+k])
  112. {
  113. j+=k+1;
  114. }
  115. else
  116. {
  117. l=i+k;
  118. i=j;
  119. ans=i;
  120. j=max(l,j)+1;
  121. }
  122. }
  123. return ans;
  124. }
  125. bool compare(int ans0,int ans1)
  126. {
  127. int pos1=ans0,pos2=ans1;
  128. for(int i=0; i<n; i++)
  129. {
  130. if(str[pos1]==str[pos2])
  131. {
  132. if(++pos1>=n) pos1-=n;
  133. if(--pos2<0) pos2+=n;
  134. }
  135. else
  136. {
  137. return str[pos1]>str[pos2];
  138. }
  139. }
  140. return ans0<=ans1;
  141. }
  142. string st,en;
  143. int main()
  144. {
  145. // freopen("data.txt", "r", stdin);
  146. init();
  147. int T;
  148. read(T);
  149. while(T--)
  150. {
  151. st.clear();
  152. en.clear();
  153. read(n);
  154. scanf("%s",str);
  155. for(int i=0; i<n; i++)
  156. st+=ch[str[i]-'a'];
  157. en=st;
  158. reverse(en.begin(),en.end());
  159. int ans0=getsmall(st,false);
  160. int tmp=getsmall(en,true);
  161. int ans1=(n-tmp-1)%n;
  162. if (compare(ans0,ans1))
  163. printf("%d 0\n",ans0+1);
  164. else
  165. printf("%d 1\n",ans1+1);
  166. }
  167. return 0;
  168. }

后缀数组法,裸的后缀数组应用

  1. // xixihaha
  2. #include <algorithm>
  3. #include <iostream>
  4. #include <iomanip>
  5. #include <cstring>
  6. #include <climits>
  7. #include <complex>
  8. #include <fstream>
  9. #include <cassert>
  10. #include <cstdio>
  11. #include <bitset>
  12. #include <vector>
  13. #include <deque>
  14. #include <queue>
  15. #include <stack>
  16. #include <ctime>
  17. #include <set>
  18. #include <map>
  19. #include <cmath>
  20. #include <functional>
  21. #include <numeric>
  22. #pragma comment(linker, "/STACK:1024000000,1024000000")
  23. using namespace std;
  24. #define eps 1e-9
  25. #define PI acos(-1.0)
  26. #define INF 0x3f3f3f3f
  27. #define LLINF 1LL<<62
  28. #define speed std::ios::sync_with_stdio(false);
  29. typedef long long ll;
  30. typedef unsigned long long ull;
  31. typedef long double ld;
  32. typedef pair<ll, ll> pll;
  33. typedef complex<ld> point;
  34. typedef pair<int, int> pii;
  35. typedef pair<pii, int> piii;
  36. typedef vector<int> vi;
  37. #define CLR(x,y) memset(x,y,sizeof(x))
  38. #define CPY(x,y) memcpy(x,y,sizeof(x))
  39. #define clr(a,x,size) memset(a,x,sizeof(a[0])*(size))
  40. #define cpy(a,x,size) memcpy(a,x,sizeof(a[0])*(size))
  41. #define debug(a) cout << #a" = " << (a) << endl;
  42. #define debugarry(a, n) for (int i = 0; i < (n); i++) { cout << #a"[" << i << "] = " << (a)[i] << endl; }
  43. #define pb(x) push_back(x)
  44. #define lowbit(x) (x&(-x))
  45. #define MID(x,y) (x+((y-x)>>1))
  46. #define ls (idx<<1)
  47. #define rs (idx<<1|1)
  48. #define lson ls,l,mid
  49. #define rson rs,mid+1,r
  50. template<class T>
  51. inline bool read(T &n)
  52. {
  53. T x = 0, tmp = 1;
  54. char c = getchar();
  55. while((c < '0' || c > '9') && c != '-' && c != EOF) c = getchar();
  56. if(c == EOF) return false;
  57. if(c == '-') c = getchar(), tmp = -1;
  58. while(c >= '0' && c <= '9') x *= 10, x += (c - '0'),c = getchar();
  59. n = x*tmp;
  60. return true;
  61. }
  62. template <class T>
  63. inline void write(T n)
  64. {
  65. if(n < 0)
  66. {
  67. putchar('-');
  68. n = -n;
  69. }
  70. int len = 0,data[20];
  71. while(n)
  72. {
  73. data[len++] = n%10;
  74. n /= 10;
  75. }
  76. if(!len) data[len++] = 0;
  77. while(len--) putchar(data[len]+48);
  78. }
  79. //-----------------------------------
  80. const int MAXN=100010;
  81. char C[MAXN],rC[MAXN];
  82. int idx[MAXN],mp[MAXN];
  83. int rk[MAXN],sa[MAXN],height[MAXN],w[MAXN],wa[MAXN],ret[MAXN];
  84. void getSa (int len,int up)
  85. {
  86. int *k = rk;
  87. int *id = height;
  88. int *r = ret;
  89. int *cnt = wa;
  90. for(int i=0;i<up;i++) cnt[i] = 0;
  91. for(int i=0;i<len;i++) cnt[k[i] = w[i]]++;
  92. for(int i=0;i<up;i++) cnt[i+1] += cnt[i];
  93. for(int i = len - 1; i >= 0; i--) {
  94. sa[--cnt[k[i]]] = i;
  95. }
  96. for(int d = 1,p = 0; p < len;){
  97. for(int i = len - d; i < len; i++) id[p++] = i;
  98. for(int i=0;i<len;i++)if(sa[i] >= d) id[p++] = sa[i] - d;
  99. for(int i=0;i<len;i++) r[i] = k[id[i]];
  100. for(int i=0;i<up;i++) cnt[i] = 0;
  101. for(int i=0;i<len;i++) cnt[r[i]]++;
  102. for(int i=0;i<up;i++) cnt[i+1] += cnt[i];
  103. for(int i = len - 1; i >= 0; i--) {
  104. sa[--cnt[r[i]]] = id[i];
  105. }
  106. swap(k,r);
  107. p = 0;
  108. k[sa[0]] = p++;
  109. for(int i=0;i<len-1;i++) {
  110. if(sa[i]+d < len && sa[i+1]+d <len &&r[sa[i]] == r[sa[i+1]]&& r[sa[i]+d] == r[sa[i+1]+d])
  111. k[sa[i+1]] = p - 1;
  112. else k[sa[i+1]] = p++;
  113. }
  114. if(p >= len) return ;
  115. d *= 2,up = p, p = 0;
  116. }
  117. }
  118. void getHeight(int len) {
  119. for(int i=0;i<len;i++) rk[sa[i]] = i;
  120. height[0] = 0;
  121. for(int i = 0,p = 0; i < len - 1; i++) {
  122. int j = sa[rk[i]-1];
  123. while(i+p < len&& j+p < len&& w[i+p] == w[j+p]) {
  124. p++;
  125. }
  126. height[rk[i]] = p;
  127. p = max(0,p - 1);
  128. }
  129. }
  130. int getSuffix(char s[]) {
  131. int len = strlen(s),up = 0;
  132. for(int i = 0; i < len; i++) {
  133. w[i] = s[i];
  134. up = max(up,w[i]);
  135. }
  136. w[len++] = 0;
  137. getSa(len,up+1);
  138. getHeight(len);
  139. return len;
  140. }
  141. int solve(char s[],int n)
  142. {
  143. int len=getSuffix(s);
  144. /* for(int i=1;i<len;i++){ printf("%s\n",s+sa[i]); }*/
  145. int start=len-1;
  146. while(sa[start]>n/2)start--;
  147. int ans=idx[sa[start]];
  148. while(height[start]>=n/2){
  149. start--;
  150. ans=min(ans,idx[sa[start]]);
  151. }
  152. return ans;
  153. }
  154. int cmp(int x,int y,int n)
  155. {
  156. for(int i=x,j=y,k=0;k<n;k++,i++,j++){
  157. if(C[i]==rC[j])continue;
  158. if(C[i]<rC[j])return -1;
  159. if(C[i]>rC[j])return 1;
  160. }
  161. return 0;
  162. }
  163. int main()
  164. {
  165. // freopen("in","r",stdin);
  166. int T;scanf("%d",&T);
  167. while(T--){
  168. int n;
  169. scanf("%d",&n);
  170. scanf("%s",C);
  171. for(int i=0;i<n;i++)rC[i]=C[i];
  172. reverse(rC,rC+n);
  173. for(int i=0;i<n;i++){
  174. C[i+n]=C[i];
  175. idx[i]=idx[i+n]=i;
  176. }
  177. C[n*2]='\0';
  178. int ans=solve(C,n*2),dir=0;
  179. for(int i=0;i<n;i++){
  180. rC[i+n]=rC[i];
  181. idx[i]=idx[n+i]=n-i-1;
  182. mp[n-i-1]=i;
  183. }
  184. rC[n*2]='\0';
  185. // cout<<rC<<endl;
  186. int res=solve(rC,n*2);
  187. // cout<<ans<<"!!"<<res<<endl;
  188. // cout<<string(C+ans,n)<<endl;
  189. // cout<<string(rC+mp[res],n)<<endl;
  190. int flag=cmp(ans,mp[res],n);
  191. if(flag==-1){
  192. ans=res,dir=1;
  193. }
  194. else if(flag==0){
  195. if(res<ans){
  196. ans=res;
  197. dir=1;
  198. }
  199. }
  200. printf("%d %d\n",ans+1,dir);
  201. }
  202. return 0;
  203. }

发表评论

表情:
评论列表 (有 0 条评论,213人围观)

还没有评论,来说两句吧...

相关阅读

    相关 HDU 5442 Favorite Donut

    第一种方法,最小表示法 其实呢,你将每一个字母反转一下,将’a’变成’z’,就是最小表示法。 但是反转之后,我们如果用最小表示法,得到的是,在原串上位置最靠后的情况,与

    相关 my favorite --------- 引用

    引用 引用是我们C++中新引入的一种机制,那么到底什么是引用呢? 引用概念:引用不是新定义一个变量,而是给已存变量取了一个别名,编译器不会为引用变量开辟内存空间,