差分数组 前面学习了前缀和，根据前缀和的定义，我们可以知道如下等式：对于数组，有 则s数组便为a数组的前缀和数组。<view>那么差分的定义又是什么呢？对于数组，有</view> 则d数组便为a数组的差分数组。 差分数组的理解 我们可以根据式子知道，差分数组d中每一个值，代表的是a数组当前位置的元素与前一元素相减的结果，即相邻两数的差距。 下面用例题来讲一讲吧。 NOIP2013积木大赛 这一题仔细想想，如果需要另外在一段连续区间[l,r]中搭建积木的话，说明这一区间的长度是大于这个区间外的相邻两个积木的高度的。那么我们只需要关注差分数组，从前往后扫一遍差分数组，...

前缀和 及 前缀和的变形 前言 听完zngg的课后，我顿时醍醐灌顶，如同突破了瓶颈一般，感觉打开了一扇新世界的大门。现在稍微记录一下课堂笔记，届时便可反复复习。 前缀和 以往也是有了解过前缀和，但是也仅仅只是停留在表层，也就是最基本的题目，区间求和问题。对于一段长度为n的数列a1,a2,...,an定义前缀和为：则当需要求区间[l,r]各个元素之和时，便需要计算即可得出答案。 前缀和的变形 其实这么几年来对于前缀和的了解我也仅仅只停留在上面的定义。在听了zngg的课之后，了解到了前缀和的变形之后，我发现其实是我的思想没有打开，就是没有理解到前缀和的思想。对于上面最基本的前缀和的定义中，...

