SP279 INUMBER - Interesting number 题解
题目链接:INUMBER - Interesting number
题意:
对于给定的数 \(n\),求出能被 \(n\) 整除的最小正整数,其位数之和为 \(n\)。
输入格式:
第一行,输入一个整数 \(T\),是测试用例的数量。
接下来的 \(T\) 行,每行输入一个整数 \(n\) 。
输出格式:
共 \(T\) 行,答案。
数据范围:
\(1 \le T \le 50,~1 < n \le 10^3\) 。
这个题貌似是05年的题,比 cxy 还大。 (但是 cxy
是萌妹子/oh)
看上去就是个搜索题。考虑 bfs 。记状态 \((x,y)\) 表示当前位数的和为 \(x\) ,实际数\(\bmod n\) 的值为 \(y\) 。
初始状态 \((0,0)\) ,我们需要的是 \((n,0)\) 。其实还是蛮套路的,主要考察的就是模 \(n\) 这个优化。
时间复杂度 \(\mathcal{O}(n^2)\)
代码:
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
typedef pair<int,int> pii;
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
#define N ((int)(1e3 + 55))
#define Fi first
#define Se second
char obuf[N];
int tim(0), vis[N][N];
pair<pii,int> pre[N][N]; queue<pii> q;
void solve()
{
int n,x(-1),y(-1); cin >> n; ++tim; while(!q.empty()) q.pop();
for(q.emplace(0,0); !q.empty(); )
{
x = q.front().Fi, y = q.front().Se; q.pop();
if(x == n && y == 0) break;
for(int i = (x ? 0 : 1); i <= 9; i++)
{
int tx = x + i, ty = (y * 10 + i) % n;
if(tx > n || vis[tx][ty] == tim) continue;
vis[tx][ty] = tim; pre[tx][ty] = {make_pair(x,y), i};
q.emplace(tx,ty);
}
}
int O = 1015; x = n; y = 0;
while(x || y)
{
obuf[O--] = '0' + pre[x][y].Se;
tie(x,y) = pre[x][y].Fi;
}
cout << obuf + O + 1 << '\n';
}
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
// freopen("check.in","r",stdin);
// freopen("check.out","w",stdout);
int Q; cin >> Q; while(Q--) solve();
return 0;
}
参考文献:
[2] https://github.com/gcdart/PC-solutions/blob/master/Spoj/INUMBER.cpp