本页面已浏览36次
Farmer John最近购入了N头新的奶牛(\(3\le N\le 5×10^5\)),每头奶牛的品种是更赛牛(Guernsey)或荷斯坦牛(Holstein)之一。
奶牛目前排成一排,Farmer John想要为每个连续不少于三头奶牛的序列拍摄一张照片。 然而,他不想拍摄这样的照片,其中只有一头牛的品种是更赛牛,或者只有一头牛的品种是荷斯坦牛——他认为这头奇特的牛会感到孤立和不自然。在为每个连续不少于三头奶牛的序列拍摄了一张照片后,他把所有「孤独的」照片,即其中只有一头更赛牛或荷斯坦奶牛的照片,都扔掉了。
给定奶牛的排列方式,请帮助Farmer John求出他会扔掉多少张孤独的照片。如果两张照片以不同的奶牛开始或结束,则认为它们是不同的。
输入格式(从终端 / 标准输入读入):
输入的第一行包含N。
输入的第二行包含一个长为N的字符串。如果队伍中的第
i
头奶牛是更赛牛,则字符串的第i
个字符为G。否则,第i
头奶牛是荷斯坦牛,该字符为H。
输出格式(输出至终端 / 标准输出):
输出Farmer John会扔掉的孤独的照片数量。
输入样例:
5
GHGHG
输出样例:
3
这个例子中的每一个长为3的子串均恰好包含一头更赛牛或荷斯坦牛——所以这些子串表示孤独的照片,并会被Farmer John扔掉。所有更长的子串(GHGH、HGHG 和 GHGHG)都可以被接受。
这道题的要求很简单,解析成数学语言就是:对于一个长度\(\ge 3\)的字符串,判定是不是只有一个G或者只有一个H。
最直接的解法,是按照这个思路去一个一个检查。符合条件的字符串有\(N^2\)个,而每次检查需要遍历子串(\(O(N)\))。因此,最终的时间复杂度来到了\(O(N^3)\)。
一个改进的方式,可以让时间复杂度降到\(O(N^2)\):我们每次固定子串中最左边的字符,然后一个一个向右找。如果我们找了至少3个字符,而且其中只有一个G或者一个H,那这张照片就是要被扔掉的(计数加1)。我们一个一个地改变最左边字符(向右走),最后就能得到结果。
相比USACO给出的答案,我们进行了一次优化(39-42行):如果G和H的数量都\(\ge 2\),那么可以保证的是:没有哪种牛是“孤单”的,而且照片中的牛的数量一定超过了3。后续不论如何,这些照片都不会被删除,因此我们可以跳出内循环了。这样虽然没能降低时间复杂度,但至少可以优化一部分。这样的小修补,也是一种成就。
还有没有更省时间的方式?
我们来看下所谓“孤独”的牛出现时,是怎样的情况。先从3头牛开始,下图中,H牛是孤独的:
再扩展到多头牛的情况:
... | G | G | G | H | G | G | G | G | ... |
中间的这头H牛(假定是s[i]
)显然很“孤独”。
s[i-1]!=s[i]
,所以左计数(lhs
)要加1。k
从i-2
开始往左,所有的s[k]==s[i-1]
,lhs
加1。s[i]
,向左计算与s[i]
不同的字符s[i-1]
的最大连续长度。lhs
是这个长度。向右看的情形类似。这两个过程结束后,我们分别得到了lhs
和rhs
。考虑不同的组合的情况(还是以上图为例,孤独的牛是H):
lhs
头G,右边有rhs
头G,这样的组合有\(lhs*rhs\)种。lhs-1
种。rhs-1
种。注意,2/3两种情况要考虑lhs
和rhs
是1的情况,这时是不构成单边“孤独”的情形的。
最后的代码如下,请大家注意循环的终止和各自情形下的判定。
USACO声称,这个算法的复杂度是\(O(N)\)。但我们似乎看到了两个循环,这是怎么回事?
我请教了ChatGPT-4o,它一开始也认为是\(O(N^2)\)的复杂度,经过进一步提示后,它的分析如下。
==============
即使一个字符串只包含'H'和'G',我们对于每个字符只检查它的“紧邻”,而且这是一个线性扫描收敛于\(O(N)\)。
===============
这给了我们一个重要的提示:不是光看for
循环就能确定时间复杂度的,在这个例子中,最终的复杂度还是收敛到了\(O(N)\)。
Farmer John的N头奶牛对他们牛棚的室温非常挑剔。有些奶牛喜欢温度低一些,而有些奶牛则喜欢温度高一些。
Farmer John的牛棚包含一排N个牛栏,编号为\(1...N\),每个牛栏里有一头牛。 第i
头奶牛希望她的牛栏中的温度是\(p_i\),而现在她的牛栏中的温度是\(t_i\)。为了确保每头奶牛都感到舒适,Farmer John安装了一个新的空调系统。该系统进行控制的方式非常有趣,他可以向系统发送命令,告诉它将一组连续的牛栏内的温度升高或降低1个单位——例如“将牛栏5…8的温度升高1个单位”。一组连续的牛栏最短可以仅包含一个牛栏。
请帮助 Farmer John求出他需要向新的空调系统发送的命令的最小数量,使得每头奶牛的牛栏都处于其中的奶牛的理想温度。
输入格式(从终端 / 标准输入读入):
输入的第一行包含N。下一行包含N个非负整数\(p_1...p_N\),用空格分隔。最后一行包含N个非负整数\(t_1...t_N\)。
输出格式(输出至终端 / 标准输出):
输出一个整数,为Farmer John需要使用的最小指令数量。
输入样例:
5
1 5 3 3 4
1 2 2 2 1
输出样例:
5
一组最优的 Farmer John 可以使用的指令如下:
初始温度 :1 2 2 2 1
升高牛棚 2..5:1 3 3 3 2
升高牛棚 2..5:1 4 4 4 3
升高牛棚 2..5:1 5 5 5 4
降低牛棚 3..4:1 5 4 4 4
降低牛棚 3..4:1 5 3 3 4
这道题一共有两种解法。我们一个一个地分析。
作为一个预备工作,我们创建另外一个数组d
,用来存放每一头当前牛棚温度和理想温度的差(\(p_i-t_i\))。我们的目的当然是所有d
里的元素都是0。
注意,我们对一个区间的牛棚调整一次(温度变化1)的时候,所有的d
也会被调整一次。
首先是最直观的方法。
直觉告诉我们,要想调整次数最小,有一些原则:d
为0的时候,我们不调整;d
是正/负的时候,我们也不去升高/降低温度。
问题进一步简化到:对于某个特定的d[N]
,那么我们要找到最小的一个j
使得\([j, N]\)之间的所有的d
和这个特定的d[N]
同号。然后进行一次调整(计数加1)。
这个动作可以执行很多次,直到d[N]
为零。那么我们进入下一个牛棚,并重复上述操作。
上述这个方案的复杂度是\(P(NV)\),其中的V
是d
中可能的最大值。根据题目,“温度值不超过10,000”,牛不超过100,000。这个数据量还是很大的。我们需要优化。
一个不改变复杂度的方法是,我们不用每次计算的时候,都只有1度。我们可以直接计算要调几度——这不是FJ的机器能做到的,但我们在模拟的时候可以这么做。
整体思路是:
d
,满足:这些d
不为0,而且和d[N]
同号。d
中的最小值,这就是要调整的度数(也就是次数)。这个做法不能降低复杂度,但可以显著降低计算量。
让我们深入分析,将复杂度降低到\(O(N)\)!
我们已经得到了数组d
,并用它记录一个差值:当前温度和理想温度的差。这个差值决定了调整的次数。
我们再来分析一下d
。对于d[i]
和d[i+1]
,如果它们相等,意味着如果我们对d[i]
做任何操作,都必须对d[i+1]
也做一次。这样可以更快地让d[i]
和d[i+1]
同时归零。而如果两者差距极大,意味着,对d[i]
或者d[i+1]
之一(但不是两者)至少需要做abs(d[i]-d[i+1])
次操作。
我们令e[i]=abs(d[i+1]-d[i])
,我们还可以观察到如下事实:
也就是对于[i, j]
这个范围中的d
做了一次调整后,只有e[i-1]
和e[j]
变化了1(总共变化了2)。当中的e
值没有变。
所以,最少的次数可以用公式快速获得:\(\sum_{i=0}^N e_i/2\)
也就是数组e
的和的一半。
于是,编程反而简单了。
一个模拟题,变成了数学公式!这不是“差分”唯一出现的场合。
在网上搜索“差分在编程中的应用”,可以找到很多有用的资料。比如这一篇。我摘录部分内容如下。
差分是一种和前缀和相对的策略,可以当做是求和的逆运算。差分,一般在大数据里用在以时间为统计维度的分析中,其实就是下一个数值 ,减去上一个数值 。当间距相等时,用下一个数值,减去上一个数值 ,就叫“一阶差分”,做两次相同的动作,即再在一阶差分的基础上用后一个数值再减上一个数值一次,就叫“二阶差分"。
差分是求前缀和的逆操作1,类似于数学中的求导和积分,对于原数组a[n]
,构造出一个数组b[n]
,使a[n]
为b[n]
的前缀和。一般用于快速对整个数组进行操作,比如对将a
数组中[l,r]
部分的数据全部加上c
。使用暴力方法的话,时间复杂至少为O(n)
,而使用差分算法可以将时间复杂度降低到O(1)
。
请特别注意上面的“将时间复杂度降低到O(1)
”。这就是我们使用差分解题的出发点和得到的好处。
差分可以用物理概念来映射:
有兴趣的同学可以去阅读这篇文章。
奶牛Bessie正准备从她最喜爱的草地回到她的牛棚。
农场位于一个\(N×N\) 的方阵上(\(2\le N\le 50\)),其中她的草地在左上角,牛棚在右下角。Bessie 想要尽快回家,所以她只会向下或向右走。有些地方有草堆(haybale),Bessie无法穿过;她必须绕过它们。
Bessie今天感到有些疲倦,所以她希望改变她的行走方向至多K
次(\(1\le K\le 3\))。
Bessie有多少条不同的从她最爱的草地回到牛棚的路线?如果一条路线中Bessie经过了某个方格而另一条路线中没有,则认为这两条路线不同。
输入格式(从终端 / 标准输入读入):
每个测试用例的输入包含
T
个子测试用例,每个子测试用例描述了一个不同的农场,并且必须全部回答正确才能通过整个测试用例。输入的第一行包含T
(\(1\le T\le 50\))。每一个子测试用例如下。每个子测试用例的第一行包含
N
和K
。以下
N
行每行包含一个长为N
的字符串。每个字符为.
,如果这一格是空的,或H
,如果这一格中有草堆。输入保证农场的左上角和右下角没有草堆。
输出格式(输出至终端 / 标准输出):
输出
T
行,第i
行包含在第i
个子测试用例中Bessie可以选择的不同的路线数量。
输入样例:
7
3 1
...
...
...
3 2
...
...
...
3 3
...
...
...
3 3
...
.H.
...
3 2
.HH
HHH
HH.
3 3
.H.
H..
...
4 3
...H
.H..
....
H...
输出样例:
2
4
6
2
0
0
6
样例给出了很好的提示:我们应该从简单(\(K=1\))到复杂(\(K=3\))地处理这个问题。
\(K=1\)
如果Bessie只想转一次弯就到家,只有一种可能:从左上角开始,要么它向右走到底,然后向下走到底到家(右下角);或者,它向下走到底,然后向右走到底到家。如图:
如果这两个路径上有任何格子是H
,那么就走不通。否则走法加1。所以,问题归并为判定第一行、第一列、最后一行、最后一列上格子的状态。
for (int i = 0; i < n; i++)
{
if (g[0][i] == 'H' || g[i][n - 1] == 'H') //第一行和最后一列
{
urcorner = false;
}
if (g[i][0] == 'H' || g[n - 1][i] == 'H') //第一列和最后一行
{
dlcorner = false;
}
}
\(K=2\)
首先,要考虑\(K=1\)的情况,因为只转一次弯的路径是符合\(K=2\)的约束的。
如果转两次弯,会是怎样的路径呢?
Bessie也只有两种走法:
这就是对每一列(第一种走法)或者每一行(第二种走法)进行搜索和判定的过程。
以“右下右”(上图中的绿线)的走法为例:
j
)从第二列到最后第二列:
i
),进行判定:
g[i][j]
是草堆:不行;图中另外一种走法(红线,“下右下”)的分析请自行完成。
\(K=3\)
首先,要考虑\(K=1\)和\(K=2\)的情况。
Bessie转三次向的走法如下图所示:
换句话说,也就是Bessie在中途要多转一次弯。我们对此可以进行与\(K=2\)时类似但扩展的判定。以“右下右下”(上图中绿线)的走法为例:
(i, j)
,除了判定本身是否是草堆外,需要判定四个方向的草堆情况:
“下右下右”(红线)走法分析类似,请自行完成。
这个题目难度还是适中的。同时,解法的复杂度是\(O(N^3)\):搜索路径是一个\(O(N^2)\)的过程,而每个路径都要进行格子的判定(\(O(N)\))。
有关前缀和,在分析相关试题时再讲。 ↩