苍与红的试炼
嘿嘿天城大人,嘿嘿天城大人您要怎么蹂躏我嘿嘿。
众所周知,我是老指挥官了,所以看到这道题异常兴奋。然而我发现这道题好像是改编题,网上找不到题解,怎么能冷落天城大人呢?所以在Silver_ash以及他出的比赛的帮助下,A了这道题。祝你们成功。
知识点:数位DP
一般来说,数位DP的题目要么写成循环的形式,要么写成记忆化搜索的形式,但这道题比较特殊,需要写成bfs
的形式。
因为要求最优解,并且没有给上限,而dfs
无法保证搜索的顺序,所以最坏的情况需要跑满整棵搜索树,时间复杂度显然无法接受。
而 bfs
会优先搜索小的情况,同时可以剪枝跳过属性相同的情况,复杂度 \(O(sd)\),在可接受范围内。
思路
按照数位DP的思路,我们从高位往低位选。
枚举当前位填的数,记录下当前数的性质,即当前数每一位的和以及 \(\%d\) 的余数。判断该性质是否出现过。如果该性质出现过,那当前数一定不是最优解。
为什么?显然,相同性质的数对答案的贡献是相同的。由于bfs
一层一层搜索的特性,会先搜索到较小的数,那另一个性质相同的数显然比我们现在搜到的数小,肯定是另一个数更优,所以当前的情况就可以舍弃了。
要注意的是,在算 \(\%d\) 的余数的时候,我们肯定不能把所有位上的数整合成一个大数。考虑取模运算的性质,\(a \% b = c\) 那么 \((a \times 10 + d)\% b = (c \times 10 + d) \% b\),所以 \(mod_{now} = (mod_{last} \times 10 + i)\%d\)。
统计答案的话,我们记录下每一位上可能的答案,同时记录它的前驱,即搜索树中的父节点,在第一次找到合适的数的时候就直接递归输出即可。(不会的话建议重修栈与队列专题)。
Code
#include<queue>
#include<cstdio>
using namespace std;
const int MAXD = 510, MAXS = 5010;
int d, s, head, tail;
int pre[MAXS * MAXD]; //搜索树最多有 s * d 个节点
char ans[MAXS * MAXD];
bool used[MAXS][MAXD]; //判断一种性质是否出现过
struct Number{
int sum/*每一位的数的加和*/, mod/*模 d 的余数*/;
};
queue<Number> q;
void Print(int pos){
if(pos == 1) return;
Print(pre[pos]);
putchar(ans[pos]);
} //递归输出
void bfs(){
q.push((Number){0, 0}); //最开始一个数也不选
used[0][0] = true;
tail++;
while(!q.empty()){
int now_sum = q.front().sum;
int now_mod = q.front().mod;
q.pop();
head++;
for(register int i = 0; i <= 9; i++){
int new_sum = now_sum + i; //当前数每一位的加和
int new_mod = (now_mod * 10 + i) % d; //余数
if(new_sum > s) break; //剪枝,每一位上的加和大于 s 了肯定没希望了
if(used[new_sum][new_mod]) continue;
if(new_sum == s && !new_mod){ //如果找到了符合要求的数
pre[++tail] = head; //记录前驱
ans[tail] = i + 48; //记录答案
Print(tail); //递归输出
return; //直接结束
}
used[new_sum][new_mod] = true; //这种性质已有
q.push((Number){new_sum, new_mod}); //入队
tail++;
pre[tail] = head; //记录前驱
ans[tail] = i + 48; //记录答案
}
}
puts("-1"); //没有符合要求的数,输出 -1
}
int main(){
scanf("%d%d", &d, &s);
bfs();
return 0;
}
最后扯点闲篇
既然题目背景是天城老婆的话,科普一下天城吧。
天城是游戏《碧蓝航线》中的角色。
天城是一名重樱阵营的超稀有级战巡舰娘,原型为旧日本天城级战列巡洋舰1号舰。——百度百科
由于国内离谱的河蟹,天城的代号是“鳐 ”。
毕竟我没有天城,加上我游戏剧情推的慢的离谱,所以相较于游戏设定,我对天城的历史原型反而了解的更多。
天城级战列巡洋舰(日语:天城型巡洋戦舰、あまぎがたじゅんようせんかん)是日本海军“八八舰队”计划的主力之一。也是在长门级战列舰的舰体基础上加装一座双联装主炮,炮塔布置与加贺级战列舰相似,可以说是加贺级的轻装甲快速型,减簿装甲,舷侧装甲带采用倾斜式设计,取消了以往日本战舰水平装甲延伸到舷侧水线以下的“穹甲结构”。副炮全部都在同一层甲板。天城级的假想对手是美国海军的6艘列克星顿级战列巡洋舰。
由于《华盛顿海军条约》,“八八舰队”计划流产。
顺带着也科普下IGN的“八八舰队”计划。
到1923年装备舰龄未满8年的八艘战列舰和八艘战列巡洋舰。
天城级共四艘,一号舰“天城”,二号舰“赤城”,三号舰“高雄”,四号舰“爱宕”,《华盛顿海军条约》签订时,天城和赤城造到了一半,高雄和爱宕直接拆解。
本身天城是要改装成航母的,然而1923年的关东大地震导致天城舰体受损严重,不得已拆解,由赤城代替其改装成航母,所以碧蓝里天城的自我介绍是:
天城级战列巡洋舰首舰·天城,原本预定要和妹妹赤城一起接受改造成为航母……可惜我不幸在那场地震中倒下……咳咳……如您所见,我的身体不是很好,不过还请不要有所顾虑。
(左为赤城,右为加贺)
毕竟天城属于出师未捷身先死的典范,也没那么多扯的了。
最后,天城老婆镇楼。