阜宁县建设局网站响应式网站头部

题目

思路：因为有走的过程不能超初始位置1e5的限制，所以不能直接用奇数最多两次，4的倍数最多两次的结论。spfa，平方数的dis为1，然后推出其他数的dis

#include<bits/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];
queue<int> 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;
}