24h購物| | PChome| 登入
2012-03-29 21:50:49| 人氣928| 回應0 | 上一篇 | 下一篇

[ZJ][最小表示法][環同構判定][a442] Necklace Problem (NP)

推薦 0 收藏 0 轉貼0 訂閱站台

內容 ：

「題目總是唬人的，事實上並沒有那麼難」

給你兩個項鍊，這兩條項鍊上都有 n 顆珠子(用 0 ~ 9 表示之)，請判定這兩條項鍊是否相同。

記住項鍊可翻面。

 

 

後文：自從上了大學，就不來 ZJ 了 ... 因此題目如有雷同，請通知下架。

輸入說明 ：

有多筆測資，每組有兩個長度相同的字串來代表兩個項鍊。

0 < n < 10000

 

輸出說明 ：

相同請輸出 same, 不同請輸出 difference

範例輸入 ： 

4263
6234
4263
4362

範例輸出 ：

difference
same

提示 ：

頭跟尾要接起來，因為是項鍊。 用 gets 會有問題, scanf 則沒有問題 ...

出處 ：

Morris (管理：morris1028)




#include <stdio.h>
#include <string.h>
int MinExpSame(const char *A, const char *B, const int slen) {
    int i = 0, j = 0, k = 0;
    int x, y, tmp;
    while(i < slen && j < slen && k < slen) {
        x = i + k;
        y = j + k;
        if(x >= slen)    x -= slen;
        if(y >= slen)    y -= slen;
        if(A[x] == B[y]) {
            k++;
            if(k == slen) {
                return 1;
            }
        } else if(A[x] < B[y]) {
            i = i+k+1;
            k = 0;
        } else {
            j = j+k+1;
            k = 0;
        }
    }
    return 0;
}
int main() {
    char A[10001], B[10001], tmp;
    int i, j;
    while(scanf("%s %s", A, B) == 2) {
        if(MinExpSame(A, B, strlen(A)) == 0) {
            for(i = 0, j = strlen(A)-1; i < j; i++, j--)
                tmp = B[i], B[i] = B[j], B[j] = tmp;
            if(MinExpSame(A, B, strlen(A)) == 0)
                puts("difference");
            else
                puts("same");
        } else
            puts("same");
    }
    return 0;
}

我要檢舉
#最小表示法#環同構判定#a442#Necklace Problem (NP)
台長： Morris

您可能對以下文章有興趣

人氣(928) | 回應(0)| 推薦 (0)| 收藏 (0)| 轉寄
全站分類: 不分類 | 個人分類: 其他題目 |
此分類下一篇:[機率][問題] 檢驗策略？
此分類上一篇:[中興資工][程設][作業HW12]

我要回應
否 是 (若未登入"個人新聞台帳號"則看不到回覆唷!)
* 請輸入識別碼：
請輸入圖片中算式的結果(可能為0) 
(有*為必填)
TOP
詳全文