zhangxixi的博客

本文搬运自本人博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/16331782.html 题目地址 A CF771A 若 a 和 b 是朋友，且 b 和 c 是朋友，那么 a 和 c 也是朋友。 看到这类字眼，一般就是说明是由完全图组成。 B CF449B 做法大致是先全部做一遍最短路，然后每个关键点判断是否能由相连点加上公路长度所得。 此题运用的是一条边可以去掉是它可以被替代。 C CF1340C 此题到达每个路口涉及时间，很明显的分层图 此题建边后边权非0即1，很明显01bfs 我认为此题唯一难点是推...

本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/16323376.html 有一元二次方程： ax2+bx+c=0(a≠0)\Large ax^2+bx+c=0\quad(a\ne 0) ax2+bx+c=0(a=0) 其两个根为： x1=−b+b2−4ac2a,x2−b−b2−4ac2a(△=b2−4ac⩾0)\Large x_1=\frac{-b+\sqrt{b^2-4ac}}{2a},x_2\frac{-b-\sqrt{b^2-4ac}}{2a} \quad(\vartriangle=b...

本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/16306588.html 题目链接 题目 DNA链由核苷酸组成。有四种类型的核苷酸：“A”，“T”，“G”，“C”。 DNA链是核苷酸序列。科学家决定追踪一种稀有物种的进化，它最初的DNA链为s。 物种的进化被描述为DNA的一系列变化。每个变化都是某些核苷酸的变化，例如，DNA链“AAGC”中可能发生以下变化：第二个核苷酸可以变为“T”，然后变成“ATGC”。 科学家们知道DNA链的某些片段会受到某些未知感染的影响。这些感染可以被表示为核苷酸序列...

本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/16302197.html 题目链接 题目 这是一道交互题 你和Li ChenLi\ ChenLi Chen正在玩一个奇怪的游戏。给出一棵NNN个点的树，双方分别给顶点编号为111到NNN，双方都不知道对方给树编号的方式。 接着双方在自己对应的树上选择一个联通子图，在你的编号方式对应的树上你选择了x1,x2,...,xk1x_1,x_2,...,x_{k_1}x1​,x2​,...,xk1​​，在Li ChenLi\ ChenLi Chen的编号方...

本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/16297018.html 题目链接 题目 给定第 000 个时刻的 n×mn \times mn×m 的 010101 矩阵。 每过一个时刻，010101 矩阵都会发生如下的变化： 考虑第 xxx 行第 yyy 列的格子。若其上下左右四个方向中相邻的格子存在与其数字相同的格子，则此格子在下一个时刻会变成另一个数字（000 变 111，111 变 000）。 有 ttt 次询问。每次询问你在第 ppp 个时刻第 xxx 行第 yyy 列的格子上的...

本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：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= ...