1
0bit 2013-04-12 16:43:59 +08:00
实现在哪里?
|
2
justfly OP |
3
longxi 2013-04-12 17:12:02 +08:00
|
4
wenbinwu 2013-04-12 17:25:03 +08:00
第一题就是考虑一开始那几种情况吧,剩下的ctrl a + ctrl c + ctrl v三个键效率肯定比aaa高,最后考虑下剩下1个或者2个键的情况
代码正确与否不知道 这样的注释嘛(#否则) 不要也罢 另外写英文的注释 |
5
binux 2013-04-12 17:29:19 +08:00
第一题这样暴力做肯定是不对的,假设之前已经输入了a个A了,那么再经过2+k次粘贴可以得到k*a个A
假设: M = F(n) 有: F(n) = max([F(n-2-k)*k for k in range(1, N)]+[n, ]) 当n<=0时: F(n) = 0 |
6
lddhbu 2013-04-12 17:35:27 +08:00
01背包
|
7
mingzhi 2013-04-12 17:43:44 +08:00
我觉得楼主的第一题好像是看错题目了吧。
Ctrl + a 这样 算2次吧 然后 n<=11 次 就是直接按a n>11 算 ((n-5)%6+5)^((n-(n-5)%6+5)/6) 不知道有没有错了。。 |
9
binux 2013-04-12 17:55:30 +08:00 1
第一题,python一行流:
F = lambda n: max([F(n-2-k)*k for k in range(1, n)]+[n, ]) if n > 0 else 0 后面的就懒得看了 |
10
lddhbu 2013-04-12 17:58:22 +08:00
好像比背包要简单,因为如果有“复制粘贴”,“复制粘贴”操作肯定是最后一步。
而如果N大于6,肯定会有“复制粘贴”,然后就可以递归了。 |
11
mingzhi 2013-04-12 18:06:06 +08:00
|
12
nkliwenjian 2013-04-12 18:13:06 +08:00
暂时没有详细研究,但是先提出来一个很严重的问题,就是单纯的(全选,拷贝,粘贴)的组合行为,实际上数量是完全没有增加的,因为粘贴的动作会覆盖掉原来的选择,并且光标会移动到最后,至少再粘贴一次才有效果。
|
13
wuma 2013-04-12 18:22:46 +08:00 1
第一个是个动态规划问题吧。第二个是正则+awk+sort。
|
14
awsx 2013-04-12 18:22:51 +08:00
现场笔的还是网络上提交?
|
15
wuma 2013-04-12 18:24:11 +08:00
n <=6 -> m=n
n>6 -> m(n) = Max (m(n-1)+p, m(n-2)+2p , m(n-3)*2) |
16
csx162 2013-04-12 18:32:46 +08:00
ctrl是可以一直按住的
全选的情况下是可以被覆盖的 |
17
hfeeki 2013-04-12 18:34:32 +08:00
第一个题目描述得太简单了,是不是只有出题人自己才能看懂呢?ctrl + A到底是算一个键呢?还是算是组合键?如果是组合键,那加上另两个组合键,全部的键的数目就是:A, C, V, ctrl。希望先讲清楚出题人到底啥意图
|
18
justfly OP |
20
justfly OP @lddhbu 没这么简单
比如十次按键: AAAA CTRL+A CTRL+C CTRL+V CTRL+V CTRL+V CTRL+V (20个A) AAAA CTRL+A CTRL+C CTRL+V CTRL+A CTRL+C CTRL+V(16个A) |
21
Muninn 2013-04-12 19:29:36 +08:00
哈哈 看来最难的是怎么理解第一题
|
22
nkliwenjian 2013-04-12 19:41:52 +08:00
动态规划我是没有学过了,但是很多时候一眼看上去的东西会有点误差。我简单的手算了一下,过程如下:
f(n + (a,c,v,v)) = f(n) * 2 f(n + (a,c,v,v,v)) = f(n) * 3 f(n + (a,c,v,v,v,v)) = f(n) * 4 f(n + (a,c,v,v,v,v,v)) = f(n) * 5 ...... f(n+4) = f(n) * 2 f(n+5) = f(n) * 3 f(n+6) = f(n) * 4 f(n+7) = f(n) * 5 f(n+k) = f(n) * (k - 2) f(n+8) = f(n) * 6, f(n+4+4) = f(n) * 2 * 2 f(n+9) = f(n) * 7, f(n+5+4) = f(n) * 3 * 2 f(n+10) = f(n) * 8, f(n+6+4) = f(n) * 4 * 2, f(n+5+5) = f(n) * 3 * 3 f(n+11) = f(n) * 9, f(n+7+4) = f(n) * 5 * 2, f(n+6+5) = f(n) * 4 * 3 f(n+12) = f(n) * 10, f(n+8+4) = f(n) * 6 * 2, f(n+6*6) = f(n) * 4 * 4, f(n+4+4+4) = f(n) * 2 * 2 * 2 f(n+16) = f(n) * 14, f(n+12+4) = f(n) * 10 * 2, f(n+8+8) = f(n) * 6 * 6, f(n+4+4+4+4) = f(n) * 2 * 2 * 2 * 2 我们知道指数函数是增长速度最快的函数,所以到此其实大概能得出结论,如果我们把k进行不同的组合拆分的话,大概会是这样的一个结果: 2 ^ (k / 4) = 2 ^ (0.25 * k) 3 ^ (k / 5) = 2 ^ (0.317 * k) 4 ^ (k / 6) = 2 ^ (0.333 * k) 5 ^ (k / 7) = 2 ^ (0.332 * k) 6 ^ (k / 8) = 2 ^ (0.323 * k) k / 6的时候取得最大值,有兴趣可以算一下验证一下,基本上就是底下的公式变形推导: a ^ (k / (a + 2)) = 2 ^ (lg(a) / lg(2)) ^ (k / (a + 2)) 2 ^ (k / lg(2) * (lg(a) / (a + 2)) 所以,当n足够大时,尽量多的按照这个a+c+v+v+v+v的组合来操作,结果是最大的。剩下的部分就是n从多少开始满足这个规则,以及6的组合余下的余数放哪,这个就不推算了。 有错误莫怪哦。 |
23
qdcanyun 2013-04-12 21:22:19 +08:00
第一题 很简单的动态规划
分为3个原子操作: “A” “Press Ctrl+A;Press Ctrl+C;Press Ctrl+V;Press Ctrl+V;” "Press Ctrl+V;" 当前敲击按键x的次数的最大值为(list[x-1]+1, list[x-4] * 2, list[x-1]+copy_clipboard_num)里的最大值 当 list[x-4] * 2 与 list[x-1]+copy_clipboard_num 相等时 优先使用 list[x-4] * 2 ,这样在步数相同的情况下可以扩大clipboard 其实分析一下就可以看出PressA这种情况在第8次敲键盘之后不会出现, 也可以初始化前八次按键的状态, 然后只采用2种原子操作 代码 http://gist.github.com/5371878 |
24
qdcanyun 2013-04-12 21:23:42 +08:00
输出步骤的时候从后往前找出来就行
|
25
MayLava 2013-04-12 21:42:07 +08:00
研究了半天状态,结果还是用5分钟写个搜索……orz……
效率不高,n=46时约用时1s 简单的三种操作,1、按A;2、按C-v;3、按C-a,C-c,C-v,C-v 简单的剪枝:如果Clipboard大于1则不按A;反之则按A。 http://gist.github.com/MayLava/5372068 |
26
MayLava 2013-04-12 21:48:10 +08:00
|
27
nkliwenjian 2013-04-12 23:07:43 +08:00
@justfly 1秒钟之内循环1到49毫无压力。注意我前面说的,全选复制粘贴是不会变多的,至少粘贴两次才会多出来一次,所以结果会跟你的不一样。当n=11的时候,m=20。而不是n=10。
SELECT_ALL = 'CTRL+A' COPY = 'CTRL+C' PASTE = 'CTRL+V' PRESS_GROUP = [SELECT_ALL, COPY, PASTE, PASTE, PASTE, PASTE] A4 = ['A', 'A', 'A', 'A'] def f(n): press_left = n press_keys = [] total = 0 group_count = 0 if n <= 7: return (n, ['A'] * n) elif n == 8: return (9, [['A', 'A', 'A'], [SELECT_ALL, COPY, PASTE, PASTE, PASTE]]) elif n == 9: return (12, [['A', 'A', 'A', 'A'], [SELECT_ALL, COPY, PASTE, PASTE, PASTE]]) else: press_a4(press_keys) press_left = press_left - 4 group_count = press_group(press_left, press_keys) press_left = press_left - 6 * group_count allot_left(press_left, press_keys) total = calculate_total(press_keys) return (total, press_keys) def press_a4(press_keys): press_keys.append(A4) def press_group(press_left, press_keys): group_count = press_left / 6 for i in range(group_count): press_keys.append(PRESS_GROUP) return group_count def allot_left(press_left, press_keys): if len(press_keys) == 2: a_count = press_left / 2 v_count = press_left - a_count for i in range(a_count): press_keys[0].append('A') for i in range(v_count): press_keys[1].append(PASTE) else: left = press_left index = len(press_keys) - 1 while left > 0: left = left - 1 press_keys[index].append(PASTE) index = index - 1 if index == 0: index = len(press_keys) - 1 def calculate_total(press_keys): total = len(press_keys[0]) for l in press_keys[1:]: total = total * (len(l) - 2) return total def main(): for i in range(1, 50): print 'n=%d, m=%d' % (i, f(i)[0]) if __name__ == "__main__": main() |
28
nkliwenjian 2013-04-12 23:28:00 +08:00
@justfly 一点小bug,请把press_keys.append(A4)改成press_keys.append(copy.copy(A4)),把press_keys.append(PRESS_GROUP)改成press_keys.append(copy.copy(PRESS_GROUP))
|
29
jesse_luo 2013-04-14 01:40:50 +08:00
第一题是动态规划吧……归纳下可以得出递推式:
m=f(x)= 1(x=1) f(x-1)+1 f(x-3)*2 f(x-1)+Clickboard |
31
dndx 2013-04-14 02:01:45 +08:00
歪下楼
[I 130403 17:26:40] 1 200 GET /question/123 (8.8.9.9) 200.39ms [I 130403 17:26:90] 1 200 GET /topic/456 (8.8.9.9) 300.85ms [I 130403 17:26:90] 1 200 POST /answer/789 (8.8.9.9) 300.85ms 公司是知乎,鉴定完毕。 |
32
sethverlo 2013-04-24 13:25:18 +08:00
|
33
rrfeng 2013-04-24 14:13:00 +08:00
第二题题意不是很明确……
不过用 awk 直接实现很容易的呀。用三个键计数: 1. awk '/GET \/topic/{id[$4]++;topic[$7]++;it[$4" "$7]++}' 2. END 里面判断: {for(x in id){if(id[x]>2)print x}} 访问 /topic 大于2次的用户列表 {for(y in it){if(it[y]>2)print y}} 同一个用户访问了2次以上不同 /topic 地址的列表 id /topic/*** 真的没看懂题目的要求 [用户列表] :访问了 2个不同的 /topic 并且这几个topic 均重复访问了 2次? 不过三个哈希组合判断足够了,awk 后面直接跟所有文件的列表一次搞定~~ |
34
rrfeng 2013-04-24 14:13:40 +08:00
python 的话……好长。
|
35
sailxjx 2013-04-24 16:23:45 +08:00
|
36
zhangxi1989 2013-04-25 15:58:21 +08:00
这个结果对不对?
/* 括号里表示一开始输入几个0 0:0(0) 1:1(1) 2:2(2) 3:3(3) 4:4(4) 5:5(5) 6:6(6) 7:9(3) 8:12(3) 9:16(4) 10:20(4) 11:25(5) 12:36(3) 13:48(3) 14:64(4) 15:80(4) 16:100(5) 17:144(3) 18:192(3) 19:256(4) 20:320(4) 21:400(5) 22:576(3) 23:768(3) 24:1024(4) 25:1280(4) 26:1600(5) 2304(3) 3072(3) 4096(4) */ |