zhangxixi的博客

本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/16289494.html 题目链接 题目 Farmer John wants to set up a telephone line at his farm. Unfortunately, the phone company is uncooperative, so he needs to pay for some of the cables required to connect his farm to the phone system. The...

本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/16285749.html 题目链接 题目 对于完全图 GGG，若有且仅有一棵最小生成树为 TTT，则称完全图 GGG 是树 TTT 扩展出的。 给你一棵树 TTT，找出 TTT 能扩展出的边权和最小的完全图 GGG。 思路 要使一个图总存在唯一最小生成树，需满足所有非最小生成树的边（假设连接 u,vu,vu,v），使这条边的边权 www 大于 u,vu,vu,v 在最小生成树上的最短路径的最大边权。 因此，我们可以先dfs一遍求出每个点到根节点...

本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/16267581.html 题目链接 题目 发展采矿业当然首先得有矿井，小 FF 花了上次探险获得的千分之一的财富请人在岛上挖了 nnn 口矿井，但他似乎忘记考虑的矿井供电问题…… 为了保证电力的供应，小 FF 想到了两种办法： 在这一口矿井上建立一个发电站，费用为 vvv（发电站的输出功率可以供给任意多个矿井）。 将这口矿井与另外的已经有电力供应的矿井之间建立电网，费用为 ppp。 小 FF 希望身为「NewBe_One」计划首席工程师的你帮他想...

本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/16254702.html 题目链接 题目 原题来自：CEOI 1999 给定一张无向图，求图中一个至少包含 3 个点的环，环上的节点不重复，并且环上的边的长度之和最小。该问题称为无向图的最小环问题。在本题中，你需要输出最小环的方案，若最小环不唯一，输出任意一个均可。若无解，输出 No solution.。图的节点数不超过 100。 思路 先不管方案，就是一个无向图求最小环问题。 那就是一个floyd，每一次把 kkk 作为中转点前，先去统计与 ...

本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/16250248.html 题目链接 题目 知道黑暗城堡有 NNN 个房间，MMM 条可以制造的双向通道，以及每条通道的长度。 城堡是树形的并且满足下面的条件： 设 DiD_iDi​为如果所有的通道都被修建，第 iii 号房间与第 111 号房间的最短路径长度； 而 SiS_iSi​ 为实际修建的树形城堡中第 iii 号房间与第 111 号房间的路径长度； 要求对于所有整数 i(1≤i≤N)i(1≤i≤N)i(1≤i≤N)，有 Si=DiS_i= ...

本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/16207447.html 题目链接 题目 Xenia the beginner programmer has a sequence $ a $ , consisting of $ 2^{n} $ non-negative integers: $ a_{1},a_{2},…,a_{2^{n}} $ . Xenia is currently studying bit operations. To better understand how they ...

本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/16203821.html 题目链接 题目 We saw the little game Marmot made for Mole's lunch. Now it's Marmot's dinner time and, as we all know, Marmot eats flowers. At every dinner he eats some red and white flowers. Therefore a dinner can be r...

本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/16199885.html 题目链接 题目 Quite recently a creative student Lesha had a lecture on trees. After the lecture Lesha was inspired and came up with the tree of his own which he called a $ k $ -tree. A $ k $ -tree is an infinite rooted...

本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/16195913.html 题目链接 题目 Kefa decided to celebrate his first big salary by going to the restaurant. He lives by an unusual park. The park is a rooted tree consisting of $ n $ vertices with the root at vertex $ 1 $ . Vertex $ 1 $ ...

本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/16195790.html 题目链接 题目 Alex doesn't like boredom. That's why whenever he gets bored, he comes up with games. One long winter evening he came up with a game and decided to play it. Given a sequence $ a $ consisting of $ n $ inte...