查看: 2622|回复: 15
收起左侧

Zach(1) 刷屏问题

|只看干货 |刷题

分享帖子到朋友圈
zach | 显示全部楼层 |阅读模式
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   91% (2307)
 
 
8% (228)    👎

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?注册账号

x
我们经常想刷屏,比如打100个“顶” like this
LZ威武啊!
顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶

我们一般是先打几个顶,然后复制粘贴若干次。

那么,连续输入n个“顶”最少需要多少次按键呢?连续输入至少n个“顶”,最少需要多少次按键呢?

注:输入一个“顶”视为一次按键,复制一次视为一次按键,粘贴一次视为一次按键。

上一篇:Ananimous(3) 求m个字符串中重复n次字符串的最长的那个
下一篇:Microsoft(3) 最长重复子串
K姐 2011-4-21 06:55:37 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   94% (10530)
 
 
5% (571)    👎
ctrl + A doesn't count as a key stroke?
回复

使用道具 举报

K姐 2011-4-21 07:00:02 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   94% (10530)
 
 
5% (571)    👎
does it have to be exactly 100, or > 100 is also ok?
回复

使用道具 举报

K姐 2011-4-21 07:00:05 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   94% (10530)
 
 
5% (571)    👎
does it have to be exactly 100, or > 100 is also ok?
回复

使用道具 举报

Imbalism 2011-4-21 07:19:43 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (42)
 
 
0% (0)    👎
本帖最后由 Imbalism 于 2011-4-21 08:30 编辑

int getMin(n)
{
    if(n <= 4)
        return n;
    return getMin(floor(sqrt(n))) + getMin(n - floor(sqrt(n)) * floor(sqrt(n)));
}

不知道对不对
回复

使用道具 举报

darksteel 2011-4-21 07:36:16 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (32)
 
 
0% (0)    👎
回复 5# Imbalism
为什么min和max都只有一个实参?

另外说说我的想法,严格等于n的情况用n^2的dp应该能出来,不知道能不能更好。至少n的情况,递推一下i次操作所能产生的最大数目就行,考虑到这个基本是指数增长的,可以认为logn就能出来

   
回复

使用道具 举报

darksteel 2011-4-21 07:46:30 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (32)
 
 
0% (0)    👎
想用i次操作弄出尽可能多的“顶”,策略是先直接输入几次,i为奇数则先输入3次,i为偶数则先输入两次,然后用剩下的操作不断翻倍。这样如果能把公式写出来的话,第二问可能O(1)就能出来。当然必须把取log的代价看做常数
回复

使用道具 举报

 楼主| zach 2011-4-21 07:48:03 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   91% (2307)
 
 
8% (228)    👎
1. ctrl + A doesn't count as a key stroke?
2. does it have to be exactly 100, or > 100 is also ok?

小K 发表于 2011-4-20 18:00

1. 全选和输入一个字,和复制,和粘贴一样,都算一次
2. 我说了,有两问嘛。
    (1)连续输入n个“顶”最少需要多少次按键呢?
    (2)连续输入至少n个“顶”,最少需要多少次按键呢?
回复

使用道具 举报

 楼主| zach 2011-4-21 07:49:13 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   91% (2307)
 
 
8% (228)    👎
回复  Imbalism
为什么min和max都只有一个实参?

另外说说我的想法,严格等于n的情况用n^2的dp应该能出 ...

darksteel 发表于 2011-4-20 18:36

Yep. I guess it's a typical DP problem
回复

使用道具 举报

darksteel 2011-4-21 07:53:26 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (32)
 
 
0% (0)    👎
本帖最后由 darksteel 于 2011-4-21 07:54 编辑

回复 9# zach
但我刚才又想了下,似乎可以复制任意长度破坏了这一点。这样除了小于等于4的特殊情况需要处理
下,其它的最后一步肯定由复制得到。如果第二问算出来了,第一问是完全一样的结果,因为完全可以在在最后一次复制的时候少复制一些而得到正好n个。我觉得如果改成每次复制只能翻倍,大概就得用dp了。


   
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 注册账号

本版积分规则

隐私提醒:
■拉群请前往同学同事飞友|拉群结伴版块,其他版块拉群,帖子会被自动删除
■论坛不能删帖,为防止被骚扰甚至人肉,不要公开留微信等联系方式,请以论坛私信方式发送。
■特定版块可以超级匿名:https://tools.1point3acres.com/thread
■其他版块匿名方法:http://www.1point3acres.com/bbs/thread-405991-1-1.html

>
快速回复 返回顶部 返回列表