| 题目名称 | 663. [USACO Feb12] Moo游戏 |
|---|---|
| 输入输出 | moo.in/out |
| 难度等级 | ★ |
| 时间限制 | 1000 ms (1 s) |
| 内存限制 | 128 MiB |
| 测试数据 | 10 |
| 题目来源 |
 Makazeu
于2012-03-29加入 |
| 开放分组 | 全部用户 |
| 提交状态 | |
| 分类标签 | |
| 分享题解 |
| 通过：28， 提交：59， 通过率：47.46% | ||||
 龙征天 |
100 | 0.000 s | 0.00 MiB | C++ |
 Youngsc |
100 | 0.000 s | 0.00 MiB | C++ |
 father |
100 | 0.001 s | 0.32 MiB | C++ |
 习小小 |
100 | 0.002 s | 0.30 MiB | C++ |
|
习小小 |
100 | 0.002 s | 0.30 MiB | C++ |
|
习小小 |
100 | 0.002 s | 0.30 MiB | C++ |
|
习小小 |
100 | 0.002 s | 0.30 MiB | C++ |
 烟雨 |
100 | 0.002 s | 0.31 MiB | C++ |
 Lovelove_boii |
100 | 0.002 s | 0.31 MiB | C++ |
 sqyon |
100 | 0.002 s | 0.31 MiB | C++ |
| 关于 Moo游戏 的近10条评论(全部评论) | ||||
|---|---|---|---|---|
|
回复 @QhelDIV :
正解  徐驰
2017-10-04 15:17
3楼
| ||||
|
楼上正解。
 Makazeu
2012-08-07 17:18
2楼
| ||||
|
无限切割
f[i]表示第i个串有多长 找到长度最小大于N那个串 将它分成3份 ...(1)moo..oo(2)....(3) (1)和(3)相同,判断如果f[i-1]<=N<=f[i]-f[i-1] 即N在中间(2) 这样就可以直接输出了 否则递归找下去 根据题目性质可得N只可能在我们找到的第i个串的(2)或者(3) 所以让再找到最短的比(N-f[i]+f[i-1])长的串j,重复上述步骤 如果递归到了S0,直接输出即可  QhelDIV
2012-06-19 09:43
1楼
| ||||
USACO Contest Feb2012 Bronze
Problem 3. Moo Moo游戏
Translated by Freddy
奶牛们迷上了一个名为“Moo”的新的单词游戏。
在玩该游戏时，奶牛们站成长长的一排，在队列中的每一头
奶牛都有责任尽可能快的大声说出一个特定的字母。
在Moo游戏中，这个单词序列严格上说是无穷的，它是这样开始的：
m o o m o o o m o o m o o o o m o o m o o o m o o m o o o o o
这一串最好由递归表示：令S(0)为三个字符的序列“moo”
那么更长的字符串S(k)由三部分组成，第一部分是S(k-1)，第二部分是”m o…o”(k+2个’o')，第三部分又是S(k-1)。例如：
S(0)=”m o o”
S(1)=”m o o m o o o m o o”
S(2)=”m o o m o o o m o o m o o o o m o o m o o o m o o”
正如你所看到的，这个过程最终将会产生一个无穷的长字符串，并且
这个长字符串正是被玩Moo游戏的奶牛一个一个说出。
Bessie这头奶牛，自我感觉很聪明，他想要预测第N头奶牛将会说出m还是o。请你帮助他！
输入：
一个正整数N(N<=10^9)
输出 :
输出文件只有一行，包含一个字符，“o”或者“m”
输入样例：
11
输出样例：
m