首页 > 其他 > 详细

[NOIP2004] 虫食算

时间:2018-02-26 21:29:36      阅读:240      评论:0      收藏:0      [点我收藏+]

建议网页缩放:250%

 

题目:(传送门

技术分享图片

从数据量来看,N≤26,也就是最多26个字母,26进制,26位数

第一个想到的肯定是直接爆搜

算一下时间复杂度为 O(N!) 显然不可取。

但很明显可以看出来,有大量的是可以直接排除的,或者说是不存在的。

那么按照加法竖式,从低位往高位。

例如样例C+A=C,那么一算就知道A是0.

举个例子若最后一位A+B=C (mod 10),那么在搜索的时候所有A+B≠C (mod 10)的情况就可以直接舍去

那这么一看我们就把搜索剪剪枝。

就可以过了。

 

dfs+剪枝

 

------------------------------分割线--------------------------

好的接下来是从网上看到的一种方法。

先把原网址放在这里。

高斯消元+dfs

据称时间复杂度是O( 2(n-1) * n2  

但博主原话是:总的时间复杂度变为O(2n?1n2),但由于很多取值不用O(n2)的时间即可判定为不可行,所以时间会比较短。

具体代码可以去看那个博客,毕竟我也没看太明白。

 

[NOIP2004] 虫食算

原文:https://www.cnblogs.com/Wh1t3zZ/p/8475915.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!