本页面已浏览29次

1. Word Processor

奶牛Bessie正在完成她的写作课的一篇作文。由于她写字很难看,她决定用一个文字处理器来输入这篇作文。

这篇作文共有N个单词(\(1\le N\le 100\)),用空格分隔。每个单词的长度在1到15之间,仅由大写和小写字母组成。根据作业的要求,这篇作文需要用一种特别的方式排版:每一行包含的字符不超过K个(\(1\le K\le 80\)),空格不计。幸好 Bessie 的文字处理器能够处理这样的要求,它会按照如下的方式:

如果Bessie输入了一个单词,这个单词能够放进当前行,就放在当前行。

否则,将这个单词放到下一行,然后继续向下一行添加单词。

当然,同一行中的单词之间仍然用一个空格分隔。每一行的结尾都不应当有空格。

很不幸,Bessie 的文字处理器刚好坏了。请帮助她正确地排版她的作文!

输入格式(文件名:word.in):

输入的第一行包含两个空格分隔的整数N和K。

下一行包含N个单词,单词之间用单个空格分隔。所有单词的长度都不超过一行中的字符上限数K。

输出格式(文件名:word.out):

输出正确排版的 Bessie 的作文。

输入样例:

10 7
hello my name is Bessie and this is my essay

输出样例:

hello my
name is
Bessie
and this
is my
essay

第一行包含 7 个非空格字符,包括"hello"以及"my"。再加入"name"会使得第一行包含11>7个非空格字符,所以这个单词会被放到下一行。

分析

这道题难度不大。基本判定如下:

  1. 读入一个单词,并得到长度。
  2. 加上目前的行长度。
    1. 如果不超长,可以在本行输出。
    2. 如果超长,那就要换行输出。
  3. 重复1-2的过程。

同时,需要注意的是,根据题设,两个单词之间用空格分割,而且行尾不能用空格。因此在输出时,需要判定是否是第一个单词。

  1. 如果是第一个单词,那么原样输出。
  2. 否则,需要输出“(空格)单词”。

这样能保证题设要求。

答案

思考

本题很简单。需要注意的点已经在分析中列出。

2. Photoshoot

Farmer John在给他编号为\(1...N\)的N头奶牛排队拍照(\(2\le N\le 10^3\))。FJ一开始计划从左向右数第i个位置排编号为\(a_i\)的奶牛,他在一张纸上写下了排列\(a_1, a_2, ..., a_N\)。不幸的是,这张纸刚刚被Farmer Nhoj偷走了!

幸好FJ仍然有机会恢复他之前写下的排列。在这张纸被偷走之前,Bessie记录了序列\(b_1, b_2, ..., b_{N-1}\),对于每一个\(1\le i\le N\) 满足\(b_i=a_i+a_{i+1}\)

基于Bessie的信息,帮助FJ恢复可以产生序列b的“字典序最小”的排列a。排列x字典序小于排列y,如果对于某个j,对于所有i<j均有\(x_i=y_i\),且有\(x_j\lt y_j\)
(换句话说,这两个排列到某个位置之前都相同,在这个位置上x小于y)。保证存在至少一个满足条件的a

测试点性质:

测试点2-4满足\(N\le 8\)

测试点5-10没有额外限制。

输入格式(文件名:photo.in):

输入的第一行包含一个整数N。

第二行包含N−1个空格分隔的整数\(b_, b_2, ..., b_{N-1}\)

输出格式(文件名:photo.out):

输出一行,包含N个空格分隔的整数\(a_1, a_2, ..., a_{N-1}\)

输入样例:

5
4 6 7 6

输出样例:

3 1 5 2 4

a能够产生b,因为3+1=4,1+5=6,5+2=7,2+4=6。

分析

这道题也有两种做法。复杂度为\(O(N^2)\)的暴力法,以及复杂度为\(O(N)\)的分治法。

暴力法

暴力法的总体分析如下。

由题意可知,\(b[i-1]=a[i]+a[i-1] \to a[i]=a[i-1]+b[i-1]\),这是一个明确的递推关系,我们只要得到\(a[0]\),就可以得出所有的项。

那么我们不妨暴力搜索:\(a[0]\)从最小的值(1)开始,一个个地得到\(a[1], a[2]...\)。这是一个\(O(N)\)的过程。同时由于我们会不断地变动\(a[0]\)(从1到N),这也是一个\(O(N)\)的过程。总体的时间复杂度就达到了\(O(N^2)\)

