黑书笔记

作者:网络    软件教程库   2020-05-15

就从p77开始记好了.(稍微扩容)

p77

排序.

1.香农信息论

基于比较的排序不可能突破o(nlogn)的复杂度限制.
1) 比较一次可以得到一个bool量,最大信息熵为$\log_2{2}=1.0$bit
2) 全排列的个数是$n!$级别的,唯一地确定一个全排列需要$o\left(\log_2{n!}\right)=o(n\log{n})$bit的信息熵
3) 因此比较的次数不可能少于$o(n\log{n})$级别.

2.实数比较的$o(n\log{\log{n}})$时间算法.

这个的资料我没有找到,如果有谁找到了请告诉我.我只找到了两三篇整数排序的论文.

1) 时间复杂度$o(n\log{\log{n}})$,链接: http://pan.baidu.com/s/1i3vha0p 密码: atfv
2) 期望时间复杂度$o(n\sqrt{\log{\log{n}}})$,链接: http://pan.baidu.com/s/1jgmydsi 密码: irxb
upd: 第三篇
3) 时间复杂度$o(n\log{\log{n}})$,$o(n)$,parallel,...,空间复杂度$o(n)$,链接: http://pan.baidu.com/s/1qwkjvgw 密码: qmca
(神级论文)

(论文地址请不要转载,谢谢.)

整数的排序可以使用veb树,也可以使用一种据2)中说的"简单"的算法3).

p78

1.poi

polish olympaid in informatics

避免邪教污染,这里给出了地址.

p87

1.并查集删除一个元素

我们对于每个并查集节点设置一个disabled属性即可.

当删除一个节点时,将它的disabled属性设置为true,并重新建立一个节点,将原节点查找指针指向新节点.($o(1)$)

如果删除的是root,我们遵循lazy updating的原则;在第一个访问到root是一个disabled节点时将这个root的father指向这个节点,把这个节点设置为新的root即可.($o(1)$)

2. 1.4.2 1.4.3

1.4.2) 没试过...
1.4.3) 这个均摊时间复杂度是错误的,因为它无法保证k的大小,当n=1时,假设原数字是$2^{k-1}-1$,此时的操作时间复杂度为$o(k)=o(kn)$.均摊复杂度需要对于任意操作序列都有$t(n)=o(n)$,而显然长度为1的操作序列也是合法的,但是此时不成立,因此均摊分析是错误的.

3.穿线森林

我们可以对每一棵堆建立一个链表,然后启发式合并.这个很简单的,有一篇大学的讲稿:链接: http://pan.baidu.com/s/1sje4ja9 密码: c8n3

4.poi窗户

因没有数据范围,仅提供思路.

我们将顶点坐标排序,用根离散化的扫描线处理.在处理前我们要先在通过窗户上下界的与上下界垂直的线段的垂足上加点,以处理边界情况.从上界往下界(或反过来),边扫描边合并矩形.到另一个界的时候查看下有几个联通块即可.

p88

1.ceoi1999 奇数偶数

这个专题是并查集,那么往并查集的方向去想.

那么这道题就是用并查集维护奇偶性数据,并动态合并.动态合并是一个难点,但也不是不可以解决.方法很简单,我们把闭区间转化为半开半闭区间就可以无压力地合并了.

a) 如果两个端点都是同一个联通块的端点,那么他们的奇偶性已经可以直接用异或运算查询出来.
b) 如果两个端点不是同一个联通块,就把小的联通块并入大的那个,并修改小的的奇偶性以吻合.

那么通过一个$o(1)$的merge操作怎么能保证a)中的性质呢还是lazy updating,方法是边路径压缩边以父亲节点为准更新.为什么这样做是正确的我们的题目要求尽量处理前面的序列,中间不能断开,也就是现有的状态其实都是合法的.那么最后更新的节点肯定是根节点,那么我们只需要查询时lazy地保持与根节点不冲突即可.

我们可以非常方便地维护奇偶性,只需要异或运算.

p90

1.ceoi2003 赛车(the race)

1) 求逆序对数可以用树状数组解决.
2) 安利一下好写的二项堆.
3) 建议大神实现rank-pairing heap以增长rp.

2.可怜的奶牛

1) lrj的oibh已经不在了.
2) 这道题是按模n同余类分块牛分别处理每日产量最少牛.

p92

1) 待理解:prefixless语言.

黑书笔记

原文地址:http://www.cnblogs.com/tmzbot/p/4471437.html

这篇内容就是由软件教程库 小编为各位整理 原文链接:https://www.itjcku.com/9999/1091424.html

阅读全部内容


Tags:笔记

返回首页



推荐内容

//codeforces471D//kmp初学

// codeforces 471d // #includelt;cstdiogt; #includelt;cstrin ...

搭建基于域名虚拟主机

修改主配置文件 # cd /etc/httpd/conf.d/ # vim vhost.conf lt;virtu ...

