作者LPH66 ((short)(-15074))
看板puzzle
标题[中译] PuzzleUp 2009 (5) Pattern
时间Wed Aug 19 20:31:53 2009
首页：
http://www.puzzleup.com/2009/?home
时限：2009/08/20（四）19:00～08/26（三）18:59
答案可上传５次，但每改１次扣２０分（基本分为１００分）
在比赛期间内可随时回答，但只有在时限内回答者有额外加分
◆Pattern
在一个５Ｘ５的格子里任意涂黑三格共有几种涂法？
注意：若一个涂法可以由另一个涂法经旋转(且不镜射)而得到，
则两者就认为是相同的涂法。
--
'Oh, Harry, dont't you
see?' Hermione breathed. 'If she could have done
one thing to make
absolutely sure that every single person in this school
will read your interview, it was
banning it!'
---'Harry Potter and the order of the phoenix', P513
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 140.112.30.84
1F：→ LPH66:就不等帕索大了 自己先贴 XD (其实是解的差不多了...(逃 08/19 20:32
※ 编辑: LPH66 来自: 140.112.30.84 (08/19 20:33)
2F：推 northkk:如果题目是 4x4 或 6x6 的格子会比较简单... 08/19 20:57
3F：→ northkk:题目长得就是一付有陷阱的脸... 08/19 20:58
4F：推 xphacker:只用乘跟除的答案会对吗 08/19 21:09
5F：推 northkk:不晓得耶, 我在想有没有解法是可以用到开根号的....:P 08/19 21:17
6F：推 werul:5*5的关键就是中间这格 08/19 21:27
7F：推 northkk:没错, 陷阱脸.... 08/19 21:30
8F：推 ars1an:同意，掌握关键後剩下的就是排列组合啦 08/19 23:34
9F：→ ars1an:怎麽用根号解我也想不到… :P 08/19 23:35
10F：推 puzzlez:算完之後，我得到一个惊人的结果…… 08/20 08:25
11F：推 xphacker:什麽!! Σ(⊙▽⊙"a 08/20 08:39
12F：→ xphacker:咦!闲聊区不见了 08/20 08:42
13F：推 FACE90006:哇呜~这样就不能玩帕索了ＱＱ。。。 08/20 20:29
14F：推 JimAbbott:他故意的 08/20 20:40
15F：推 FACE90006:帕索大真残忍...唯一的乐趣也被硬生生地剥夺ＱＱ。。。 08/20 20:49
16F：推 xphacker:为了这题 我翻出了尘封以久的五子棋来排 08/20 20:50
17F：推 werul:要牌很久喔 08/20 21:01
18F：推 puzzlez:只排三阶就很快...而且会发现一件奇怪的事... 08/20 21:36
19F：推 xphacker:也是只排3 冥冥中有个巧合....难不成... 08/20 21:42
20F：推 puzzlez:只要确定是21或22 我就能确定5阶的答案了... 08/20 21:43
21F：推 puzzlez:嗯 是22种 我能确定5阶的答案了！ 08/20 21:55
22F：推 puzzlez:22种是3阶的答案...别误会了....... 08/20 21:56
23F：推 northkk:我可以确定1阶的答案是0种.... 08/20 22:03
24F：→ northkk:提供大家做参考.. 08/20 22:03
25F：推 xphacker:2阶是1种 肯定! 08/20 22:10
26F：推 puzzlez:我经过2天不眠不休，再用微积分，终於算出4阶有140种... 08/20 22:13
27F：推 puzzlez:解数列 0, 1, 22, 140, ? 天啊...这个提示真大..... 08/20 22:15
28F：推 xphacker:不眠不休 0口0"" 08/20 22:23
29F：推 turing:这不是应该用5x5格子中涂1个格子有几种、涂两个格子有几种 08/20 22:34
30F：→ turing:进而算出涂三个格子有几种？ 08/20 22:35
31F：推 puzzlez:楼上一语惊醒梦中人！我本来还想用线性回归法去分析说.... 08/20 23:14
32F：推 werul:有尾数@@ 08/21 01:12
33F：推 JimAbbott:帕索不眠不休，那来的梦中人 = = 08/21 01:41
34F：推 puzzlez:啊我就不能做白日梦哦-.- 真爱计较... 08/21 06:40
35F：推 puzzlez:TO werul: 什麽尾数来着？你之前是算 XXX0 吗？ 08/21 06:42
36F：推 werul:我算的是有尾数 而且没超过1000@@ 尾数就是不是5或0的数字 08/21 16:28
37F：推 JimAbbott:爱做白日梦的帕索大 08/21 17:28
38F：推 puzzlez:我是故意打四位数说 被你破梗XDDDD 我的尾数也不是5或0... 08/21 18:24
39F：推 utomaya:答案个位数是8吗? 想确认一下 讲个位数应该不算泄露答案! 08/21 20:51
40F：推 utomaya:写了2个小时的程式 让程式去跑出答案 哈哈! 我真懒惰 08/21 20:53
41F：→ utomaya:但不知道答案对不对? 但4X4的话 我的程式跑出来是140种 08/21 20:54
42F：→ utomaya:6x6跑来出是1785种 08/21 21:34
43F：推 werul:我算出来尾数是3.. 08/21 23:18
44F：推 utomaya:应该是奇数格才要考虑对称情形 如3X3 5X5 7X7 08/21 23:22
45F：推 werul:我算出来是5X3...Q口Q 08/21 23:24
46F：→ utomaya:偶数格没有对称情形 直接除以四 ex: C(2^2,3)/4 =1 08/21 23:24
47F：→ utomaya:c(4^2,3)/4 = 140 C(6^2,3)/4 = 1785 08/21 23:25
48F：→ utomaya:除以4的原因是因为可以旋转4个角度 都视为一种 08/21 23:26
49F：推 werul:对 08/21 23:27
50F：→ utomaya:奇数格则会图形对称的情况 需另外考虑 不能直接除以4 08/21 23:28
51F：推 werul:直接除答案是575..不过当然不对XD 08/21 23:29
52F：推 werul:想知道程式怎麽写的 08/21 23:32
53F：推 FACE90006:我也想知道QQ...我最近好像变笨了... 08/22 10:32
54F：推 utomaya:就是把三格数字化 例如(1,1),(4,1),(5,5)记为114155 08/23 21:59
55F：→ utomaya:然後开始排列，把每一个三格翻转4次得到的数字丢到阵列去 08/23 22:00
56F：→ utomaya:然後下一个排列的三格，看看数字有没有已经在阵列里? 08/23 22:01
57F：→ utomaya:有的话 不予计数，免得得到同样的图形而重覆计数了! 08/23 22:03
58F：→ utomaya:我的程式没有很长 大概200行左右 用c++写的 08/23 22:13
59F：推 turing:借用utomaya的想法，如果我以中间(3,3)的格子当作原点。 08/24 22:05
60F：→ turing:向右为实数1,2;向左为-1,-2;向上为虚数i,2i向下为-i,-2i 08/24 22:06
61F：→ turing:则(1,1)以数字表示为-2+2i;(4,1)=1+2i;(5,5)=2-2i 08/24 22:07
62F：→ turing:逆时针旋转90度，相当於数字乘上i。 08/24 22:09
63F：→ turing:例如 (1,1)=-2+2i 乘上i = -2-2i = (1,5) 08/24 22:10
64F：→ turing:经过这样转换，是否有什麽定理可以用原题的解题上？ 08/24 22:12
65F：推 puzzlez:还满有创意，但至今我还想不出有什麽应用解题的方式.... 08/25 10:06
66F：推 stimim:在旋转的时候把中间的格子当做(0,0)， 08/25 11:20
67F：→ stimim:在做运算的时候把左上角的格子当做(0,0)， 08/25 11:20
68F：→ stimim:如果可以，就代表重覆，否则计数器加一 08/25 11:21
69F：→ stimim:唔...连推失败 08/25 11:21
70F：→ stimim:在旋转的时候把中间的格子当做(0,0)， 08/25 11:21
71F：→ stimim:在做运算的时候把左上角的格子当做(0,0)， 08/25 11:21
72F：→ stimim:整个盘面有25个格子，一个integer占32个bit 08/25 11:22
73F：→ stimim:所以用右边的25个bit来代表那些格子， 08/25 11:22
74F：→ stimim:(x,y)用第(x*5+y)个bit来表示，如果有放东西 08/25 11:22
75F：→ stimim:就是1，否则是0， 08/25 11:22
76F：→ stimim:所以每一个盘面会有三个bit不为零，可用一个整数代表 08/25 11:22
77F：→ stimim:，假设为k，对於每一个k，检查是否可以转换成一个更小的k' 08/25 11:22
78F：→ stimim:如果可以，就代表重覆，否则计数器加一 08/25 11:22
79F：→ stimim:这样枚举完所有可能之後就可以算出有几种方法 08/25 11:23
80F：→ stimim:这样写的话大概50行就够了 08/25 11:24
81F：推 puzzlez:嗯，看懂了...好像真的不难耶...... 08/25 14:38
82F：推 puzzlez:这麽一来就不用把查过的位置，记录下来了..... 08/25 14:39
83F：推 stimim:找到奇数项的公式了，可是不知道为什麽长这样 >.< 08/25 21:05
84F：推 puzzlez:哇，我知道为什麽耶～突然觉得自己好优秀～XDDDDD 08/25 21:35
85F：推 stimim:哇!！！我懂了，原来我忘了某一项～XDD 08/25 21:40
86F：推 puzzlez:结果我只优秀了35分钟....=.=" 08/26 06:51
87F：推 yhong:我3X3的只排出19个 = = 08/27 14:00
88F：推 yhong:对不起我错了 <(_ _)> 重算後是21，不知道少哪一个 ^^" 08/27 14:05