內容
小新習慣將提款卡的密碼寫在卡片上，因為怕被盜領，小新做了如下的動作：
- 密碼數字是一個完全平方數。
- 將此數字重新排列後才寫在卡片上。
由於提款機輸入密碼時有次數的限制，請您先將可能的密碼列出。
輸入
數字每行是一個 4 ~ 10 位數的數字。
數字內不含 0
1269
3133
輸出
請將輸入的數字重新排列後，依序輸出符合條件的密碼。
如果找不到密碼請輸出 0
1296 2916 9216
0
解題思路
因為題目表明沒有 0 且位數是再 4~10 位數，所以在建表的時候，只需要建 36~99999 的平方項，且如果該項為 0 可直接跳過不紀錄。
而這題原本想建好表之後用 DFS 配合 BinarySearch 查表來解，無奈 10! 的可能性過多，最後 3 筆測資 TLE，所以改用 HashTable 來做。
根據題意只要是由 1,2,6,9 四個字組合而成的數，都要輸出 { 1296、2916、9216 } 三個，所以將它們視為一組答案，而既然他們是一組答案又要使用 HashTable 來做，1296、2916、9216 就應該共用一個 HashKey，所以在製成 HashKey 時，用基數排序紀錄每個數有幾個，再將它們打成 HashKey，如此一來不管原本是多少，只要構成的字元一樣，得到的 HashKey 就會是一樣的。
將表建好之後只要每次將輸入的字串打成 HashKey 查表，若有查到相同的答案則輸出，若否則代表這組數字組合無法組合成完全平方數，輸出 0。
完整程式碼
AC (33ms, 7.3MB)
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef struct Hash
{
unsigned int Key, vLen;
char Values[40][11];
struct Hash* Next;
}Hash;
Hash* pList[32768];
Hash** now;
long long tmp;
unsigned int key, pLen;
char value[11];
inline unsigned int APHash(char src[])
{
unsigned int hash = 0;
char str[10] = { 0 };
for (int i = 0; src[i]; i++)
str[src[i] - '0']++;
for (int i = 9; i; i--)
{
if (i & 1)
hash ^= (~((hash << 11) ^ (str[i]) ^ (hash >> 5)));
else
hash ^= ((hash << 7) ^ (str[i]) ^ (hash >> 3));
}
return (hash & 0x7FFFFFFF);
}
inline void addHash(long long square)
{
sprintf(value, "%lld", square);
key = APHash(value);
now = &pList[key & 32767];
while (*now)
{
if ((*now)->Key == key)
{
strcpy((*now)->Values[(*now)->vLen++], value);
return;
}
now = &(*now)->Next;
}
(*now) = malloc(sizeof(Hash));
(*now)->Key = key;
(*now)->vLen = 1;
strcpy((*now)->Values[0], value);
(*now)->Next = NULL;
}
inline void getAns(char src[])
{
key = APHash(src);
now = &pList[key & 32767];
while (*now)
{
if ((*now)->Key == key)
{
for (int i = 0; i < (*now)->vLen; i++)
printf("%s ", (*now)->Values[i]);
putchar('\n');
return;
}
now = &(*now)->Next;
}
puts("0");
}
int main()
{
for (long long i = 34; i < 100000; i++)
{
tmp = i * i;
while (tmp % 10)
tmp /= 10;
if (!tmp)
addHash(i * i);
}
while (scanf(" %s", value) == 1)
{
getAns(value);
}
return 0;
}
|
