欢迎来到大分享文库-在线教育资源分享平台 ! | 帮助中心 大分享文库-在线教育资源分享平台
大分享文库-在线教育资源分享平台
  • 简介:在信息学竞赛中的简单应用,侯启明,信 息 论,信息论简介,信息论是关于信息的本质和传输规律的科学的理论。 通过它可以很方便地得到某些交互式问题的一个较好的步数下界“信息论下界”,让我们先来看一些信息论的基本理论,理论基础,定义如果一个随机变量x共有n种取值,概率分别为p0,p2,,pn,则其熵为Hxfp0,p2,,pn-∑Cpilogpi 定理1在得到关于随机变量x的一个熵为h的信息后,x的熵将会减少h。 定理2当一个随机变量的各种取值概率相等时,它的熵最大。,这些理论看上去和某些题目关系密切,不是吗 那么,具体应该如何运用呢让我们来看一些例子,我们宿舍二楼到三楼
    下载积分: 10
    上传时间:2019-02-08
    页数: 36
    29人已阅读
    ( 4 星级)
  • 简介:长方体的体积并,金陵中学 陆可昱,矩形,平面中n个矩形的面积并的计算 方法 离散 扫描法 线段树,离散,离散点 矩形各边(或其延长线)与坐标轴的交点 离散单位段 离散点有序化后相邻两个离散点之间的距离,扫描法,把平面分割成条,在每个条中环境变成一维的 每一个给定的条的截面都可表现为其相邻两个条截面中任意一个小的修改,线段树,二叉树 每个结点表示一区间[a,b] b-a1 cab div 2 [a,c]及[c,d],长方体,三维空间中n个长方体的体积并的计算 方法 离散 扫描法 存储平面,二重二叉树,存储平面 x轴二叉树 y轴二叉树,矩形的示意,标号,根结点为1 非叶子结点i 左
    下载积分: 10
    上传时间:2019-02-08
    页数: 19
    38人已阅读
    ( 4 星级)
  • 简介:由对称性解2-SAT问题,2-SAT,2-SAT就是2判定性问题,是一种特殊的逻辑判定问题。 2-SAT问题有何特殊性该如何求解 我们从一道例题来认识2-SAT问题,并提出对一类2-SAT问题通用的解法。,Poi 0106 Peaceful Commission [和平委员会],某国有n个党派,每个党派在议会中恰有2个代表。 现在要成立和平委员会 ,该会满足 每个党派在和平委员会中有且只有一个代表 如果某两个代表不和,则他们不能都属于委员会 代表的编号从1到2n,编号为2a-1、2a的代表属于第a个党派,输入n(党派数),m(不友好对数)及m对两两不和的代表编号 其中1≤n≤8000
    下载积分: 10
    上传时间:2019-02-08
    页数: 24
    56人已阅读
    ( 4 星级)
  • 简介:探寻深度优先搜索中的优化技巧,从正方形剖分问题谈起,,正方形剖分问题,问题描述 将n n 个小格组成的大正方形分割成若干个较小的整数边长的正方形,要求分成的小正方形数目最小。 范围1≤n≤32。 编程环境FreePascal。可用64MB空间,分析,当n为偶数时最少需要4个小正方形,当n为奇数时,很难发现有什么数学规律。,设fi,j表示一个ij的矩形最少可以被剖分成多少个小正方形,n7时,求出结果为10,并不是最优值。原因最优方案不一定能被某条直线分割。,fn,n仅是一个可行解,不过其值与最优解十分接近的。 目前只能用搜索 优化搜索之前先用上述动
    下载积分: 10
    上传时间:2019-02-08
    页数: 27
    27人已阅读
    ( 4 星级)
  • 简介:一类称球问题的解法,,问题的提出,给定N个球 有个比标准球重的次品混入其中 你有一架天平,用最少的次数找出这个次品。,N 3,①是次品,②是次品,③是次品,N3时称1次就可以找出次品,N 9,次品在A中,次品在B中,,,,,,,A,B,通过一次称量,可以把次品可能存在的范围从9个,缩小到3个 N 3的时候一次就能称出次品,N 9时称2次,,,,,,,次品在C中,A,B,更一般的情况,N 3k,A,B,C,更一般的情况,次品在A中,次品在B中,次品在C中,,,,范围缩小到原来的1/3,更一般的情况,n 3k1, n 3k2和n3k类似,也是均分成三堆 每次称
    下载积分: 10
    上传时间:2019-02-08
    页数: 32
    34人已阅读
    ( 4 星级)
  • 简介:一类搜索的优化思想数据有序化,南京市金陵中学 刘一鸣,数据有序化,为什么要进行数据有序化 数据有序化的实现 两种实现方法的比较,数据有序化的思想,就是将杂乱的数据,通过简单的分类和排序,变成有序的数据,从而加快搜索的速度。,为什么要进行数据有序化,例1 装箱问题,题目大意 现有一个体积为V的集装箱和N种货物,每一种货物都有固定的体积,数量无限。你的任务是写一个程序,求出最少用多少个货物,就能放满集装箱。 数据规模V货≤V≤109,运行时间的对比,测试方法随机生成20个数据,测试运行时间并求平均值。,程序效率不同的原因,不理想的初始解,最理想的初始解,最优解,比较理想的初始解,数据
    下载积分: 10
    上传时间:2019-02-08
    页数: 30
    25人已阅读
    ( 4 星级)
  • 简介:染色法和构造法在棋盘上的应用,广东北江中学 方奇,1 基本概念 2 棋盘的覆盖 1 同形覆盖 2 异形覆盖 3 小结 3 马的遍历 1 马的哈密尔顿链 2 马的哈密尔顿圈 4 其它问题 1 Worm world 5 结语,目录,●构造法 直接列举出某种满足条件的数学对象或反例导致结论的肯定与否定,或间接构 造某种对应关系,使问题根据需要进行转化的方法,称之为构造法 。,●染色法 用不同颜色对棋盘格子进行染色,起到分类的效果。 类似国际象棋盘上的黑白二染色,称为“自然染色”。,●棋盘 所谓m*n棋盘,指由m行n列方格构成的m*n矩形。每个方格成为棋盘的格,
    下载积分: 10
    上传时间:2019-02-08
    页数: 23
    43人已阅读
    ( 4 星级)
  • 简介:答案只有一个,浅谈问答式交互问题,交互式问题的分类,分类依据库函数和选手程序的关系 博弈式交互 问答式交互,博弈式交互,问答式交互,问答式交互的逻辑模型,,,,,,,,,,,,,,,,,最后的答案,发现之旅,我们的目标,把题目做对,拿到分数。 不管用什么方法,在题目允许的情况下完成此题 把题目做好。 用较好的方法把交互式题目做得简洁、漂亮。 用合适的方法,找出那唯一可能的解。 探讨这一类问题的解决策略。 触类旁通,争取为其它问题提供灵感。,我们的工具,解决问题的两种思路,思路一“筛”法,一言以蔽之减少答案的不确定性 提问的选择范围 可能降低问题不确定性的所有问题。 如何选择提
    下载积分: 10
    上传时间:2019-02-08
    页数: 25
    37人已阅读
    ( 4 星级)
  • 简介:求最大重复子串 江苏金陵中学 林希德,题目,字符串W由大写字母组成,W中包含一 些连续出现两次的相同子串,称之为重复子 串。重复子串的大小决定于循环节的长度。,W “B B A A B A B A A B A B B”,A B A A B A,,举例,,,B B,,,循环节长度为3,循环节长度为1,请你求出最大重复子串的循环节长度。,题目,字符串W由大写字母组成,W中包含一 些连续出现两次的相同子串,称之为重复子 串。重复子串的大小决定于循环节的长度。,数据规模,n |w| 100000,On2,Onlg2n,On,后缀树,两个辅助算法,On,KM
    下载积分: 10
    上传时间:2019-02-08
    页数: 38
    38人已阅读
    ( 4 星级)
  • 简介:平面图在信息学中的应用,海南省海南中学 刘才良,引言,平面图是图论中一类重要的图,在实际生产中应用非常广泛。比如集成电路的设计就用到平面图理论。在信息学中,虽然有关平面图的题目并不多见,但对于某些题目,如果通过建模转化,应用平面图的性质,将大大提高算法的效率。因此,掌握一些平面图理论会对我们有很大的帮助。,相关定义、定理及推论,平面图 一个无向图G,如果能把它画在平面上,且除V中的节点外,任意两条边均不相交,则称该图G为平面图。,例如图a经变动后成为b,故图a为平面图。而图c无论如何变动,总出现边相交,图c为非平面图。,,相关定义、定理及推论,面 设G为一平面图,若由
    下载积分: 10
    上传时间:2019-02-08
    页数: 23
    32人已阅读
    ( 4 星级)
关于我们 - 网站声明 - 网站地图 - 资源地图 - 友情链接 - 网站客服客服 - 联系我们

copyright@ 2008-2018 大分享文库网 版权所有
经营许可证编号:豫ICP备11013292号-2

客服QQ:1965775022

收起
展开