2011-06-10 20:39:45Morris
d643. 勞動的符咒
http://zerojudge.tw/ShowProblem?problemid=d643
內容 ：
繼上次你解決了梅蘭城符咒室的災難之後，
現在法師們又有新的問題了。
「想新符咒真是麻煩~__~」
於是法師們想出一個絕妙的辦法來產生新符咒
叫做「勞動的符咒」
假設有一長度為8的符咒bcadefpa，
取數字2表示兩個字一組分成bc,ad,ef,pa
然後將這四組字按照ASCII的順序排列成為adbcefpa
這樣就可以製造出新符咒了
雖然省去了想新符咒的麻煩，
但是作這樣的分解排列卻讓法師們陷入另外一場混亂中，
你可以寫個程式幫幫他們嗎？
現在法師們又有新的問題了。
「想新符咒真是麻煩~__~」
於是法師們想出一個絕妙的辦法來產生新符咒
叫做「勞動的符咒」
假設有一長度為8的符咒bcadefpa，
取數字2表示兩個字一組分成bc,ad,ef,pa
然後將這四組字按照ASCII的順序排列成為adbcefpa
這樣就可以製造出新符咒了
雖然省去了想新符咒的麻煩，
但是作這樣的分解排列卻讓法師們陷入另外一場混亂中，
你可以寫個程式幫幫他們嗎？
輸入說明
：
每個測資點的測資僅一列。即原符咒內容。
(字元長度不超過100000個字元，僅包含小寫英文字母)
假設符咒長度是12個字元，
那麼你必須由小到大列出1、2、3、4、6個字元一組的所有符咒
(也就是12的因數。當然了不必列12，因為和原符咒一樣)
萬一發生分解排列後符咒與原本相同的話，
那麼就不用輸出該符咒。
(字元長度不超過100000個字元，僅包含小寫英文字母)
假設符咒長度是12個字元，
那麼你必須由小到大列出1、2、3、4、6個字元一組的所有符咒
(也就是12的因數。當然了不必列12，因為和原符咒一樣)
萬一發生分解排列後符咒與原本相同的話，
那麼就不用輸出該符咒。
輸出說明
：
輸出數種不同類型的符咒。一條符咒一列。
萬一無法產生新的符咒，
請輸出bomb!
萬一無法產生新的符咒，
請輸出bomb!
範例輸入 ：
efpabcad
範例輸出 ：
aabcdefp adbcefpa bcadefpa
提示
：
共計三個測資點，配分30％、35％、35％
另外這題因為第三個測資點很大...ZJ上傳時會自動把換行吃掉
基本上用C/C++語言(忽略換行)比較不會有問題
出處
：
jack1
(管理：jack1)
作法 : 字串排序
因為是用C語言寫，所以沒有像C++ 那麼方便，但是又怕退化
所以我用SA(suffix array)去做字串排序，把rank[] 用 O(LlogL)建出
直接排序的效率是O(L) 百分百不退化
但是要比對重複這塊，我就寫差了，還是O(L)
作法 : 字串排序
因為是用C語言寫，所以沒有像C++ 那麼方便，但是又怕退化
所以我用SA(suffix array)去做字串排序，把rank[] 用 O(LlogL)建出
直接排序的效率是O(L) 百分百不退化
但是要比對重複這塊，我就寫差了，還是O(L)
/**********************************************************************************/
/* Problem: d643 "勞動的符咒" from jack1 */
/* Language: C */
/* Result: AC (36ms, 1098KB) on ZeroJudge */
/* Author: morris1028 at 2011-06-05 22:39:11 */
/**********************************************************************************/
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define MaxL 100002
void Merge(int, int, int);
void MergeSort(int, int);
struct xy_change_rank{
int index, v;
}Data[MaxL], X[MaxL];
char S[MaxL], Ss[MaxL], base_rank[256];
int s2[25]={1}, rank[MaxL], SA[MaxL], L;
void MergeSort(int l, int h) {
if(l < h) {
int m=(l+h)/2;
MergeSort(l ,m);
MergeSort(m+1,h);
Merge(l,m,h);
}
}
void Merge(int l, int m, int h) {
int In1 = l, In2 = m+1;
int a, b, Top = 0;
while(In1 <= m && In2 <= h)
if(Data[In1].v <= Data[In2].v)
X[Top++] = Data[In1++];
else X[Top++] = Data[In2++];
while(In1 <= m) X[Top++] = Data[In1++];
while(In2 <= h) X[Top++] = Data[In2++];
for(a = 0, b = l; a < Top; a++, b++)
Data[b] = X[a];
}
void Doubling_Algorithm() {
int a, b, C, temp;
L=strlen(S);
int Queue[MaxL] = {-1};
char Mask[MaxL];
for(a = 0; a < L; a++)
rank[a] = base_rank[S[a]], Mask[a] = 0,
Data[a].v = rank[a], Data[a].index = a;
MergeSort(0, L-1);
for(a = 0; s2[a] < L; a++) {
temp = Data[0].v, C = 1;
for(b = 0; b < L; b++) {
if(Data[b].v != temp || Mask[b] == 1)
Queue[C] = b-1, temp = Data[b].v, C++, Mask[b] = 1;
rank[Data[b].index] = C;
}
Queue[C] = L-1, C++;
for(b = 0; b < L; b++) {
if(Data[b].index + s2[a]<L) Data[b].v = rank[Data[b].index + s2[a]];
else Data[b].v = 0;
}
for(b = 1; b < C; b++)
MergeSort(Queue[b-1]+1, Queue[b]);
}
for(a = 0; a < L; a++)
SA[a] = Data[a].index;
}
main() {
int a, b, c, d, N, D, q;
for(a = 1; a < 25; a++) s2[a] = s2[a-1]*2;
for(a = 'a'; a <= 'z'; a++) base_rank[a] = a-'a'+1;
while(scanf("%s", &S) == 1) {
Doubling_Algorithm();
int l = strlen(S), flag = 1;
char Ans[100001];
for(a = 1; a <= l; a++)
if(l%a == 0) {
q = 0;
for(b = 0; b < l; b++)
if(SA[b]%a == 0) {
for(c = SA[b], d = 0; d < a; c++, d++)
Ans[q++] = S[c];
}
Ans[l] = '\0';
for(b = 0; b < l; b++)
if(Ans[b] != S[b]) break;
if(b != l) puts(Ans), flag = 0;
}
if(flag) puts("bomb!");
}
return 0;
}
下一篇：d644. 壞脾氣小小皮