另外,对于每次得到的一个序列\(a_i\),我们还要判断是不是不重复地也不遗漏地用完了这N个数。这种查重的工作用集合来处理是最好的。

分治法

分治的思路比较复杂,但想通了以后也是很直白的。

考虑如下的样本输入数据:

6
6 5 4 7 11

如果我们从\(a[0]=1\)开始试算,很快就会碰到问题:

第一次试算的时候,我们得到[1, 5, 0, 4, 3, 8]这样一个数列。直觉告诉我们,起步的1太小了,造成下一个数太大(但合理),再下一个数太小(而不合理)……如果我们能一次性调整好出发点,那么我们只要算一次(\(O(N)\))就能得到所有的值。这是我们后续算法的立足点。

一个重要的观察是:第0个数不会造成第1个数的问题,但可能造成第2个数的问题,以此类推;同样的,第1个数会造成3、5、7……这些数的问题。换句话说,偶数位只对偶数位传递着影响,奇数位只对奇数位传递着影响。这两种影响其实是一个,但影响的奇偶位数不会互相干扰。

另外,一个结论是:这些数中肯定会出现一个1。它可能出现在奇数位,也可能出现在偶数位,并都会传递影响。我们要避免的,是因为1的位置不恰当,而造成某些对应位置——如果1出现在奇数/偶数位,则某些奇数/偶数位——的数字出现问题(比如第i位的数字小于等于0)。我们要找出这些位置中最小的那个,让它至少等于1(加上一个正的“偏移量”)。这样一来,这些奇数/偶数位置(以及所有位置)的数字都是合理的了。有了这些数字,我们可以对应地求出其余偶数/奇数位的数字。

我们接下来就要看如何得到相隔为2的位置上,\(a[i-1]\)\(a[i+1]\)的差值。这个不难。

根据题意,\(b[i-1]=a[i]+a[i-1]\),我们可以得到:

\(\begin{cases}b[i-1]=a[i]+a[i-1] \\b[i]\space\space\space\space\space\space\space=a[i+1]+a[i] \end{cases}\space\space\space\to\space\space\space b[i]-b[i-1]=a[i+1]-a[i-1]\)

也就是说,\(a[i-1]\)\(a[i+1]\)的差值等于对应的\(b\)数组两个相邻值的差。(下图中的最后一行。)它规定了\(a\)中两两相邻的数字的差。

但是,这个差值不能帮我们决定偏移量。我们注意到,\(diff\)中求出的差值,在每次计算并影响相隔为2的过程中是累加的。所以我们可以用一个前缀和数组来记录累加的影响。注意,在求前缀和时,也要考虑奇偶位不干扰的特性。而这个数组中,对应的最小值就决定了“偏移量”。如果这个最小值是-1,那么我们知道,我们初始设定的1要至少等于2,才能保证这里至少为1\(1-(-1)\))。

综合考虑上述情况,我们分两种情况:1出现在偶数位;以及1出现在奇数位。

以下我们只分析1在偶数位的情况。

  1. 计算所有的\(diff\)\(pref\)数组。
  2. 找到最小的那个\(pref\)min)。
  3. 假设1在偶数位(不妨设定在\(a[0]\)),将\(a[0]改为\)1-min$。
  4. \(a[1]\)可求。
  5. 递推得到所有后续的数字:$a[i]=a[i-2]+diff[i]。

如果1在奇数位,那么上述过程中的1和2是相同的,不用重复计算,但在做第2步的时候,需要考虑下标起始范围(从0开始还是从1开始)。而3-5中,我们改为先求\(a[1]\),再求\(a[0]\)即可。

这样,我们得到两个可能的排列,分别对应1在偶数位和在奇数位。

接下来,我们只要判定这两个排列的正确性:不能重复不能漏。题目和数据保证这样的排列只有一个。我们输出合理的那个就是了。

答案

暴力法

分治法

思考

看出暴力法和分治法的差异了么?

暴力法的思路简单,代价是时间长;分治法需要进行深入的分析,找到规律,甚至需要“灵光一现”。这也是两种不同的编程思路:暴力法用的是试错法,一个一个地测试可能的答案;而分治法在分析完毕后,用的是构造法,构造出符合条件的排列——而这正是分治法速度快的原因。

