隔了一年零三个月，重新刷URAL，这题挺麻烦的输出路径。输出路径挺扯的，乱写了写乱改改就A了。。。我本来想用很靠谱，记录每一条路径的，然后输出最小的，结果Tle，然后我使劲水水又过了一组，发现别人的题解。。直接来了一次 就过了。。我乱搞了搞，倒着记录最小的，然后倒着输出，就过了。。。
#include <cstring>
#include <cstdio>
#include <string>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
#define INF 10000000
int dp[][];
int pre[][];
int s[];
struct node
{
int a,b;
};
void spfa()
{
int i,a,b;
queue<node> que;
node temp,u,v;
for(i = ; i < ; i ++)
{
temp.a = i;
temp.b = i*i;
dp[i][i*i] = ;
pre[i][i*i] = i;
que.push(temp);
}
while(!que.empty())
{
u = que.front();
a = u.a;
b = u.b;
que.pop();
if(a > ) continue;
if(b > ) continue;
for(i = ; i < ; i ++)
{
v.a = i+a;
v.b = i*i+b;
if(i + a > ) continue;
if(i*i + b > ) continue;
if(dp[v.a][v.b] > dp[u.a][u.b] + )
{
pre[v.a][v.b] = i;
dp[v.a][v.b] = dp[u.a][u.b] + ;
que.push(v);
}
}
}
return ;
} int main()
{
int t,n,m,i,j;
int top;
for(i = ; i <= ; i ++)
{
for(j = ; j <= ; j ++)
{
dp[i][j] = INF;
pre[i][j] = INF;
}
}
spfa();
scanf("%d",&t);
top = ;
while(t--)
{
scanf("%d%d",&n,&m);
if(n > ||m > )
{
printf("No solution\n");
continue;
}
else if(dp[n][m] > )
{
printf("No solution\n");
continue;
}
int top = ;
while(n&&m)
{
i = pre[n][m];
s[top++] = i;
n = n - i;
m = m - i*i;
}
for(i = top-;i >= ;i --)
printf("%d",s[i]);
printf("\n");
}
return ;
}