內容
繼上次你解決了梅蘭城符咒室的災難之後，
現在法師們又有新的問題了。
「想新符咒真是麻煩__」
於是法師們想出一個絕妙的辦法來產生新符咒
叫做「勞動的符咒」
假設有一長度為 8 的符咒 bcadefpa，
取數字 2 表示兩個字一組分成 bc,ad,ef,pa
然後將這四組字按照 ASCII 的順序排列成為 adbcefpa
這樣就可以製造出新符咒了
雖然省去了想新符咒的麻煩，
但是作這樣的分解排列卻讓法師們陷入另外一場混亂中，
你可以寫個程式幫幫他們嗎？
輸入
每個測資點的測資僅一列。即原符咒內容。
(字元長度不超過 100000 個字元，僅包含小寫英文字母)
假設符咒長度是 12 個字元，
那麼你必須由小到大列出 1、2、3、4、6 個字元一組的所有符咒
(也就是 12 的因數。當然了不必列 12，因為和原符咒一樣)
萬一發生分解排列後符咒與原本相同的話，
那麼就不用輸出該符咒。
efpabcad
輸出
輸出數種不同類型的符咒。一條符咒一列。
萬一無法產生新的符咒，
請輸出 bomb!
aabcdefp
adbcefpa
bcadefpa
解題思路
簡單的排序，用一個指標陣列去映射對應的位置來排序減少記憶體操作次數，輸出時先存到陣列裡再一併輸出減少調用 putchar()函式的時間。
完整程式碼
AC (60ms, 1.2MB)
#include <stdio.h>
#include <stdlib.h>
#define MAX 100010
int len, len2;
char input[MAX], * sort[MAX], output[MAX], * oTop;
int cmpsrc(int strLen)
{
int k = 0;
for (int i = 0; i < len2; i++)
{
for (int j = 0; j < strLen; j++)
{
if (sort[i][j] != input[k++])
return 1;
}
}
return 0;
}
int cmp(const char** lhs, const char** rhs)
{
return strcmp(*lhs, *rhs);
}
int main()
{
gets(input);
for (len = 0; input[len]; len++)
;
for (int i = 1; i < len; i++)
{
if (!(len % i))
{
len2 = len / i;
for (int j = 0; j < len2; j++)
sort[j] = &input[j * i];
qsort(sort, len2, sizeof(char**), cmp);
if (cmpsrc(i))
{
oTop = output;
for (int j = 0; j < len2; j++)
{
for (int k = 0; k < i; k++)
* oTop++ = sort[j][k];
}
*oTop = '\0';
puts(output);
}
}
}
if (!oTop) puts("bomb!");
return 0;
}
|