3. Race

Bessie正在参加一场K(\(1\le K\le 10^9\))米的跑步比赛。她从0米每秒的速度开始比赛。在每一秒中,她可以选择将她的速度增加1米每秒,保持速度不变,或者将她的速度减少1米每秒。例如,在第一秒中,她可以将她的速度增加到1米每秒,跑1米,或者保持她的速度0米每秒不变,跑0米。Bessie 的速度不会降低到小于零。

Bessie始终朝着终点线的方向跑,她想要花费整数秒的时间完成比赛(在最后一秒的时候正好跑到终点或者超过终点1)。此外,她不想在终点时跑得太快:在Bessie跑完K米的时刻,她希望她的速度不超过X(\(1\le X\le 10^5\))米每秒。Bessie想要对于N(\(1\le N\le 1000\))个不同的X值知道她多快可以完成比赛。

测试点性质:

  • 测试点2-4满足\(N=X=1\)
  • 测试点5-10没有额外限制。

输入格式(文件名:race.in):

输入的第一行包含两个整数K和N。

以下N行每行包含一个整数X。

输出格式(文件名:race.out):

输出N行,每行包含一个整数,表示Bessie完成比赛时的速度小于或等于X的情况下跑完K米需要的最小时间。

输入样例:

10 5
1
2
3
4
5

输出样例:

6
5
5
4
4

\(X=1\)时,一种最优方案为:

  • 第1秒:将速度增加到1米/秒,跑1米
  • 第2秒:将速度增加到2米/秒,跑2米,总计跑3米
  • 第3秒:将速度保持在2米/秒,总计跑5米
  • 第4秒:将速度保持在2米/秒,总计跑7米
  • 第5秒:将速度保持在2米/秒,总计跑9米
  • 第6秒:将速度降低到1米/秒,总计跑10米

\(X=3\)时,一种最优方案为:

  • 第1秒:将速度增加到1米/秒,跑1米
  • 第2秒:将速度增加到2米/秒,总计跑3米
  • 第3秒:将速度增加到3米/秒,总计跑6米
  • 第4秒:将速度保持在3米/秒,总计跑9米
  • 第5秒:将速度保持在3米/秒,总计跑12米

注意当\(X=3\)时,以下方案是不合法的:

  • 第1秒:将速度增加到1米/秒,跑1米
  • 第2秒:将速度增加到2米/秒,总计跑3米
  • 第3秒:将速度增加到3米/秒,总计跑6米
  • 第4秒:将速度增加到4米/秒,总计跑10米

这是因为在Bessie跑完10米的时刻,她的速度是4米/秒。

分析

我们换个思路来思考:题目求的是满足条件的最短完赛时间。如果换个角度会如何:给定一个时间T,以及冲线的速度约束X,Bessie最多能跑出去多少米?

一些直观的结论:

  1. 比较好的跑法,肯定是在最后一秒的时候以X冲线。虽然可能多跑了一些距离,但减少了跑不到终点的风险。
  2. 一般而言,不断加速总是对的,甚至可以超过最终限速,这是为了在同样的时间里跑出更多的距离(反过来说,就是用更少的时间跑完固定的距离),但也因此,需要进行相应的减速。
  3. 引申一下:Bessie每有一秒钟“超速”,就有一秒“减速”。这样才能保证最终可以回到限速。这就有了一个“已经跑了的距离”和“还要跑的距离”的分别。
  4. 也因此:每次超速跑过一段距离,就要有另一次以相同的速度跑过同样的距离。
  5. 跑过的距离+没跑但必然要跑的距离,控制着总距离。如果这个距离超过了输入中规定的距离,就可以保证Bessie在这么多秒内完赛,并满足终点的限速条件。

用图来表示就是(以总共跑10米,终点限速1米/秒为例),Bessie需要6秒完赛:

答案

思考

这个解法充分利用了对称性:已经跑了的距离和还没跑的距离之间存在对称,也就是肯定有若干个这样的距离对,是用同样的速度跑完的。通过“同时”减去这些距离,可以很快地求出答案。


  1. 换句话说,Bessie在最后一秒结束后,总的距离可以超过\(K\)米。 

Previous Post Next Post