网站底部导航栏,郑州制作网站推荐,建湖人才网官网登录,07年以前东莞有多乱题目
思路#xff1a;因为有走的过程不能超初始位置1e5的限制#xff0c;所以不能直接用奇数最多两次#xff0c;4的倍数最多两次的结论。spfa#xff0c;平方数的dis为1#xff0c;然后推出其他数的dis
#includebits/stdc.h
using namespace std;
#define int …题目
思路因为有走的过程不能超初始位置1e5的限制所以不能直接用奇数最多两次4的倍数最多两次的结论。spfa平方数的dis为1然后推出其他数的dis
#includebits/stdc.h
using namespace std;
#define int long long
const int maxn 2e5 5, inf 1e9, N 1e5;
int a[maxn];
int sq[maxn], dis[maxn];
int m;
// int f[320][maxn];
queueint q;
bool inque[maxn];
bool issq(int x){int sqt sqrt(x);return sqt * sqt x;
}
void solve(){int Q;cin Q;memset(dis, 0x3f, sizeof(dis));for(int i 1; i * i 1e5; i){sq[m] i * i;dis[i * i N] 1;q.push(i * i);dis[-i * i N] 1;q.push(-i * i);inque[i * i N] inque[-i * i N] 1;}while(!q.empty()){int u q.front();q.pop();inque[u N] 0;for(int i 1; i m; i){int v u sq[i];if(v -N v N){if(dis[u N] 1 dis[v N]){dis[v N] dis[u N] 1;q.push(v);inque[v N] 1;}} v u - sq[i];if(v -N v N dis[u N] 1 dis[v N]){dis[v N] dis[u N] 1;q.push(v);inque[v N] 1;}}}while(Q--){int d;cin d;cout dis[d N] \n;}
// for(int i 99900; i N; i){
// cout dis[i N] ;
// }
}
signed main(){
// memset(f, 0x3f, sizeof(f));int T 1;
// cin T;while(T--){solve();}return 0;
}
