试了一下,纯 O(|s|!)枚举仍然会TLE,就换了个方式枚举可过 想法是,如果我们用输入的一部分凑出了余数r,那必须用输入的另一部分 凑出余数 d-r. 所以说,我们把输入拆分成前 |s|/2 个和後 |s|/2 个分别排列,使得排列 的花费降为 (|s|/2)! 之後,再把两边分别组合起来;为了方便,我们先枚举 前 |s|/2 个字所要占用的位置,这样後 |s|/2 可以用的位置就确定了. 枚举位置+排列後,对前後分别记下算出余数r(0≦r＜d),然後算出被d整除 的方式 枚举位置的花费则是 C(n,n/2),极限测资C(10,5)≦252;所以这样做时间 复杂度为 O( C(n,n/2)[d+(n/2)!] )... 传上去是跑 0.120s 举个例子, s=12345, d=2, 前半取 2 个, 後半取 3 个 12 21 余0的有12000,21000共两个 余1的0个 345 354 435 453 534 543 余0的354,534两个 余1的345,435,453,543共四个 所以位子这样分配时,mod d余零的共 2*2 + 0*4 = 4个 1 2 2 1 余0的有10200,20100共两个 余1的零个 3 45 3 54 4 35 4 53 5 34 5 43 余0的有3054,5034两个 余1的3045,4035,4053,5043共4个 ...剩下类推 附上写得烂烂的程式码 http://pastie.org/2474232 我想这样做在这题能跑这麽快是因为d不会全部都是10,000... 而这种题目让人很想状态压缩 DP (状态:[哪些用了哪些还没][余数]) ,不过枚举能过就算了... ※ 引述《singlovesong (~"~)》之铭言： : 题目: : 11084 http://luckycat.kshs.kh.edu.tw/homework/q11084.htm : Code: : 11084: http://codepad.org/c7XwSbg4 : 这两题都没有什麽特别的想法 直接暴搜 : 果然都TLE : 想请问这两题该用什麽解法才可以不超时的呢？ : 上网google 了好一阵子都没什麽结果... : code写的很丑 只希望强者能指点一下算法^^" --

※ 发信站: 批踢踢实业坊(ptt.cc) ◆ From: 61.217.33.236 ※ 编辑: suhorng 来自: 61.217.33.236 (09/03 11:03)