用商城系统做教育网站,国家和住房城乡建设部网站首页,中文域名网站有哪些,网站建设报价清单内容蓝桥杯备赛 | 洛谷做题打卡day18 文章目录 蓝桥杯备赛 | 洛谷做题打卡day18旅行计划题目描述输入格式输出格式样例 #1样例输入 #1样例输出 #1 提示题解代码我的一些话 旅行计划
题目描述
Kira酱要去一个国家旅游。这个国家有 N N N 个城市#xff0c;编号为 1 1 1 至 N N… 蓝桥杯备赛 | 洛谷做题打卡day18 文章目录 蓝桥杯备赛 | 洛谷做题打卡day18旅行计划题目描述输入格式输出格式样例 #1样例输入 #1样例输出 #1 提示题解代码我的一些话 旅行计划
题目描述
Kira酱要去一个国家旅游。这个国家有 N N N 个城市编号为 1 1 1 至 N N N并且有 M M M 条道路连接着Kira准备从其中一个城市出发并只往东走到城市 i i i 停止。
所以她就需要选择最先到达的城市并制定一条路线以城市 i i i 为终点使得线路上除了第一个城市每个城市都在路线前一个城市东面并且满足这个前提下还希望游览的城市尽量多。
现在你只知道每一条道路所连接的两个城市的相对位置关系但并不知道所有城市具体的位置。现在对于所有的 i i i都需要你为Kira酱制定一条路线并求出以城市 i i i 为终点最多能够游览多少个城市。
输入格式
第一行为两个正整数 N , M N, M N,M。
接下来 M M M 行每行两个正整数 x , y x, y x,y表示了有一条连接城市 x x x 与城市 y y y 的道路保证了城市 x x x 在城市 y y y 西面。
输出格式 N N N 行第 i i i 行包含一个正整数表示以第 i i i 个城市为终点最多能游览多少个城市。
样例 #1
样例输入 #1
5 6
1 2
1 3
2 3
2 4
3 4
2 5样例输出 #1
1
2
3
4
3提示
均选择从城市 1 1 1 出发可以得到以上答案。
对于 20 % 20\% 20% 的数据 1 ≤ N ≤ 100 1\le N ≤ 100 1≤N≤100对于 60 % 60\% 60% 的数据 1 ≤ N ≤ 1000 1\le N ≤ 1000 1≤N≤1000对于 100 % 100\% 100% 的数据 1 ≤ N ≤ 100000 1\le N ≤ 100000 1≤N≤100000 1 ≤ M ≤ 200000 1\le M ≤ 200000 1≤M≤200000。 题解代码 学会利用新知自己多试试并尝试积攒一些固定解答方案debug以下是题解代码 ~ #includeiostream
#includecstdio
#includealgorithm
#includequeue
#includemap
#includecmath //别忘记头文件哦
using namespace std;
int n,m,lin[100010],in[100010],total,f[100010];
queueintq;
struct cym{int to,next;
}e[400010];
int main()
{scanf(%d%d,n,m);for(int i1;im;i){int x,y;scanf(%d%d,x,y);e[total].toy;e[total].nextlin[x];lin[x]total;in[y];}for(int i1;in;i)if(in[i]0){f[i]1;q.push(i);}while(!q.empty()){int cntq.front();q.pop();for(int ilin[cnt];i;ie[i].next){f[e[i].to]max(f[e[i].to],f[cnt]1);if(--in[e[i].to]0)q.push(e[i].to); } }for(int i1;in;i)printf(%d\n,f[i]);
}我的一些话 今天来巩固动态规划dp很显然每个点的答案是它所有前驱节点的答案加1即f[i]max(f[i],f[j]1); 考虑空间复杂度用邻接表存图在拓扑排序同时DP就好了不用再外面再做什么工作。多思考思路还是很好掌握的虽然一次性AC有一定难度需要通盘的考虑和理解以及扎实的数据结构基础才能独立写出AC代码。但无论难易大家都要持续做题保持题感喔一起坚持(o´ωo) 如果有非计算机专业的uu自学的话关于数据结构的网课推荐看b站上青岛大学王卓老师的课讲的很细致有不懂都可以私信我喔 总结来说思路很重要多想想多在草稿纸上画画用测试数据多调试debug后成功编译并运行出正确结果真的会感到很幸福 关于之前蓝桥杯备赛的路线和基本方法、要掌握的知识之前的博文我都有写欢迎大家关注我翻阅自取哦~ 不管什么都要坚持吧三天打鱼两天晒网无法形成肌肉记忆和做题思维该思考的时候一定不要懈怠今天就说这么多啦欢迎评论留言一起成长
