电子商务网站建设实验指导,网站建设总结 优帮云,查询企业的app哪个好,做网站 广告 备案题目名称#xff1a;小豚鼠搬家 时间限制#xff1a;1000ms内存限制#xff1a;256M 题目描述 小豚鼠排排坐。 小艺酱买了一排排格子的小房子n*m#xff0c;她想让k只小豚鼠每只小豚鼠都有自己的房子。 但是为了不浪费空间#xff0c;她想要小房子的最外圈尽量每行每列都有… 题目名称小豚鼠搬家 时间限制1000ms内存限制256M 题目描述 小豚鼠排排坐。 小艺酱买了一排排格子的小房子n*m她想让k只小豚鼠每只小豚鼠都有自己的房子。 但是为了不浪费空间她想要小房子的最外圈尽量每行每列都有一只小豚鼠居住。 小艺酱想知道自己有多少种方案安排小豚鼠。 输入描述 输入整数n,m,k。(1n,m20,0kn*m) 输出描述 输出方案数答案对1e97取模。 示例 示例1 输入 3 3 2 输出 2 提示 无 用例里有两个比较特殊一个是没有豚鼠的用例[3, 4, 0]这个如果用递归的话需要避免这个用例豚鼠数字小于2就返回0笼子就1个格返回1
另一个就是真正的算法考验的用例了 [5, 5, 12]返回结果是 4704606…我在本地跑了一下最土的递归用了一分半钟左右才得出这个结果
先放第一版的
def s(row,col,num,start,pos):#result []result 0if num 1:for i in range(start,row*col):t pos [i]if len([_ for _ in t if _ // col 0])0 and len([_ for _ in t if _ % col 0])0 and len([_ for _ in t if _ // col row-1])0 and len([_ for _ in t if _ % col col - 1])0:#result.append(pos [i])result 1return resultelse:for i in range(start,row*col-num1):result s(row,col,num-1,i1,pos[i])return resultn,m,k [4,4,14]
result s(n,m,k,0,[])于是就想起来好像看到过某个文章里讲解了这个题目怎么算完全不用递归组合什么的就是数学公式最后找了半天也没找到之前看到的文章但还是搜索出了一个类似的讲解的也比较清楚的文章
https://www.cnblogs.com/pengwill/p/7367030.html
文章的意思就是用最大组合减去不合要求的组合再加上遗漏的组合再减去遗漏组合中不合要求的组合。。。嗯用循环完成的叫什么容斥原理。。。原谅老顾没上过学。。。。 具体为什么程序这么写倒是没搞明白尤其是中间用到位运算怎么就和这总计的16项最大集合及15个容斥原理对应内容 最后还是列了个输出信息才弄明白哪些是加的哪些是减的分别加了多少减了多少。。。。嗯只需要一个阶乘函数一个组合函数就够了
n,m,k [5,5,12]total 0for i in range(16):idx 0row ncol mif i 1: # 对应集合 A最上边一行无小鼠col - 1idx 1if i 2: # 对应集合 B最下边一行无小鼠col - 1idx 1if i 4: # 对应集合 C最左边一列无小鼠row - 1idx 1if i 8: # 对应集合 D最右边一列无小鼠row - 1idx 1print(i:,i,i1,i2,i4,i8,idx:,idx,idx 1,row:{},col:{}.format(row,col))if idx 1:total - int(X(row*col,k))else:total int(X(row*col,k))print(total)
准备自己时常复习一下争取把这个公式弄明白加油老顾
弄这么个文章主要是搜不到“小豚鼠搬家”这个题目的题解百度出来的都没有具体算法好伤心
