USACO/prime3
来自"NOCOW"
这篇文章可以证实是由NOCOW用户原创，不存在任何版权争议。 本文作者同意以GNU FDL、CC-by-sa和GNU LGPL（如果适用）三种版权发布此文章（不包括翻译文章中属于原始所有者的部分版权）。 如果你修改了这篇文章并且不同意用GNU FDL以外的版权发布，可以换一个版权模板或者移除此模板。
- 这是USACO Chapter 4 .3中的OI题目The Primes的介绍及题解，参见 翻译，C语言代码，C++语言代码，Pascal语言代码。
目录 |
[编辑] 问题分析
这道题比较难。 采取枚举模拟搜索，但是需要优化。
[编辑] 优化技巧
一行行的枚举连样例都过不了，考虑这题格子之间有相互约束，所以首先要优化枚举顺序。先枚举两条对角线，因为他们控制的行列是最多的，而且左上角的数已经确定了。接着枚举中间的一竖列,因为它同样控制的行列最多,接着枚举最上面一行和最下面一行。此时第3行的2，4两个数也可以通过减法得到了。最后枚举第2，4行，第3行减法得到。于是所有格子都已经确定了，验证一下就OK。
数据结构方面，需要多个数组记录满足条件的素数，比如已知第1,3,5位的所有素数或已知第1位的所有素数都要预处理出来。并且每个数用5个1位数储存，这样操作方便而且效率高。
全程都需要时刻剪去不满足要求的情况。
注意细节，此题相当繁杂。
By Leser Yang.
其实用for暴力枚举不烦，但是写错就完蛋了，调试要累死的.
[编辑] 谁说顺序枚举过不了
Test 1: TEST OK [0.011 secs, 3092 KB] Test 2: TEST OK [0.011 secs, 3092 KB] Test 3: TEST OK [0.043 secs, 3092 KB] Test 4: TEST OK [0.065 secs, 3092 KB] Test 5: TEST OK [0.076 secs, 3092 KB] Test 6: TEST OK [0.270 secs, 3092 KB] Test 7: TEST OK [0.346 secs, 3092 KB] Test 8: TEST OK [0.464 secs, 3092 KB] Test 9: TEST OK [0.821 secs, 3092 KB] Test 10: TEST OK [1.156 secs, 3092 KB]
用了15重循环枚举+类Trie+位运算（类似Checker），写起来很爽，一次AC。。。 但用时确实不会很快。。。 具体见C++源代码
你程序牛逼，囧rz --路人
你的程序相当牛逼，OTZ。在下佩服得五体投地 -- By 路人乙
你的程序确实相当相当牛逼，囧rz Orz。在下看了仰天长叹 -- By 路人丙
你的程序实在是太太太太牛牛牛牛逼，囧rz Orz，各种rz。在下看了各种佩服外加无限仰慕 -- By 路人丁
[编辑] 递归的顺序枚举都能过
Test 1: TEST OK [0.011 secs, 2280 KB] Test 2: TEST OK [0.022 secs, 2280 KB] Test 3: TEST OK [0.043 secs, 2280 KB] Test 4: TEST OK [0.097 secs, 2280 KB] Test 5: TEST OK [0.108 secs, 2280 KB] Test 6: TEST OK [0.346 secs, 2280 KB] Test 7: TEST OK [0.464 secs, 2280 KB] Test 8: TEST OK [0.594 secs, 2280 KB] Test 9: TEST OK [0.994 secs, 2280 KB] Test 10: TEST OK [1.339 secs, 2280 KB]
只用了lowbit和原始的递归
搜了4*4的方阵，对于任何行、列、主副对角线 都用lowbit 剪枝即可。
具体见C源码……
[编辑] 我的递归顺序枚举
TASK: prime3 LANG: C++
Compiling... Compile: OK
Executing...
Test 1: TEST OK [0.022 secs, 3412 KB] Test 2: TEST OK [0.032 secs, 3412 KB] Test 3: TEST OK [0.043 secs, 3412 KB] Test 4: TEST OK [0.054 secs, 3412 KB] Test 5: TEST OK [0.076 secs, 3412 KB] Test 6: TEST OK [0.097 secs, 3412 KB] Test 7: TEST OK [0.130 secs, 3412 KB] Test 8: TEST OK [0.151 secs, 3412 KB] Test 9: TEST OK [0.194 secs, 3412 KB] Test 10: TEST OK [0.227 secs, 3412 KB]
All tests OK. 用的是顺序枚举，速度很快 具体顺序：
0 20 22 23 8 13 1 17 7 15 9 10 2 11 12 14 6 18 3 16 5 19 21 24 4
加粗的可以推出来，13重for 详见bc_zhan1代码
[编辑] 另一种思路
Executing...
Test 1: TEST OK [0.011 secs, 4852 KB] Test 2: TEST OK [0.011 secs, 4852 KB] Test 3: TEST OK [0.022 secs, 4852 KB] Test 4: TEST OK [0.162 secs, 4852 KB] Test 5: TEST OK [0.065 secs, 4852 KB] Test 6: TEST OK [0.216 secs, 4852 KB] Test 7: TEST OK [0.259 secs, 4852 KB] Test 8: TEST OK [0.486 secs, 4852 KB] Test 9: TEST OK [0.594 secs, 4852 KB] Test 10: TEST OK [0.972 secs, 4852 KB]
方法： 保存两个符合要求的10000..100000质数表，一个质数表中的质数须满足最高位为矩阵的第1个数且全部为非零位; 另一个质数表的质数满足各数位均非偶数; 两个表中的质数的各位之和为输入值。想必读者已经猜到了，矩阵最外一层的四个质数必然分别在这两个表中。而经过实际测试表明，两个表的大小基本上不会超过100，由此只需四重循环枚举，再判断内部的9个数字。 经过计算可得出矩阵中央位置的数字可有最外层的16个数字直接确定。因此只需再枚举2个数，即可确定剩余的数字。
By Ever_ljq.
[编辑] 优化顺序枚举
前7个点0.000secs 后3个点0.027secs
USER: Wang Qian [wangqia6] TASK: prime3 LANG: C++
Compiling... Compile: OK
Executing...
Test 1: TEST OK [0.000 secs, 8068 KB] Test 2: TEST OK [0.000 secs, 8068 KB] Test 3: TEST OK [0.000 secs, 8068 KB] Test 4: TEST OK [0.000 secs, 8068 KB] Test 5: TEST OK [0.000 secs, 8068 KB] Test 6: TEST OK [0.000 secs, 8068 KB] Test 7: TEST OK [0.000 secs, 8068 KB] Test 8: TEST OK [0.027 secs, 8068 KB] Test 9: TEST OK [0.027 secs, 8068 KB] Test 10: TEST OK [0.027 secs, 8068 KB]
All tests OK.
[编辑] DFS手动指定搜索顺序
其实和for循环的做法差不多, 就是在DFS里写上25个case..但是速度要快得多, 最后一个测试点0.1s 搜索顺序是这样的：
0 21 18 22 5
12 2 13 8 9
16 23 3 24 10
14 7 15 4 11
6 19 17 20 1
大致分为几种情况{sum表示当前行\列\对角线未填数字之和}:
1)非末位. 边界条件是 0 <= i <= min{sum, 9}
2)末位. 边界条件是i = 1, 3, 7, 9(i <= sum)
3)可计算位(即该行或列或对角线已经填了4个数). sum < 10, 判断是否为素数, dfs下一层时, sum-下一层已填充位置.
4)对于由情况3)转移而来的状态, 需要检查sum >= 0.
详见C++代码.
--Climber.pI
