這是前天成都網(wǎng)賽的題，比賽時(shí)候確實(shí)一點(diǎn)思路也沒有。比完之后看了人家的解題報(bào)告，還是不會(huì)怎么搜出答案，太弱了。
題意是給出N,K，求M，使得M是N的正倍數(shù)，而且M用K進(jìn)制表示后所需要的不同數(shù)字(0,1,2,3,...,k-1)最少，如果有多組
這樣的情況，求出最小的M。
很數(shù)學(xué)的題意。用到了一個(gè)結(jié)論，就是任意數(shù)字的正倍數(shù)均可以用不超過2個(gè)不同數(shù)字的數(shù)得到。
證明如下：
任意數(shù)M % N 總共有N種結(jié)果，假如有N+1個(gè)不同的M，那么肯定有2個(gè)M對(duì)N取模后的結(jié)果是相同，這個(gè)是所謂鴿巢原理。
那么，我取a,aa,aaa,...,aaaaaaaaaa....，總共N+1個(gè)，同樣滿足上面的結(jié)論。那么我取那2個(gè)對(duì)N取模相同的數(shù)字相減得到
數(shù)字aaaaa...000....，這個(gè)數(shù)字肯定是N的倍數(shù)。
綜合上面的證明，只能得到2個(gè)數(shù)字肯定能表示N的倍數(shù)。但是不能說形式就是aaaaa...000....。
到了這里我還是一點(diǎn)思路都沒有，一點(diǎn)都不知道怎么搜索。。。
想了1個(gè)多小時(shí)，無頭緒，問過了這題的同學(xué)，還是無頭緒。看解題報(bào)告，他們的代碼寫得太牛了，完全看不懂，無頭緒。
也許也是我對(duì)bfs理解太淺，才看不懂他們的搜索代碼。而且，我連可以搜索的地方都沒有找到，都不知道搜什么了。
想了好久，昨天吃飯的時(shí)候，終于發(fā)現(xiàn)可以對(duì)余數(shù)進(jìn)行搜索。
對(duì)于任意的N，其余數(shù)就是范圍是[0, N -1]。這個(gè)其實(shí)就可以代表狀態(tài)了，或者代表bfs中的點(diǎn)了。從當(dāng)前余數(shù)轉(zhuǎn)移到其它
余數(shù)的是MOD * K + A 或者 MOD * K + B，如果要轉(zhuǎn)移到得余數(shù)以前沒被搜過，那就可以轉(zhuǎn)移過去。這個(gè)剛好就是一個(gè)
優(yōu)化了。也可以看成是子問題了。但是，dfs完全不行。剛開始用dfs，絕對(duì)的超時(shí)。
用dfs也是我對(duì)思路理解不深，僥幸認(rèn)為能過。。。后面發(fā)現(xiàn)，這題完全和bfs吻合。[0, N -1]剛好代表N個(gè)點(diǎn)，我要通過
從外面的一個(gè)點(diǎn)，最短的遍歷到點(diǎn)0，可以bfs或者最短路算法。這題我覺得還有個(gè)難點(diǎn)就是保存答案，因?yàn)榇鸢缸铋L(zhǎng)的長(zhǎng)度
可能是N(N<=10000)，所以把答案直接放到節(jié)點(diǎn)里面肯定不行的。但是，我還仔細(xì)看過算法導(dǎo)論。因此想到了可以利用bfs
搜索出來的那顆樹或者最短路算法跑出來的那顆樹，從目標(biāo)節(jié)點(diǎn)逆序?qū)ふ掖鸢福业匠霭l(fā)節(jié)點(diǎn)之后，再把答案reverse一下就行了。
這題還得注意0不能是N的倍數(shù)，所以注意bfs(0,i)這種情況的處理。
代碼如下：
#include <stdio.h>
#include <
string.h>
#include <queue>
#include <algorithm>
using namespace std;
const int MAX_N = 10010;
int nOut[MAX_N];
int nOLen;
int nAns[MAX_N];
int nALen;
bool bMod[MAX_N];
int nFather[MAX_N];
int nChoose[MAX_N];
int nN;
int nK;
bool bFind;
int Cmp(
int* A,
int nLA,
int* B,
int nLB)
{
if (nLA != nLB)
{
return nLA - nLB;
}
for (
int i = 0; i < nLA; ++i)
{
if (A[i] != B[i])
{
return A[i] - B[i];
}
}
return 0;
}
void Bfs(
int nA,
int nB)
{
memset(bMod,
false,
sizeof(bMod));
queue<
int> que;
que.push(0);
int nTemp;
bool bFirst =
true;
bFind =
false;
if (nA > nB)swap(nA, nB);
//printf("nA:%d, nB:%d\n", nA, nB);
while (!que.empty())
{
//printf("nMod:%d\n", que.front());
int nMod = que.front();
que.pop();
if (nMod == 0)
{
if (bFirst)bFirst =
false;
else {
bFind =
true;
break;
}
}
nTemp = (nMod * nK + nA) % nN;
if (!(nMod == 0 && nA == 0) && !bMod[nTemp])
{
nFather[nTemp] = nMod;
nChoose[nTemp] = nA;
que.push(nTemp);
bMod[nTemp] =
true;
//printf("nTemp:%d\n", nTemp);
}
if (nA == nB)
continue;
nTemp = (nMod * nK + nB) % nN;
if (!bMod[nTemp])
{
nFather[nTemp] = nMod;
nChoose[nTemp] = nB;
que.push(nTemp);
bMod[nTemp] =
true;
//printf("nTemp:%d\n", nTemp);
}
}
if (bFind)
{
int nF = 0;
nALen = 0;
do {
nAns[nALen++] = nChoose[nF];
nF = nFather[nF];
}
while (nF);
reverse(nAns, nAns + nALen);
}
}
int main()
{
while (scanf("%d%d", &nN, &nK) == 2)
{
bool bOk =
false;
nOLen = 0;
for (
int i = 1; i < nK; ++i)
{
Bfs(i, i);
if (bFind)
{
if (nOLen == 0 || Cmp(nOut, nOLen, nAns, nALen) > 0)
{
nOLen = nALen;
memcpy(nOut, nAns,
sizeof(
int) * nALen);
}
bOk =
true;
}
}
if (!bOk)
for (
int i = 0; i < nK; ++i)
{
for (
int j = i + 1; j < nK; ++j)
{
Bfs(i, j);
if (bFind)
{
if (nOLen == 0 || Cmp(nOut, nOLen, nAns, nALen) > 0)
{
nOLen = nALen;
memcpy(nOut, nAns,
sizeof(
int) * nALen);
}
}
}
}
for (
int k = 0; k < nOLen; ++k)
{
printf("%d", nOut[k]);
}
printf("\n");
}
return 0;
}