[POJ 3420]状态压缩动态规划、矩阵乘法、快速幂

【题目大意】给定一个4*N的方格,求用2*1或1*2的方块把它填满有多少种方案。

【算法分析】就是用状态压缩动态规划的转移方程构造矩阵,从而用快速幂解决。

【其它】1CE,g++不允许不打stdio.h就用scanf

6418763 edward2 3420 Accepted 168K 47MS C++ 1622B 2010-02-06 21:19:33

【CODE】

#include

[POJ 2663]状态压缩动态规划

【题目大意】给定一个3*N的block,然后要你求用2*1或1*2的格子填满它有多少种方案。

【算法分析】F[I,J]表示第i行,状态为j的时候的方案数。而对于j,1表示需要向下延伸,0表示不需要向下延伸。

【其它】1A,很久没做状态压缩,有点手生了。。。

6418536 edward2 2663 Accepted 168K 0MS C++ 828B 2010-02-06 20:10:21

【CODE】

#include

HDU月赛

今天被虐了5个小时。一整天就做了两道题。果然,ACM和OI差别还是非常大的。。。

一开始看到前两题,数学,直接放弃。然后看到第3题,感觉很简单,因为之前做过一个类似的,而且比这个还要难,算是加强版,所以1A秒杀。然后切出去看problem list。发现最后一题最多人AC,就去做最后一题。做了才发现代码量非常大,接近两百行,如果有模板,应该是水得。。。不过很可惜,我不是职业acmer,没有模板,所以。。。敲了N久,调试了大概1.5个小时,1A!

然后回看第2题,用等比数列求和公式把数列的通项先推出来,然后发现实际上是求x^n mod a0=1所对应的最小的n值,然后与肥闽讨论了N久,决定暴力。然后TLE,MLE。。。换了3种hash,全部挂掉了。。。于是,再次果断放弃。

然后最后看到第4题也比较多人A,然后就去做,写了个200+行的A*,还没调出样例,比赛结束了= =

虽然比较悲剧,但是也居然排到了13名。。。

最后发现一点,数学差得太远了,差得更远的是英语。。。

另外,YM DIY群的AC大牛和UranusX大牛。。。就是第一和第四那两只。。

Rank Team Solved Penalty 1001 1002 1003 1004 1005 1006 1007 1008 1009 1 AC&&ZT&&LCC 5 11:22:00 02:27:04
(-2) 01:43:33
(-3) 01:34:23 02:46:20 (-20) 01:10:40 2 yaya&zgmf_x20a&Arios 5 18:26:30 01:15:05 02:32:55
(-1) 03:30:25
(-4) 04:50:37
(-1) 03:57:28
(-1) 3 万物皆数 4 12:58:12 02:03:22 02:27:23
(-4) 04:12:18 02:55:09 4 UranusX 4 13:21:39 03:15:44
(-4) 00:57:45
(-1) 04:42:43 01:45:27
(-3) 5 whu_高云翔 4 13:30:39 03:06:27
(-2) 04:04:39
(-2) (-3) 03:08:40
(-1) 01:30:53 6 囧の軌跡 3 07:22:08 03:20:25
(-1) 01:33:08 02:08:35 7 z__jj 3 07:35:38 (-1) 04:35:08
(-2) 00:57:31 (-9) 01:22:59 8 majiaNO.1 3 08:50:19 03:28:09
(-4) 01:29:53 (-5) 02:12:17
(-1) 9 zsasuke 3 10:58:14 01:02:45
(-5) 04:25:05
(-2) (-2) 02:30:24
(-2) 10 ggcc11 3 10:59:01 03:19:09
(-3) 02:37:14 04:02:38 11 NewHorizon 3 11:41:02 03:04:23 04:05:31 (-1) 04:31:08 12 gtzygtzy 3 12:15:16 04:32:14
(-1) 03:41:52 03:41:10 13 cwj 2 03:31:25 (-5) 01:14:43 02:16:42 14 wccn 2 04:40:00 01:20:16
(-1) (-3) 01:59:44
(-3) 15 SHNU_FireStar 2 04:53:01 (-1) 02:09:08
(-1) (-1) 02:23:53 16 喔拉拉 2 05:08:49 (-11) 01:17:14
(-2) 03:11:35 17 依然紫轩 2 05:13:37 01:35:25 03:38:12 (-3) 18 seabao 2 05:29:00 03:35:46 01:33:14
(-1) 19 visitor00 2 05:31:44 (-8) 02:07:52 03:03:52
(-1) 20 Rexer 2 05:38:03 04:33:54 (-2) 00:44:09
(-1) 21 starvae 2 05:42:57 04:06:38 (-1) 01:36:19 22 WHU_123 2 06:16:57 02:03:51
(-1) 03:33:06
(-1) 23 foreverlin 2 06:47:24 (-7) 03:18:22
(-1) (-3) 02:49:02
(-1) 24 majia 2 07:02:44 03:38:15
(-2) (-4) 02:44:29 25 山寨队 2 07:30:31 (-2) 03:52:24 02:58:07
(-2) 26 ReDow 2 07:59:30 (-5) 03:03:34
(-1) (-5) 03:55:56
(-2) 27 kaka8 2 08:05:20 (-3) 04:49:39
(-1) 02:55:41 28 xxjx 2 08:34:33 03:03:48
(-2) (-4) (-1) 04:30:45
(-1) 29 UESTC-Arbiter 2 09:36:12 (-6) 04:02:13
(-3) 02:33:59
(-6) 30 yrjie 2 12:01:28 (-5) 04:52:28
(-12) 02:29:00
(-2) 31 rectaflex 2 12:23:55 (-2) 04:04:43
(-15) 02:19:12
(-3) 32 RaceBug 1 01:08:35 (-5) 01:08:35 33 luther 1 01:39:32 (-5) 01:19:32
(-1) 34 autumncat 1 01:49:49 (-3) 01:09:49
(-2) 35 PlayerII 1 02:08:41 02:08:41 (-4) 36 whu_fatboy 1 02:09:08 (-2) (-5) 02:09:08 37 zjshark 1 02:23:00 02:23:00 38 PrimeMusic 1 02:29:17 (-3) 02:29:17 39 tao 1 02:46:12 (-2) 02:06:12
(-2) 40 open 1 02:57:15 02:37:15
(-1) 41 qu317058542 1 03:13:38 01:33:38
(-5) 42 UESTC_09P27 1 03:26:50 03:06:50
(-1) 43 chenlie 1 03:28:35 (-1) 03:28:35 44 Jsky 1 03:31:10 03:31:10 45 kimhmguen 1 03:32:12 03:32:12 46 surffor 1 03:41:03 (-2) 03:41:03 47 弯弯陈 1 03:44:44 03:24:44
(-1) 48 cowmick 1 03:46:18 (-1) 03:06:18
(-2) 49 yudaer 1 03:55:46 (-9) 03:35:46
(-1) 50 skddj 1 04:03:49 03:43:49
(-1)