Mysql5.6.24zip解压缩版配置及修改默认编码方法

win64位下载地址: http://dev.mysql.com/downloads/file.phpid=456319 ...

图片的预加载和按需加载

图片预加载 lt;!doctype htmlgt; lt;htmlgt; lt;headgt; lt;meta htt ...

iPhone/iPad程序怎么禁止自动休眠

//禁止自动休眠可以通过这一句话搞定:[uiapplication sharedapplication].idletim ...

普林斯顿《算法II》第一周学习笔记UndirectedGraph

普林斯顿的算法课是cousera上评价挺高的一门课,课程的教学语言用的是java,课程中的算法都会被封装成类的形式,对于 ...

headFirst学习笔记之九:迭代器与组合模式(5.1)

1.任务: 大新闻!对象村餐厅和对象村煎饼屋合并了!可以在同一个地方吃早饭和午饭了hohoho(有什么好开森的对象村的小 ...

IOSapplicationWillResignActive

一、挂起当有电话进来或者锁屏,这时你的应用程会挂起,在这时,uiapplicationdelegate委托会收到通知,调 ...

哥我要向前看了

七年前的五一节前的那个周六,我遇到生命中一个重要的人。虽然相处短暂,好梦不长,但是回忆丰满,念念不忘。 七年后的五一节, ...

GoldSmith第二章

uhf:特高频 300m-3000mhz shf:超高频 3g-30g 所有发射与接收的信号都是实信号(因为调制器的振荡 ...

动态规划总结【模板】

最长递增子序列 给定一个序列,找到最长子序列的长度,使得子序列中的所有元素被排序的顺序增加。 1.求最长递增子序列的 ...

HDUACM1103Flo'sRestaurant

分析:借助stl的min_element实现。每次更新最先被占用的桌子,具体见注释。 #includelt;iostre ...

【翻译自mos文章】Oracledb12c中,每次日志切换时,会改变alert_sid.log的权限

12c中,每次日志切换时,会改变alert_sid.log的权限 来源于: alert log file‘s perm ...

poj1988(并查集)

题意:有30000个木块,编号从1到30000,然后有两种操作m a b,把木块a所在的堆块放到木块b所在的堆块上,操作 ...

org.hibernate.exception.GenericJDBCException:Couldnotopenconnection

1、错误描述 org.hibernate.exception.genericjdbcexception: could ...

ubuntu下mysql导出数据

使用的是workbench,原因时workbench的导出工具mysqldump和mysql的版本不一致,这个时候手动指 ...

怎样看懂女人哪些最直接的肢体暗示,撒娇

主动拥抱。 拥抱是最简单却十分亲密的身体接触,女人在想亲热时,会主动寻求拥抱,向伴侣靠近。如果她躺在你的怀抱中,并用语言 ...

移动后端云平台Bmob介绍

对于移动端的独立开发者来说,最痛苦的事情莫过于搭建后台服务器。没有基础的还得从头学起,有技术的又要搭建维护后台,非常 ...

WAMP配置虚拟主机

问题背景:从网上下载了一个php项目a,a项目需要部署在网站的根目录下。配置虚拟主机可以解决这个问题。1.打开apach ...

java克隆测试

1.person类 1 //clone方法必须实现cloneable接口 2 public class perso ...

C++string中用于查找的find系列函数浅析

总述:以下所讲的所有的string查找函数,都有唯一的返回类型,那就是size_type,即一个无符号整数(按打印出来的 ...

Savingoutputofagrepintoafilewithcolors

19 down vote favorite 7 i need to save the result o ...

hibernate异常之QueryException

org.hibernate.queryexception: expected positional parameter ...

Redis的Python客户端redis-py的初步使用

1. 安装 sudo pip install redis sudo pip install hiredis pa ...

《构建高性能Web站点》笔记

书名:构建高性能web站点 出版社: 电子工业出版社 isbn:9787121170935 一 绪论 等待的时间: ( ...

制作OSX10.10.3启动安装U盘

1.获得install os xyosemite.app 2.准备一个8gb的u盘,用磁盘工具抹掉,格式默认的mac o ...

域名解析URL转发

url转发 转发功能:如果您没有一台独立的服务器(也就是没有一个独立的ip地址)或者您还有一个域名b,您想访问a域名时访 ...

instancetypeVSid

英文好的直接读下面链接的文章就好了: http://stackoverflow.com/questions/897222 ...

androidapp开发感想

这几天帮学长做app的时候,照着视频学了json数据的传递,接着遇到了问题,就是httpurlconnection会 ...

常用软件及注册码

vmware-workstation-full-11.0.0-2305329.exe m50ac-j034j-08l8a ...


本网站部分内容来自互联网,版权归原作者所有,文章内容仅代表原作者个人观点。如有侵权请联系我们删除 电子邮件 itjcku@foxmail.com