蓝桥杯一日游(试题E:路径 题解)

昨天第一次参加蓝桥杯,就遇到了史上最难的题目!之前听学长说暴力杯拿奖很容易,还有学分拿,就动心了!没想到暴力杯一去不复返~~搭进去300块钱,罚坐四小时。出来一对答案,估计拿了不到40分(太羞耻了)

说几点反思吧:赛前练的比较多的dfs遇到实际题目又不会写了,前面时间花的太久以至于能骗分的题目都没有完全骗到手,就完全空着...把时间Allin某一题的坏习惯真的要改,最近好几场比赛都因为这个拉垮了...至少要把所有题目都看一遍吧。

不过令人高兴的是本来没有抱太大希望的最后一道填空题做对了,算是给失败的竞赛过程留下了一点美好回忆吧。

这题用到的dp其实我赛前准备的是比较少的,但是还是做出来了。知乎上说用弗洛伊德或者是Dij是完全没有接触过。

试题E:路径
小蓝学习了最短路径之后特别高兴,他定义了一个特别的图,希望找到图
中的最短路径。
小蓝的图由2021个结点组成,依次编号1至2021。
对于两个不同的结点a,b,如果a和b的差的绝对值大于21,则两个结点
之间没有边相连;如果a和b的差的绝对值小于等于21,则两个点之间有一条
长度为a和b的最小公倍数的无向边相连。
例如:结点1和结点23之间没有边相连;结点3和结点24之间有一条无
向边,长度为24;结点15和结点25之间有一条无向边,长度为75。
请计算,结点1和结点2021之间的最短路径长度是多少。

(可折叠)

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll number[2099][25];
ll lcm(ll a,ll b)
{
    return a*b/(__gcd(a,b));
}
ll ans[2099];
int main()
{
    for(ll i=1;i<=2021;i++)
    {
        for(ll j=1;j<=21;j++)
        {
            number[i][j]=lcm(i,i+j);
        }
    }
    //打表算出LCM的值
    for(ll i=1;i<=2021;i++)
    {
        for(ll j=1;j<=21;j++)
        {
            if(ans[i+j]==0)ans[i+j]=ans[i]+number[i][j];//从i走j步,如果ans[i+j]==0就说明第i+j个点还没有走过,就尝试从i走到j
            else ans[i+j]=min(ans[i+j],ans[i]+number[i][j]);//第i+j个点之前已经走过了,所以要判断从当前点走j步的结果是否比不走更小
        }
    }
    cout<<ans[2021];//输出结果
    return 0;
}

这个做法应该是比知乎大佬说的方法更简洁一些,可以秒出结果。

求求拿个省三吧!至少把报名费给我报销了🙏🙏🙏

 

 

更新:报名费成功报销!(省二)

文章标题:蓝桥杯一日游(试题E:路径 题解)
文章链接:https://intmain0.com/120/
本作品采用知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议进行许可。转载请注明出处
评论和私信会在第一时间回复。如果您觉得文章对您有帮助,可以点击文章右下角【分享】一下。您的鼓励是博主的最大动力!
暂无评论

发送评论 编辑评论


|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