企业官网建设流程全解析

清河做网站,8黄页网站建设,如何用模板建站,网站开发实用技术​欢迎大家订阅我的专栏#xff1a;算法题解#xff1a;C与Python实现#xff01; 本专栏旨在帮助大家从基础到进阶 #xff0c;逐步提升编程能力#xff0c;助力信息学竞赛备战#xff01; 专栏特色 1.经典算法练习#xff1a;根据信息学竞赛大纲#xff0c;精心挑选…​欢迎大家订阅我的专栏算法题解C与Python实现本专栏旨在帮助大家从基础到进阶 逐步提升编程能力助力信息学竞赛备战专栏特色1.经典算法练习根据信息学竞赛大纲精心挑选经典算法题目提供清晰的代码实现与详细指导帮助您夯实算法基础。2.系统化学习路径按照算法类别和难度分级从基础到进阶循序渐进帮助您全面提升编程能力与算法思维。适合人群准备参加蓝桥杯、GESP、CSP-J、CSP-S等信息学竞赛的学生希望系统学习C/Python编程的初学者想要提升算法与编程能力的编程爱好者附上汇总贴USACO历年白银组真题解析 | 汇总-CSDN博客【题目来源】洛谷[P10135 USACO24JAN] Potion Farming S - 洛谷【题目描述】你正在玩你最喜欢的手机游戏。在尝试收集药水以便有机会击败传说中的牛头怪boss。游戏地图是一系列标有1…N的房间这些房间由N-1条边连接形成一棵树( 2 ≤ N ≤ 10 5 ) (2\le N\le 10^5)(2≤N≤105)。你可以通过进行一系列的“遍历”来探索地图。一次遍历是从房间1到树中任何其他房间的一条简单路径。一次遍历结束后你可以从房间1开始另一次遍历。一旦地图的每个房间至少被遍历过一次地图就算完成。你的主要目标是用最少的遍历次数完成地图。 你的次要目标是尽可能多地收集药水。在一次遍历开始前一瓶药水会在地图上的某个房间生成。通过在当前遍历中生成药水的房间你就可以捡起它。如果你没有捡起药水那么它将在当前遍历结束后消失所以你不能在未来的遍历中捡起它。 作为一个聪明的程序员在查看游戏文件后你能够在接下来的N次遍历之前找出药水将出现在哪里。如果你在最少的遍历次数内完成地图你可以从地图上收集到的最大数量的药水是多少【输入】输入的第一行包含一个整数N表示地图中房间的数量。 然后是N个空格分隔的整数p 1 p 2 … p N p_1p_2\dots p_Np1​p2​…pN​其中1 ≤ p i ≤ N 1\le p_i\le N1≤pi​≤Np i p_ipi​表示在第i次遍历之前药水会出现在哪个房间。最后接着是N-1行每行有两个用空格分隔的整数*a b ( 1 ≤ a , b ≤ N ) a b(1\le a,b\le N)ab(1≤a,b≤N)*代表房间a和b之间的一条边。可以保证这些边组成了一棵树。【输出】输出一行包含一个整数即你可以在最少遍历次数的情况下从地图中获得的最大药水量。【输入样例】5 5 4 3 2 1 1 2 1 3 3 4 3 5【输出样例】2【算法标签】《洛谷 P10135 Potion Farming》 #USACO# #2024#【代码详解】#includebits/stdc.husingnamespacestd;constintN100005;intn,p[N],leaf[N],d[N];// leaf[x] -- 以 x 为根的子树中的叶子节点数量// d[x] -- 以 x 为根的子树最多能获得的药水数量vectorinte[N];// 邻接表存储树// 深度优先搜索计算每个子树的叶子节点数量voiddfs(intx,intfa){// 如果 x 不是根节点且是叶子节点度为1则 leaf[x] 1if(x!1e[x].size()1){leaf[x]1;}// 遍历所有子节点for(inti0;ie[x].size();i){intye[x][i];if(yfa)continue;// 避免回溯父节点dfs(y,x);leaf[x]leaf[y];// 累加子树的叶子数量}}// 计算每个子树最多能获得的药水数量voidcalc(intx,intfa){// 遍历所有子节点for(inti0;ie[x].size();i){intye[x][i];if(yfa)continue;// 避免回溯父节点calc(y,x);d[x]d[y];// 累加子树的药水数量}d[x]min(d[x],leaf[x]);// 药水数量不超过叶子数量}intmain(){scanf(%d,n);// 输入节点数量// 输入每个节点的优先级 p[i]for(inti1;in;i){scanf(%d,p[i]);}// 构建树的邻接表for(inti1;in;i){inta,b;scanf(%d%d,a,b);e[a].push_back(b);e[b].push_back(a);}dfs(1,0);// 从根节点开始计算叶子数量// 根据优先级分配初始药水前 leaf[1] 个优先级最高的节点获得 1 药水for(inti1;ileaf[1];i){d[p[i]];}calc(1,0);// 从根节点开始计算最大药水数量printf(%d\n,d[1]);// 输出根节点能获得的最大药水数量return0;}【运行结果】5 5 4 3 2 1 1 2 1 3 3 4 3 5 2