**1、栅栏迷宫 田野上搭建了一个黄金大神专用的栅栏围成的迷宫。幸运的是，在迷宫的边界上留出了两段栅栏作为迷宫的出口。更幸运的是，所建造的迷宫是一个“完美的”迷宫：即你能从迷宫中的任意一点找到一条走出迷宫的路。给定迷宫的宽W(1<=W<=38)及长H(1<=H<=100)。 2*H+1行，每行2*W+1的字符以下面给出的格式表示一个迷宫。然后计算从迷宫中最“糟糕”的那一个点走出迷宫所需的步数(就是从最“糟糕”的一点，走出迷宫的最少步数）。（即使从这一点以最优的方式走向最靠近的出口，它仍然需要最多的步数）当然了，黄金大神让你必须只会水平或垂直地在X或Y轴上移动，你不能从...

A病毒分裂 Time Limit:10000MS Memory Limit:165536K Case Time Limit:1000MS Description A 学校的实验室新研制出了一种十分厉害的病毒。由于这种病毒太难以人工制造了，所以专家们在一开始只做出了一个这样的病毒。 这个病毒被植入了特殊的微型芯片，使其可以具有一些可编程的特殊性能。最重要的一个性能就是，专家们可以自行设定病毒的分裂能力K，假如现在有x 个病毒，下一个分裂周期将会有Kx 个一模一样的病毒。你作为该实验室的数据分析员，需要统计出在分裂到第N 个周期前，一共有多少个病毒单体进行了分裂。一开始时总是只有一个病毒...

B疫情延迟 Description 由于A 学校生物实验室里那个不负责的数据分析员，实验室的病毒威力被错误估算，导致了可怕的病毒泄漏，现在病毒即将在校园内传播开来。 校园里一共有n 个建筑物，生物实验室总是位于一号建筑物且在0 时刻受到病毒入侵。这n 个建筑物由m 条单向道路相连（也有可能有建筑物被孤立）。每条道路有两个信息：它的长度，它是多少年前修建的。当一个建筑物被病毒入侵，从被入侵的时刻起，病毒会从所有由这个建筑物通向其他建筑物的道路按着这条道路的方向以1 个单位每秒的速度行进。 校长得知这个事情后，决定放弃这个学校逃跑。校长总是位于编号为n 的行政楼，从零时刻开始需要共T 秒来...

单调栈 目录 名词解释 实现 功能 例题 名词解释 要了解什么是单调栈，我们可以分开来理解一下什么叫“单调”，什么叫“栈”。 栈 先引入百度百科中栈的定义 栈（stack）又名堆栈，它是一种运算受限的线性表。限定仅在表尾进行插入和删除操作的线性表。这一端被称为栈顶，相对地，把另一端称为栈底。向一个栈插入新元素又称作进栈、入栈或压栈，它是把新元素放到栈顶元素的上面，使之成为新的栈顶元素；从一个栈删除元素又称作出栈或退栈，它是把栈顶元素删除掉，使其相邻的元素成为新的栈顶元素。 用自己的话来说，栈是一种数据结构，...

最小生成树 我们先来看看关于“最小生成树”百度百科给出的解释。 一个有 n 个结点的连通图的生成树是原图的极小连通子图，且包含原图中的所有 n 个结点，并且有保持图连通的最少的边。  如果单看这一句话，“连通图”、“极小连通子图”，这些概念是让人有一些懵，那么我用自己的理解来稍微直白地解释一下吧。   简述 对于n个点，存在m条带有权值的无向边将其相连（m>=n-1），选择合适的边使其各个点之间相互连通且权值最小，而找到的路径就叫最小生成树。 换一个实际一点的问题，假设n个独立起来的城市，现在需要建立道路使其n个城市之间可以相互到达。不同城市之间修路的费用有所不同...

John was absurdly busy for preparing a programming contest recently. He wanted to create a ridiculously easy problem for the contest. His problem was not only easy, but also boring: Given a list of non-negative integers, what is the sum of them? However, he made a very typical mistake when he wrote...

Some people think that the bigger an elephant is, the smarter it is. To disprove this, you want to take the data on a collection of elephants and put as large a subset of this data as possible into a sequence so that the weights are increasing, but the IQ’s are decreasing. Input The input will con...

It’s commonly known that the Dutch have invented copper-wire. Two Dutch men were fighting over a nickel, which was made of copper. They were both so eager to get it and the fighting was so fierce, they stretched the coin to great length and thus created copper-wire. Not commonly known is that the f...

A - Registration system A new e-mail service "Berlandesk" is going to be opened in Berland in the near future. The site administration wants to launch their project as soon as possible, that's why they ask you to help. You're suggested to implement the prototype of site registration syste...

A题 洛谷 P7286 “我们在 小 Z 面前秀个恩爱吧。” “好的。” 小 Z 发现他身边都是人赢，这使他非常自闭。 小 Z 又看着身边的潇，不禁陷入了沉思…… 题目描述 潇有一个数组 kk，下标为 11 到 nn 。 潇定义 f(x,y)=\begin{cases} \min(k_x,k_y) \times (x + y) &x \ne y \\ k_x\times x&x=y \end{cases}f(x,y)={min(kx​,ky​)×(x+y)kx​×x​x=yx=y​ 。 潇想知道对于任意的 1 \le x,y \le n1≤x,y...

因为是全英题，所以题目的意思都是根据自己的英文水平去理解，可能不是原本的题目意思。望见谅。我英语差点挂科，被捞了。   A题 HDU - 4642  Alice and Bob are playing a kind of special game on an N*M board (N rows, M columns). At the beginning, there are N*M coins in this board with one in each grid and every coin may be upward or downward freely. Then they ta...

感想： 第一次进行现场的SCAU的排位赛。 昨天那场是OI赛制，实话讲很有熟悉感，感觉找回了曾经的状态。但是就是太过自信了，第一题写了单调栈，自信满满以为A掉了，但是有小失误WA掉了。然后那道写着入门的题目看着70%数据水了分就跑了，其实正解真的贼鸡儿简单。整场下来没有一道题是完全做出来的，都是水出来的，水了120分。本以为能水到200分的。 然后就开始为明天的ACM赛制烦恼了，如果真的一道题都做不出来，爆零了不就真的是个High5大学废物了吗？ 然后就是第二天的个人排位赛了。 其实还是所以题目看一遍，第一题想碰碰得到的规律对不对就秒交了，WA了，就看其他题目了。 感觉自己英文水平还...