注意去重,如果有多个符合条件的j对应相同的a[j]我们只加入最大的j对应的total[j],
这是因为如果u>v且a[u]==a[v],以a[v]为结尾的所有序列都包含于以a[u]为结尾的序列集合.
先放对角线上的两个素数,注意左上角数字是确定的,左下角是一个素数的结尾所以必须为奇数.
然后顺序枚举第1,2,3行上的素数,之后第4,5行可以算出来,记录可行解.
排序输出.
由于每列都是素数,可以打表记录下一些素数"特征"是否存在,用于剪枝,比如有素数为11351,就记 head[1]=head[11]=head[113]=head[1135]=true,如果枚举过程中出现了一些"特征"不存在(对应的head值为 false)就剪枝.另外一定要充分利用已经放置的数的信息进行提前剪枝,比如枚举到第三行素数,可以得到第二列和第四列的前四位数,即可比对这些"特 征"是否存在.
枚举去掉的路口,如果去掉后从起点floodfill不能到达终点,则此路口unavoidable.
如果从一个unavoidable的路口出发不能回到起点可达的路口,则此路口是splitting point.
首先注意到由于目标词长度最大为7,那么最多只有两个字母组合,且只有长度为3或4的单词可以组合在一起.
对长度3或4的单词单独打表,加上一些简单的剪枝,枚举两单词组合的情况不会超时.
本博客文章如非特殊说明均为本人原创,转载请注明出处. 请查看全局引用声明.
本作品采用知识共享署名-非商业性使用-相同方式共享 2.5 中国大陆许可协议进行许可.