MIT 6.828 Operating System Engineering 学习笔记

课程主页

这课稍微有点硬核…感觉基础稍微有些不扎实就做不下去orz.

网上似乎是有博客写了6.828的学习笔记,不过我更希望自己能够独立完成,二手的知识,谁知道是对的错的呢…况且课程本身给的参考资料应该还是足够多的。

环境的话,手头没有ubuntu系统,恰好半年前剁了阿里云的轻应用服务器,就在上面做吧。

为了这门课,我读了/计划读以下书籍(随时更新)。大概也是为了检查一遍自己的知识体系。

每个lab用到的网页形式的参考资料,会在每个lab的博客中分别给出。

最后,放一段《游褒禅山记》中的文字,与君共勉!

夫夷以近,则游者众;险以远,则至者少。而世之奇伟、瑰怪,非常之观,常在于险远,而人之所罕至焉,故非有志者不能至也。有志矣,不随以止也,然力不足者,亦不能至也。有志与力,而又不随以怠,至于幽暗昏惑而无物以相之,亦不能至也。然力足以至焉,于人为可讥,而在己为有悔;尽吾志也而不能至者,可以无悔矣,其孰能讥之乎?

 

codeforces round 530 div2

A,B,C:都很简单,不说了。

D:一棵树,给出树的结构,以及从树根到某个深度为偶数的节点的路径和,问能否构造一种所有节点点权和最小的树,输出最小点权和。

思路:

容易知道,如果想要点权和最小,那么尽可能让靠近树根的点承担更多的点权。

具体做法是,bfs,对于每个节点u,取其儿子中最小的S值求节点u的信息。

比赛的时候wa16…最后发现是答案要用long long存…因为单个路径和是<=1E9的。。多个加起来会超过int…  长时间不打连这种常见的坑都不敏感了啊。。。

 

codeforces hello 2019

好久没玩cf了,竟然还能涨分(虽然我用的小号Orz)

三题,D应该是数学+DP…数学实在是忘干净了。。。

前面三题大体还好,都是1A,不过因为没有提前配置环境。。耽误了一些时间。。。

A:给出一个扑克牌x,和另一个包含5个扑克牌的集合。问扑克牌x是否和扑克牌集合中至少一张扑克牌的花色或者数字相同。

不多说了。

B:一块钟表(只有一个指针),初始指向12点,需要拨动指针恰好n次(n<=15),每次可能顺时针,也可能逆时针,拨动的角度范围在[1,180],问是否有一种方案,使得拨动n次后,指针回到12点。

思路:观察下数据范围,n最大才15,最多也不过2^15的情况…既然如此,不如暴力。

枚举的话我记得有三种方法来着。。。但是已经不记得怎么写了。。所以用了最朴素的办法。。。

C: 给出n(n<=1E5)个括号序列,括号序列可能不合法,现在要从这n个括号序列中,组成尽可能多的有序二元组,使得有序二元组的括号序列合法,并且每个括号序列只能出现在一个有序二元组中,现在问最多能组成多少这样的有序二元组。

思路:我们先考虑一下怎样的两个括号序列组成的有序二元组才是合法的有序序列。容易想到的是,如果两个括号序列本身都是合法的,那么组合在一起也一定是合法的。进一步,对于本身不合法的括号序列,容易知道,其必须只有一种没有完成匹配的括号方向,且该括号方向的数量与相反括号方向的数量相同,才能完成匹配。

因此做法是,对于括号序列预处理,得到该括号序列的状态(本身匹配为0,正数代表'(‘的个数,负数代表’)’的个数,如果有两个方向同时存在,则直接舍弃掉,因为这种括号序列不可能组成合法的括号序列。预处理之后,用multiset搞一下。

代码写得比较乱…flag存的时候其实没必要存index…

D:初始一个数n(n<=1E15),k次操作,每次操作等概率将当前的数变为其因子中的一个。问k次操作之后,结果的期望是多少。

在@适牛的指导下,以及参考了官方题解。。写了出来。。

dp还是太弱了。。。。

比较重要的一点是,不需要考虑所有因子,只需要考虑质因子。

质因子的个数不超过50个(因为 2^50 > 1E15)

另外一个重要的是,对于每一个质因子的概率是积性函数,可以乘在一起。

因此问题变成了,对于一个质因子唯一的n,如何算所求的期望。

我们考虑dp[i][j]表示第i次操作后,质因子还剩j个的概率。

显然dp[0][tot]=1,其中 p^tot = n,p为某个质因子。

转移方程为:

dp[i][j] = sum(dp[i-1][jj]) (j=<jj<=tot)

然后最后结果的期望就是:sum(dp[k][j]*p^j) (0=<j<=tot)

还有一点,由于题目的输出要求,需要用到费马小定理求个逆元。。。

逆元相关的参考 acdreamer的博客。。。