首页 > 其他分享 >嘿嘿,天城大人嘿嘿嘿——苍与红的试炼 题解

嘿嘿,天城大人嘿嘿嘿——苍与红的试炼 题解

时间:2022-08-19 21:11:19浏览次数:65  
标签:试炼 int 题解 sum 苍与 tail 天城 new mod

苍与红的试炼

image

嘿嘿天城大人,嘿嘿天城大人您要怎么蹂躏我嘿嘿。

众所周知,我是老指挥官了,所以看到这道题异常兴奋。然而我发现这道题好像是改编题,网上找不到题解,怎么能冷落天城大人呢?所以在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年的关东大地震导致天城舰体受损严重,不得已拆解,由赤城代替其改装成航母,所以碧蓝里天城的自我介绍是:

天城级战列巡洋舰首舰·天城,原本预定要和妹妹赤城一起接受改造成为航母……可惜我不幸在那场地震中倒下……咳咳……如您所见,我的身体不是很好,不过还请不要有所顾虑。

(左为赤城,右为加贺)

毕竟天城属于出师未捷身先死的典范,也没那么多扯的了。

最后,天城老婆镇楼。

image

标签:试炼,int,题解,sum,苍与,tail,天城,new,mod
From: https://www.cnblogs.com/TSTYFST/p/16603325.html

相关文章

  • 【题解】[FARIO2013]Torusia
    通信题,小A和小B迷失在\(4096\times4096\)的方阵中。方阵是循环的,比如\((0,4095)\)的右边是\((0,0)\),上面是\((4095,4095)\)。两人都不知道自己的绝对位置。每......
  • 桐柏邀请赛 S10 题解
    EnchantedLove记\(S=a_1+a_2+\cdots+a_n\),那么:若\(S\)为偶数,则答案为\(\frac{S}{2}\)。否则,我们找到\(a\)中最小的奇数(显然此时\(a\)中必然有至少一个奇数),设......
  • 【题解】CF1720C
    题意简述给你一个01矩阵,每一次你可以在这个矩阵中找到一个\(L\)型,将它全部变成0。\(L\)型的定义是在一个\(2*2\)矩阵中,除开一个角之外的图形,其中必须包含至少一个......
  • QT“程序异常结束”问题解决
    今天用QT写个小程序,出现了一个小问题,就是程序编译通过了,也能运行,但是有一个按键按下后程序就会异常结束。解决办法:由于文件中有多个类,而使用某个类的函数时,存在对象只声......
  • P1967 [NOIP2013 提高组] 货车运输 题解
    题目描述A国有\(n\)座城市,编号从\(1\)到\(n\),城市之间有\(m\)条双向道路。每一条道路对车辆都有重量限制,简称限重。现在有\(q\)辆货车在运输货物,司机们想知道......
  • 题解P2143 [JSOI2010] 巨额奖金
    题意就是让你求有多少种最小生成树生成树用kruskal求就好了我们考虑用dfs中用乘法原理去计数#include<bits/stdc++.h>#defineN1000100usingnamespacestd;ty......
  • ARC097E题解
    感觉挺一眼的啊?众所周知如果序列\(i\)要通过相邻两项交换变成\(p_i\),那么交换次数就是\(\sum_{i<j}[p_i>p_j]\),或者说线段\((i,p_i)\)相交的对数。于是一个很naiv......
  • 【题解】 洛谷P3694 邦邦的大合唱站队
    发现尽管\(n\)比较大,但\(m\)非常小,于是考虑状压。记\(dp_{i}\)表示满足条件的乐队集合为\(i\)时的最小出队人数,\(dp_i=\min\{dp_{i\\xor\\1<<k}\}+w_{i\\xo......
  • [CF1450F] The Struggling Contestant 题解
    \(\mathtt{Link}\)CF1450FTheStrugglingContestant-洛谷|计算机科学教育新生态(luogu.com.cn)\(\mathtt{Description}\)\(T\)组数据。一共有\(n\)道题,题号......
  • P5080 Tweetuzki 爱序列 题解
    题目传送门更好地阅读体验题目大意Tweetuzki有一个长度为\(n\)的序列\(a_1,a_2,\cdots,a_n\)。他希望找出一个最大的\(k\),满足在原序列中存在一些数\(b_1,b......