茅断卉 发表于 2025-11-24 13:05:12

热身赛总结 题解

1. 旅行计划

赛时思路

因为目标是：求出一直向东以城市 \(i\) 为终点最多能够游览多少个城市，我进行逆向思维，转换题意，将目标改成：以城市 \(i\) 为起点一直向西最多能够游览多少个城市，再看题目的数据范围：$n \le 10^5 $，因此便直接用 dfs 进行搜索，最后 TLE 了4个点 QwQ 。
改进思路

因为题目中说图中没有环，因此我们可以通过 DP 解决此题，所以我们就可以通过记忆化递归防止进行无效的 dfs 。
AC代码

点开有惊喜#include#define ll long longusing namespace std;ll n,m,x,y,dp;vectort;ll dfs(ll x,ll val){        if(!t.size()) return val;        ll mx=0;        for(auto y:t){                if(!dp) dp=dfs(y,val);                mx=max(mx,dp);        }        return mx+1;}int main(){        cin>>n>>m;        for(int i=1;i>x>>y;                t.push_back(x);        }        for(int i=1;i>x;                        zh[++cnt]=x;                        cxa(1,1,n,x,1);                }                else if(ch=='Q'){                        cin>>x;                        if(!check(1,1,n,x)){                                coutm;        for(int i=1;i>a;                l=max(l,a);                r+=a;        }        while(l

茹静曼 发表于 2025-12-11 01:32:05

鼓励转贴优秀软件安全工具和文档！

丁若云 发表于 2025-12-15 05:43:54

收藏一下   不知道什么时候能用到

甘子萱 发表于 2025-12-15 16:18:04

前排留名，哈哈哈

廖雯华 发表于 2026-1-4 14:56:41

这个有用。

县挫伪 发表于 2026-1-18 08:17:51

东西不错很实用谢谢分享

决任愧 发表于 2026-1-19 13:26:26

分享、互助 让互联网精神温暖你我

糙昧邵 发表于 2026-1-19 23:54:27

这个好，看起来很实用

那虻 发表于 2026-1-21 18:56:33

感谢分享，学习下。

纪晴丽 发表于 2026-1-22 06:16:26

谢谢分享，辛苦了

步雪卉 发表于 2026-1-23 13:04:25

东西不错很实用谢谢分享

迭婵椟 发表于 2026-1-24 11:49:44

过来提前占个楼

杜优瑗 发表于 2026-1-24 20:09:53

感谢，下载保存了

崔竹 发表于 2026-1-25 10:01:00

谢谢分享，辛苦了

仇华乐 发表于 2026-1-25 11:30:24

懂技术并乐意极积无私分享的人越来越少。珍惜

羊舌正清 发表于 5 天前

过来提前占个楼

套缈 发表于 5 天前

谢谢分享，试用一下

鄂缮输 发表于 13 小时前

很好很强大我过来先占个楼 待编辑

高清宁 发表于 1 小时前

用心讨论，共获提升！
页: [1]
查看完整版本: 热身赛总结 题解