zhangxixi的博客

本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/15675706.html 题目链接 题目 相比 WildleopardWildleopardWildleopard 的家，他的弟弟 MildleopardMildleopardMildleopard 比较穷。他的房子是狭窄的，而且在他的房间里仅有一个灯泡。每天晚上，他徘徊在自己狭小的房子里，思考如何赚更多的钱。有一天，他发现他的影子的长度随着他在灯泡和墙壁之间走动时会发生变化。一个突然的想法出现在他的脑海里，他想知道在房间里他的影子的最大长度。 ...

本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/15674805.html 题目链接 题目 一个点每过一个单位时间就会向四个方向扩散一个距离，如图。 两个点a、b连通，记作e(a,b),当且仅当a、b的扩散区域有公共部分。连通块的定义是块内的任意两个点u、v都必定存在路径e(u,a0),e(a0,a1),…,e(ak,v)。给定平面上的n给点，问最早什么时刻它们形成一个连通块。 思路 二分答案+并查集。 首先二分时间 ttt。 如果两个点能直接相连，则他们的曼哈顿距离小于二倍 ttt。并且把...

本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/15674729.html 题目链接 题目 对于给定的一个长度为N的正整数数列 A1∼NA_{1\sim N}A1∼N​，现要将其分成 MMM（M≤NM\leq NM≤N）段，并要求每段连续，且每段和的最大值最小。 关于最大值最小： 例如一数列 4 2 4 5 14\ 2\ 4\ 5\ 14 2 4 5 1 要分成 333 段。 将其如下分段： [4 2][4 5][1][4\ 2][4\ 5][1] [4 2][4 5][1] 第一段和为 666...

本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/15674711.html 题目链接 题目 明明做作业的时候遇到了 nnn 个二次函数 Si(x)=ax2+bx+cS_i(x)= ax^2 + bx + cS​i​​(x)=ax​2​​+bx+c，他突发奇想设计了一个新的函数 F(x)=max{Si(x)},i=1…nF(x) = max{S_i(x)}, i = 1ldots nF(x)=max{S​i​​(x)},i=1…n。 明明现在想求这个函数在 [0,1000][0,1000][0,1...

本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/15673449.html 题目链接 题目 给定长度为 n 的数列 a，如果 （按位与），则在 i,j 之间存在一条长度为 的边，求 1 至所有点的最短路。 思路 暴力连边，边太多，最多 n2n^2n2 条，MLE+TLE。 于是考虑减少边的数量。 首先建32个虚点。 然后加入 aia_iai​ 在第 kkk 位上为1，就在 iii 和第 kkk 个虚点当中连边，边权为 aia_iai​。 这样最多有 n×32n\times 32n×32 条边。...

本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/15669626.html 题目链接 题目 给定一个长度为 nnn 的非负整数序列 AAA ，求一个平均数最大的，长度不小于 LLL 的子段。 思路 先二分平均值。 然后是判断。 如何判断一段数中是否存在长度大于等于 LLL 且平均值大于某个数的子段呢？ 我们可以先让序列中的数都减去二分中的值，然后就转化为： 序列中是否存在长度大于等于 LLL 的字段和为正。 我们可以先构造一个前缀和。 假设我们当前算到序列中的第 iii 项，我们只需要在前 i−...

本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/15669522.html 题目 一个有n个景点（入口）、m条单向道路的旅游胜地，单向是不友好的，因为这会让游客走很多冤枉路，而且从同一个入口出发，往不同方向走，能游玩的景点数目可能不同。于是，善良的Bob决定将道路全部改造成双向的，让每一个入口能逛的景点数量都确定下来，并制作景点数目表，让游客清楚地知道各个入口的景点数。但是，如果全部改成双向边之后，还需要修路，就可能导致景点数目表不正确。如果要景点数目表正确，请问哪些路是不能修的？ 思路 这题的...

本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/15669383.html 题目链接 题目 农夫约翰建造了一座有 间牛舍的小屋，牛舍排在一条直线上，第 间牛舍在 的位置，但是约翰的 头牛对小屋很不满意，因此经常互相攻击。约翰为了防止牛之间互相伤害，因此决定把每头牛都放在离其它牛尽可能远的牛舍。也就是要最大化最近的两头牛之间的距离。 牛们并不喜欢这种布局，而且几头牛放在一个隔间里，它们就要发生争斗。为了不让牛互相伤害。John 决定自己给牛分配隔间，使任意两头牛之间的最小距离尽可能的大，那么，这个...

本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/15669038.html 完成情况：(7/9) cf1110e 题目链接 我要是在noip前做这道题就好了。 这道题的本质就是noip2021方差中的一个性质，对于每个数进行修改，就是把它左右的差进行交换。 注意的是首项一定要一样。 Code 123456789101112131415161718192021222324252627282930313233343536373839// Problem: CF1110E Magic Stones//...

本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/15664786.html 题目链接 题目 You are given a sequence of numbers a1, a2, …, an, and a number m. Check if it is possible to choose a non-empty subsequence aij such that the sum of numbers in this subsequence is divisible by m. 给出 111 ...