分治算法

TimeLimit:1000MS  MemoryLimit:128MB
64-bit integer IO format:%lld
未提交 | 登录后收藏 | 已有3人收藏了本题
Problem Description
在处理问题的时候,有时可以将问题划分成2个子问题处理。而子问题又可以继续划分成2个更小的子问题。
例如,在处理一个长度为n的串时,我们可以先处理1~n/2 和 n/2+1~n 这两部分。
在处理区间[a,b]时,先处理区间[a,(a+b)/2],处理完后再处理区间[(a+b)/2+1,b]。
在处理这两部分时,又可以继续划分。直到划分出的区间长度为1,长度为1的区间可以直接处理结束。
所以在处理 [1,3]时,要分解成[1,2]和[3,3]。先处理[1,2],就要分别处理1和2,处理完1和2,[1,2]区间就处理完成了,然后处理3,那么[1,3]区间处理完成。

现在在已知要处理的串长度为n
那么你能描述出处理的过程吗?
Input
多组测试数据,每组数据只有一个数字n(n<=1000)
Output
每组测试数据输出格式如下:
每行的输出有3种情况
1、表示开始处理长度超过1的区间[a,b],输出格式:ready a b
2、表示处理单个元素a,输出格式:do a
3、表示处理完了一个长度超过1的区间[a,b],输出格式:done a b
每两组测试数据之间用一个空行隔开
SampleInput
1
4
5
SampleOutput
do 1

ready 1 4
ready 1 2
do 1
do 2
done 1 2
ready 3 4
do 3
do 4
done 3 4
done 1 4

ready 1 5
ready 1 3
ready 1 2
do 1
do 2
done 1 2
do 3
done 1 3
ready 4 5
do 4
do 5
done 4 5
done 1 5
Submit
题目统计信息详细
总AC数138
通过人数118
尝试人数121
总提交量233
AC率50.64%
AC该题后可以添加标签
贴完标签可以获得20ACB。
并且可以获得本题所有提交代码查看权限。
点击标题可以显示标签。
如果你还没认真思考过这题,请不要查看标签
如果您已经通过了该题,请务为该题贴上标签

T^T Online Judge

[BUG反馈] [FAQ] [闽ICP备17026590号-1]
当前版本:3.24 系统时间: