SSLOJ1460 逛機房

2022-09-23 01:52:13 字數 699 閱讀 2336

考慮到可以特判 \(n=10^6\),這樣每個數就只有 6 位。可以考慮 bfs。

但是每次詢問都 bfs 一次複雜度顯然不對。發現目標狀態是一樣的,且 \(10^6\) 以內的完全平方數只有 \(10^3\) 個,所以可以從目標狀態開始搜尋,然後 \(o(1)\) 詢問。

那麼每次有兩種轉移方式:

時間複雜度 \(o(n+q)\)。

#pragma gcc optimize("ofast")

#pragma gcc optimize("inline")

#include using namespace std;

const int n=1000010;

int q,n,dis[n];

bool vis[n];

struct node

;queueq;

int get(node x)

void bfs()

}if (len==1) continue;

for (int i=len;i<=6;i++)

bfs();

scanf("%d",&q);

while (q--)

return 0;

}