USACO 4.3.2 The Primes

够BT的一道题,改了几遍才过 - -
一开始没想费太多内存觉得稍微预存几种结果应该就差不多了,结果完全低估了数据规模。
只好把所有可能用到的模式全预算出来再循环。结果弄了快300行ORZ...
还有一次犯傻没排序就跑去提交了
 
TASK: prime3
LANG: C++
 
Compiling...
Compile: OK
 
Executing...
   Test 1: TEST OK [0.065 secs, 2984 KB]
   Test 2: TEST OK [0.054 secs, 2988 KB]
   Test 3: TEST OK [0.065 secs, 2984 KB]
   Test 4: TEST OK [0.065 secs, 2988 KB]
   Test 5: TEST OK [0.076 secs, 2984 KB]
   Test 6: TEST OK [0.140 secs, 2984 KB]
   Test 7: TEST OK [0.119 secs, 2988 KB]
   Test 8: TEST OK [0.130 secs, 2988 KB]
   Test 9: TEST OK [0.205 secs, 2988 KB]
   Test 10: TEST OK [0.259 secs, 2988 KB]
 
All tests OK.
Your program ('prime3') produced all correct answers!  This is your
submission #5 for this problem.  Congratulations!
 
要速度,貌似只能模拟填表的过程,并且每步选限制尽可能多的行或列来填。
第1行和第1列限制最多,开头第1位已定,且各位都不能出现0,先把他们填了。
然后选辅对角线(左下到右上),因为开头结尾两位都已定。
再填主对角线,第1位和第3位已定。
下面是第二行、第二列、第四行、第四列,这四种情况都是 1、2、4 位已定
然后第三行和第三列都只剩下最后一位空缺了。最后检查一下第五行和第五列即可。
 
从上面过程看出要预先计算的是:
(1) 所有5位质数且各位数字和满足条件的数
(2) 第1位已知且满足(1),各位都不为0的组合
(3) 1、5位已知且满足(1)的组合
(4) 1、3位已知且满足(1)的组合
(5) 1、2、3、4位已知且满足(1)的组合
 
其他好像有提出先填第5行和第5列的,因为这两行除了满足质数与数字和外 各位只能是 1、3、7、9 四选一。不过我觉得这没有用,例如只要第一列填了质数,则第5行第一位自然就只会是 1、3、7、9 之一了,先填第5行对第1列来说也并没有其他额外限制作用。但仅是猜测,也没试验过。
 
预先开个100000的数组,第一遍求所有质数(顺便将不是质数的值存为下标方便遍历),然后筛选数字和满足条件的数,同样使下标形成链表方便遍历。同时选出各位数字满足条件的组合预先存起来,剩下只用循环便是。排序嘛,就每位挨个判断了,也没几个数。

USACO Comments(0) 2009年4月25日 07:29