O(n)时间快速选择

如何在期望线性时间选出第i小的元素?
通过该调用快速排序的random_partition可以实现在平均O(n)时间内选出第i小的元素。
根本原因:这种方法实际上是对数组进行了局部的排序,每次只排序partition后的一半,因为将快速排序的平均时间O(nlogn)降到了O(n).严谨的数学证明请参见《算法导论》。
下面先给出算法的实现,然后叙述缺点及改进。

google code jam2016资格赛题解

A. Counting Sheep
小数据暴力呗。大数据也一样。。
B. Revenge of the Pancakes
小数据暴力呗。大数据没做。。
C. Coin Jam
小数据暴力呗。大数据没做。。
D. Fractiles
题意:一个序列由两种字符组成:L、G.给出k,c,s。表示序列初始长度k,变换了c次。每次变换:L的地方用最初始序列代替,G的地方用k个G代替。
现序列各个位置的值是看不到的,你可以选择查看其中的s个位置的值。问:能否通过小于等于s次查看,来推断出现序列是否包含G。
这题我是这样做的。小数据大数据一个做法。
如果查看一个位置发现是G,那么我们就知道序列是含有G的了,所以问题其实是在问:有没有一种查看的策略使得在查看的值都是L的情况下,可以断定序列必定没有G。
我们可以把整个变换的过程画出来,可以发现是一棵k叉树(注意一点这里我把原始序列的k个结点最为统一的“根结点”)。叶子节点是现序列。关键一点在于当得到了位置pos的值是L之后,我们就知道了pos位置的值是L之后,就知道了pos的父节点是L,它的父节点也是L。换言之,pos到树根的路径上的结点都是L。
那么为了尽可能通过一次查看得到最多信息,我们可以查看根节点的第二个子结点的第三个子结点的…………(一直到叶子结点)的值。这样就得到了min(c,k)个连续位置的值,接下来重复这个查看过程就行。
这个还是有个图比较好解释。。下次加个图。

linux内核模块编程笔记

最近因为实验室项目,开始接触了一点linux内核模块编程
内核编译选项.config所在路径:/usr/src/相应内核版本/.config
内核符号表:在编写内核模块的时候,因为LKM是动态加载到内核中,也就是说这时的内核是在内存中运行的,所以正确获取内核函数和变量的地址很重要。如果我们在内核模块中直接将地址写死,那么显然不通用,在另一个内核上可能地址就变了。内核符号表就是用于解决这个问题。每个内核都有其内核符号表,里面是内核导出的符号及其地址。我们编写的内核模块通过访问这个内核符号表就可以得到当前正在运行的内核的可用函数和变量的确切地址。
那么怎样使用内核未导出的符号呢?
我们可以使用kallsyms_lookup_name(char*)这个函数,该函数参数是符号名,返回unsigned long型的函数/变量地址。这个方法有个前提,那就是kallsyms_lookup_name(char*)这个符号本身是被内核导出的,所以要用CONFIG_KALLSYMS=y来编译内核,或者修改内核源码中的kallsyms.c文件,增加EXPORT_SYMBOL(kallsyms_lookup_name);手动将该符号导出
————————————————————————————————————————————————————————————————————————————
过程中的问题和要点:
linux内核的三种内存模型
page结构中的_count和_mapcount
_mapcount:在页表中每增加一个映射项,_mapcount就加1.初始值是-1

虚拟化笔记

VMM进程地址空间中存储了各个虚拟机具体的硬件环境(如PC值、EAX值等等,PC值指向guestOS的代码),guestOS在运行时(其实就是VMM将真实寄存器等硬件环境改为guestOS的环境,PC改为指向guestOS的代码,这样guestOS的代码就开始运行了),其代码是真正运行在真实cpu上的,由于guestOS是在ring3,所以执行特权指令时触发异常,VMM的异常处理模块截获异常,然后再做安排。

这几天发现自己一直以来有个特点,决定做一件事的时候犹豫起来没完没了。现在索性想简单点,既然还年轻,那么有喜欢的事情,就竭尽全力坚持到底就好了,不要想乱七八糟的问题。

关于圣诞节

不知道为什么今天心情真的不好,今天唯一的收获是学会了弹奏《you are my sunshine》,但是真的不适合在今天弹这么欢快的歌曲。感谢朋友的邀请,但是真的不想出去玩。晚上一个人去街上走了走,本来想一个人练下台球,好久没打了。怎么说呢,还是算了,本来平安夜那天决定以后认真去做心里决定的事情,但是这个愿望还是被一下子浇灭了,我太傻了。恩,就这样吧。lonely Christmas.
-
-
-
但是呢,我可以有更多时间去达成另一个目标,我要去我想去的那个地方。它一定会被实现。

Shortest Palindrome

leetcode的一道题
题意:给出一个字符串,只能在首部加上字符使其成为回文串,求所加字符数最少的方案。
这题以前搞acm的时候碰到过,如果是以前,就直接上KMP了。但是前面有道题是用manacher算法求字符串的最长回文子串。突然发现这题也可以用manacher来做,时间复杂度也是O(n)。
manacher确实是一种思路巧妙,代码简短的算法。
https://leetcode.com/problems/shortest-palindrome/

bestcoder#64 div1

还是做出两题。。
1001(hdu5586) Sum
题意:给出n个数,给出函数f(x),现在可以对连续的一段区间的数使用f(x)转换,也可以不用。问最后这n个数之和最大是多少.
简单dp。可以先对这n个数都使用f(x)得到新的数组b(设原数组为a),b[]-a[],得到数组c。对c[]求最大子串和,这个最大子串和就是对某一段数施加f(x)之后可以达到的最大增益。如果是负的,那么显然不应该进行f(x)的转换。a数组的和加上这个增益就是答案。

bestcoder#63 div1

第一次做div1,解出两道题,能做的也只有两道。但是第一题罚时有点厉害,一直不太相信需要高精度(因为output里写了integer。。)
1001(hdu5568) sequence2
一个整数序列有多少种长度为k的不同的递增子序列,两个子序列只要有一个元素对应位置不同就算不同。
如1 2 2有两个长度为2的不同子序列1 2和1 2(这两个2位置不同)
简单的dp题。dp[i][j]表示前i个数组成的序列中有多少个长度为j的不同子序列。
dp[i][j]=sigma(dp[t][j-1]),其中a[i]>a[t]。