自选题解题报告填数游戏_第1页
自选题解题报告填数游戏_第2页
全文预览已结束

下载本文档

版权说明：本文档由用户提供并上传，收益归属内容提供方，若内容存在侵权，请进行举报或认领

文档简介

1、填数解题江苏苏州中学1，题目描述【问题描述】某天，curimit 在家无聊ing。突然发现了一个表格，于是他开始玩起了填数。curimit 有一个 3*n 的表格，他首先将这个表格前两行填上两个 1n 的排列，每一列上没有相同的数字。下面，他要求你在最后一行填入一个 1n 的排列，并且要求每一列上没有相同的数字。他想知道，最后一行一共有多少种填数的方案。【输入文件】第一行，一个 n。第二行，n 个数。(1n 的一个排列)第三行，n 个数。(1n 的一个排列)数据保证：没有一列的两个数相同。【输出文件】一行，填数的方案数。【输入样例】42 3 1 44 1 2 3【输出样例】2【数据规模和约定】

2、100%的数据中 n100；1【来源】试题。2，观察填数，由于是 1n 的排列，样例画出来，就变成这样：很自然而然得联想到棋盘放车，把现在就是要在白域内放 n 个车，求方案数。3，初步分析棋盘放车问题，在组合数学上有一个经典的数学工具叫做“棋盘多项式”。大家不知道也没关系，这里有一个定理。要把n 个车放到白域内，现在用容斥原理进行补集转化。设在（黑域）放 k 个车的方案数为 ak，那么：的方案数为 a0*n!的方案数为 a1*(n-1)!的方案数为 a2*(n-2)!有至少 0 个车放有至少 1 个车放有至少 2 个车放.根据容斥原理，可以知道：ans=a0*n!-a1*(n-1)!+a2*(

3、n-2)!-.经过初步分析之后，得到了一个基本想法：由于白色的空白区域非常多，而黑色只有 2n 个，很少。可以求出在内放 k 个车的方案数：ak。4，进一步分析问题为了能进一步研究的性质，画一个大一点的例子。2这里为了清晰一点，把用粉红色圆点来表示了。如果，对任意两个不能同时放车的圆点之间连接一条边。那么就转化成了求这的大小为 k 的独立集的数目了。比如上图，把棋盘去掉，换成边：发现什么了吗？这是一个环！n 个节点的环上放 k 个车的方案数是CkCk 1nknk 1问题似乎就这样解决了？还没！由上面方法构造出的图可能有多个环，那么到底有几个环呢？把输入的两个排列，看成是一个置换，然后把它分解成循环。比如1 2 3 4 5 62 3 1 5 6 4分解成循环就变成了(1 2 3)(4 5 6)有两个循环，而每个循环长度都为 3，所以构造成图以后，图中一共有 2 个环，每个环上的点数都是 6。3现在就是，有多个环，求这个图的大小为 k 的独立集的数目。这个问题就非常简单了，这就是一个背包问题设 fij表示可。i 个环中选取 j 个点的方案数，然后 O(n)转移一下状态即时间复杂度：O(n3)，不计高精度5，总结

人人文库> 全部分类> 教育资料 > 课件下载

温馨提示

  • 1. 本站所有资源如无特殊说明，都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等，如果需要附件，请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸，网页内容里面会有图纸预览，若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对用户上传分享的文档内容本身不做任何修改或编辑，并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容，请与我们联系，我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

最新文档

评论

0/150

提交评论