NPSC補完計劃

登入註冊帳號.

請輸入帳號, 密碼以及預計登入時間
進階搜尋  

最新消息:

歡迎光臨NPSC補完計劃

+ NPSC補完計劃 » NPSC高中組 » NPSC2004高中組初賽
 NPSC 2004 高中組 初賽 A.迴文數目

作者 主題: NPSC 2004 高中組 初賽 A.迴文數目  (閱讀 2240 次)

sagit

  • 管理員
  • 白金會員
  • *****
  • 文章數: 217
    • 檢視個人資料
NPSC 2004 高中組 初賽 A.迴文數目
« 於: 十二月 08, 2009, 03:49:09 pm »

NPSC 2004 高中組 初賽 A.迴文數目

說明:迴文就是一個字串反轉後,會和原本的字串一樣,也就是左右對稱。現在給你幾個字串,請你計算每個字串的全排列中有多少個迴文。

解法:要知道一個字串的全排列有沒有迴文,要先計算每個字元出現的次數。如果所有字元出現的次數都是偶數,則我們把它們分兩半,一半放在字串的前面,另一半放在字串的後面,接下來計算前面這一半有多少種排序(重覆排列),而後面這一半則是和前面那一半相反,所以不用理它。

而如果出現次數有一個是奇數,則迴文的正中央那個字元一定就是那個寄數的字元,剩下的就同前面全部偶數的計算方式。但是如果有兩個字元以上的出現次數是奇數,則不可能有迴文出現。

參考程式:(By sagit)

代碼: [選擇]
// NPSC 2004 初賽 - 題目 A - 迴文數目 //
#include <iostream>
#include <fstream>
#include <cstdlib>
#define LEN 41
#define LEN2 21

using namespace std;

long long int N[LEN2];
// 記錄 N! 的值

// 計算 N! 的值
void Init()
{
    int i;
    N[0]=1;
    for (i=1; i<LEN2; i++)
        N[i]=N[i-1]*i;
}

// 計算字串 s 的迴文個數
long long int R(char s[])
{
    char c[LEN];
    int a[LEN], n, i, j, p;
    long long int l;
    // 計算各個字元出現的次數
    for (i=0, n=0; s[i]; i++)
    {
        for (j=0; j<n; j++)
            if (s[i]==c[j]) break;
        if (j<n) a[j]++;
        else
        {
            c[n]=s[i];
            a[n]=1;
            n++;
        }
    }
    l=N[i/2]; // i 為字串長度
    for (i=0, p=0; i<n; i++)
    {
        // 計算出現次數為奇數的個數
        if (a[i]%2)
        {
            p++;
            // 有兩個以上字元的出現個數為奇數, 則不可能有迴文
            if (p>1) return 0;
        }
        a[i]/=2;
        l/=N[a[i]];
    }
    return l;
}

int main()
{
    ifstream fin("pa.in");
    ofstream fout("pa.out");
    int n, i;
    char s[LEN];

    Init();
    fin >> n;
    for (i=0; i<n; i++)
    {
        fin >> s;
        fout << R(s) << endl;
    }

//    system("PAUSE");
    return 0;
}
記錄
+ NPSC補完計劃 » NPSC高中組 » NPSC2004高中組初賽
 NPSC 2004 高中組 初賽 A.迴文數目