2018秋招总结


秋招终于结束了,趁着还有些记忆写下这篇面经,希望对学弟学妹有所帮助。

首先先介绍一下个人背景,任何面试总结脱离了作者的背景都可能误导读者。本人本科期间参加了一年多(从入HDU校队开始算)ACM/ICPC比赛,最好成绩是区域赛银牌。硕士在浙江大学体系结构实验室,主要研究linux内核和虚拟化相关的东西。

然后列一下我主要投的公司和offer情况。我投递的公司不多,如下:

(注:sp=special 不确定是否是special offer的我都标了offer,其中的创业公司都是sp offer

需要注意的一点是,因为一些原因,本文不打算详细叙述面试过程中的具体题目。

1.微信:

微信是我最早拿到的一个offer,因为是实习转正。实习面试分3轮,2轮技术面+1轮hr面。第一面技术面之前会给30分钟做4/5道算法题,写在一张A4纸上,题目比较简单。然后开始和面试官唠嗑,第一面基本上是我在讲简历上的项目,印象中没提什么问题。第二面问了一些操作系统和算法的基础知识,不难。然后开始了在广州的实习,这次实习对我帮助很大,我感觉学到很多东西。

实习是在基础消息组,实际实习时间1个月,完成了一个c++内存泄露检测工具,由于业务需求,所以检测泄漏的时候用了一种比较创新的方法,特别是针对协程做了优化。当然这里面有同事们的帮助。由于实习面试、实习表现以及后续转正面试成绩很不错,进入了技术类实习生前两名,所以有幸参加了技术大咖的面试,不过遗憾的是面试挂掉了。

总的来说,微信的经历对我培养在强压力下工作的能力很有帮助,由于入职较晚,离考核只有一个月时间(最开始通知是三个星期),所以基本上那一个月非常忙。不过令人欣慰的是最后写出来的工具确实发挥了作用,检测出一些微信业务代码中的陈年内存泄露。特别是检测出了gperftools中的一个bug,可惜新版本已经fix了。

微信的用户量很大,但其实开发团队相对来说很小,所以很多地方有点像创业公司。招聘门槛也比较高,基本上从我了解到的信息来说,腾讯内部转岗都很难进。待遇上来讲挺不错,推荐大家前往。

2.Hulu Beijing

Hulu也是实习转正,不过是去年G20的时候去实习的。

实习面试:实习面试分三面,因为我在杭州,所以都是电面。每一面都是算法题。

转正面试:Hulu的转正面试是需要先提名的,一般来讲由你实习时候的manager发起提名。面试分3轮,因为人在杭州所以也是skype面试。2轮技术面+1轮boss面。2轮技术面都是算法,在线做题题目不难。

总体感觉,一般如果你申请的是SDE,那么面试是在一个共享文档上写代码,感觉我遇到的题都不难,题目比较注重基本功的考察。但是也有同学遇到比较难的题,这个应该和面试官有关,但是总体而言Hulu目前的面试难度没有五六年之前传说级那么难了。

总结:Hulu是家很不错的公司,技术实力很强。这一点从北京研发中心的员工构成可窥一斑,你身边会有大量清北的同事,甚至是姚班的大神。交流起来会比较顺畅。

3.阿里巴巴

阿里我投的是阿里云,让以前在阿里实习时的同事内推了一下。面试(我记得)分为4面,3轮技术+1轮hr。第一面面试问了我实验室的项目,然后一些系统方面的基础知识。最后写了一道基础的编程题。二面问了我除了内存相关的东西,对linux内核还有哪些了解之类的问题,由于对内核其他方面不是很了解,答的比较尴尬。最后问了OS中的一个基础题,我没答好。三面是交叉面,面试官好像是阿里云数据库团队的。具体问了啥已经忘了基本上是问各方面的基础知识。由于数据库我不是很懂,聊不起来。

总结:总的感觉是阿里云很重视你的既有经验,特别是在某个领域的深度,面试过程中很看重基本功,编程方面基本没问,可能是因为我简历上写了acm经历的缘故。阿里云现在还是比较缺人的,因为这几年发展的很好。我投的是内核团队也就是早前的淘宝内核组。面试通过后,会认真和你交流,实际选组比较自由,当我表达对分布式有兴趣之后,也让块存储的同事和我交流了,总之会比较尊重你的选择。

4.网易游戏

网易游戏让实验室学长内推了一下,由于在hihocoder上做了几场offer收割赛成绩不错,所以免去了在线笔试。onsite面试在网易杭州园区,分为30分钟的白板(纸上)写题+2轮面试。白板写题部分我遇到的是实现LRU Cache,我是用unordered_map+双向链表来做的,leetcode上有原题。然后是面试,面试时间很长,问了很多东西,首先是LRU Cache这题,review代码之后问我用单链表怎么做,然后还有OS、network、database、data structure/algorithm方面的一些基础。问了最长公共子序列,秒杀,面试官也笑了,觉得这题不该问。。还有一题是给出一个结构体的定义,现在已知指向该结构体的一个实例中的一个成员的指针,求出该实例的起始内存地址。其实这是linux内核中的链表经常用的一个技巧,对应的宏叫container_of,但是面试时候一直没想起来是怎么做的,后来发现关键点是把常数强转为指向结构体的指针,这样就可以知道给出的成员与结构体起始位置的偏移量。另外还有一题是告诉你地图上有很多怪物和玩家,用二维坐标表示,怪物和玩家都是运动的,当玩家距离怪物距离R以内时会察觉并攻击,问怎么维护这个关系。这题没答好。二面没有具体考察,主要是问我在微信的项目,对实习过的各个公司的看法等等问题。

总结:如果喜欢玩游戏做游戏,去这家不会有错。

5.依图科技

依图是一家人工智能领域的创业公司,第一次听说是去年CAD一位学长去面试了,和我说很不错,后来一位本科同学也跳槽去了,问了下感觉不错就去面了。我投了算法工程师和后台开发两个岗位,其实我并不懂机器学习,但是当时有转机器学习的想法。

依图面试

面试分为4轮,3轮技术面+1轮大佬面。第一轮是算法面,个人感觉这轮面试是我整个秋招过程中面试难度最大的两轮面试之一,另一轮是微软的第一面。当然题目仍然是leetcode水平,并没有真的很难。第二轮有点忘了,只记得问了道非常有意思的智力题,回答的不错。第三轮没问算法,问了system design:如何设计一个微博系统,用户10亿,DAU 1亿。听完有点懵,以前没想过这些问题。这一面答的不好。基本是是在提示下一点点前进。这一轮收获很大,以前从没考虑过这种问题。这样一个系统,需要哪些功能,QPS怎么假设,数据表怎么设计,需要多少台服务器,业务需要多少台,存储需要多少台,每台配置如何,何种外存,ssd还是机械盘,机械盘转速多少,怎么算出具体iops,容灾怎么做,网络瓶颈等等,非常具体。

总结:依图现在发展很好,而且薪水给的心服口服。

6.拼多多

同学面完后向hr推荐了我,听HR介绍了之后感觉公司不错就投了简历。

笔试题很不错,不是都很简单那种。其中有一道是机器人扫地的题目,让人感觉耳目一新。

onsite分两轮,第一轮面试官尝试问了我一些网络方面的问题,因为我这块不熟,所以一直尬聊。最后做了一道dp题,回答的比较好

总结:

7.google

参加了kickstart笔试,onsite是在上海。第一轮比较顺利,第二轮时候沟通有点问题,面试官在回答我clearify的问题时给了错误的条件。

总结:google题不难但是一定要注意理解题意,做题前和面试官沟通清楚。如果面试官自己也搞错了,那就没办法了。google今年似乎只提供了北京和上海的岗位,无法申请海外岗。

8.facebook

找了学长内推但是联系我的是facebook London的hr说可以提供伦敦那边的机会,很可惜电面挂了。面试题是leetcode难度,但是第二题题目理解错了,写完之后又重写,最后时间不够了。

总结:fb的hr做事非常高效。面试前发了很多相关资料,回邮件也非常快。面试的时候我是边说边写代码的,感觉其实是有难度的,因为很多时候头脑中有一个中文转英文的过程会打断思考。现在我的看法是先说完思路,写代码的时候就不要解释了,写完之后再对必要之处进行解释从我的经历来推测今年fb可能是不会为处于美国之外的外国候选者(应届毕业生)sponsor H1B。目前H1B政策前景不明的情况下,没有美国学位的候选人劣势很大。如果真想去这家,还是去美国读个研吧。

9.微软西雅图

这是我今年秋招的最后一个面试。最后也选择了这个offer。

由于google和facebook纷纷挂掉导致心情很差。痛定思痛,我打算好好复习准备微软的面试。于是开始刷leetcode的median题,我发现对于acm选手来说,hard题并不算难,因为很多都是acm竞赛中的一些套路。反而一些median题思路清奇,万一遇到又没做过的话临场很难想到最优解。于是面试前几个星期,我认真刷了array、linkedlist、tree、string等几个专题。并且复习了以前打比赛时候的一些算法,比如莫队分块、BIT、线段树、manacher、最小表示法等比较简单好写又非常实用的算法。然而这些都没有什么卵用。事实证明,好好刷leetcode就好了。

微软面试是在上海,面试分4面,都是英文面。算法部分不是很难。但是设计题感觉没答好。不过最后还是拿到了offer。由于签了NDA,具体题目就不透露了。

总结:据我目前信息来看,MS是今年唯一一家为中国大陆应届毕业生提供美国岗位的公司,可以说是良心企业在中国大陆招收的人很少,个人估计在20人以内。

10.Jane Street Capital

JSC不是我接触的第一家金融类公司,我记得去年去上海面试过JP Morgen的quant岗(实习),话说JPMorgen的面试非常有意思,面了整整一天并且全是英文面,到最后真的够呛。话说回来,JSC是美国一家对冲基金,在NYC、HK、London都有office。最早知道这家公司是因为浙大以前有个大牛叫崔天翼——也就是网络上背包九讲的作者DD(据说是他高中时候写的。。)拒了google的offer去了这家公司。后来姚班的刘佳倩在blog中也提到了这家公司。据说JSC的bar非常高,而且hack氛围很好而且薪水逆天。抱着试一试万一成功了岂不是很爽重在参与的心态我在官网投递了简历。我投的是软件开发岗,一星期后hr打电话来聊了5分钟,询问了一些背景情况,说如果有匹配的岗位会发起面试。几天后发来拒信。。。

总结:这家的软件开发岗位招的人极少,我感觉有些年份是不招人的,并且候选人的各方面要求都非常高,可以说是精英主义了。而且据说会OCaml并不会为你加分,实际上对方不在乎你会什么,有哪些技能等,而是看重你的聪明程度这个公司的信息较少,相关的面经可以看:

http://blog.sina.com.cn/s/blog_52f526870102wkca.html

http://blog.sina.com.cn/s/blog_72f8a5d00102w6p3.html

11,其他还投递了一些公司,比如今日头条,但是面试流程太诡异了。很早就让同学内推了,但是一直没任何消息。结果过了一个月hr和我说在人才库中看到了我的简历也就是说我简历挂了然后又内推了一次。之后头条到浙大宣讲,当场笔试。做完又没消息了。当时hr说只要以前内推过的就可以不需要当场再投简历我就没投。但是当场投的好像去面试了。。后来11月多了终于联系我面试。。因为已经决定去微软了,于是拒了面试。

总的来讲,找工作不仅是看实力,运气也很重要,但是实力是前提。人总有发挥不好的时候,但机会只有一次,所以better safe than sorry,准备越充足越好。很多学弟学妹咨询我赴美工作相关的问题,有些问题我自己也没有答案,所以很难给出令人信服的解答。但是一些方向性和操作性的问题我还是有点经验的,欢迎与我交流。

        另一方面,从目前的形势上来说,国内在一些方面是领先美国的,而且现在国内的待遇也上来了(很多创业公司开出了很高的offer,和美国那边差距在缩小。所以出国并不一定就好,关键是要找到适合自己的道路。就到这里吧,以后有机会可以再聊聊我的一些实习经历。

        btw,最近在做区块链,主要是智能合约相关的研究。有兴趣有时间的同学可以一起交流。

cf#369 div2

很久没做题了,昨天这场codeforces时间比较早就做了一下。A
A.Bus to Udayland x5233
签到题

#include<stdio.h>
#include<string.h>
char mat[1000+10][5];
int main()
{
    int i,j;
    int n;
    char tmp;
    while(~scanf("%d",&n))
    {
        getchar();
        bool flag=0;
        for(i=1;i<=n;i++)
        {
            scanf("%c%c%c%c%c",&mat[i][1],&mat[i][2],&tmp,&mat[i][3],&mat[i][4]);
            getchar();
            if(flag) continue;
            if((mat[i][1]=='O') && (mat[i][2]=='O'))
            {
                mat[i][1]='+';mat[i][2]='+';
                flag=1;
                continue;
            }
            if((mat[i][3]=='O') && (mat[i][4]=='O'))
            {
                mat[i][3]='+';mat[i][4]='+';
                flag=1;
                continue;
            }
        }
        if(!flag) {printf("NO\n");continue;}
        printf("YES\n");
        for(i=1;i<=n;i++)
            printf("%c%c|%c%c\n",mat[i][1],mat[i][2],mat[i][3],mat[i][4]);
    }
    return 0;
}

B.Chris and Magic Square x3112
也很简单

#include<stdio.h>
#include<string.h>
typedef long long ll;
ll a[510][510];
int main()
{
    int i,j;
    int n;
    while(~scanf("%d",&n))
    {
        int x,y;
        int flag=1;
        for(i=1;i<=n;i++)
            for(j=1;j<=n;j++)
            {
                scanf("%I64d",&a[i][j]);
                if(!a[i][j]) {x=i,y=j;}
            }
        if(n==1) {printf("1\n");continue;}
        ll ans=-1,tmp=0;
        for(i=1;i<=n;i++)
        {
            if(i==x) continue;
            for(j=1;j<=n;j++) tmp+=a[i][j];
            if(ans==-1) {ans=tmp;tmp=0;continue;}

            if(tmp!=ans)
            {
                flag=0;
                break;
            }
            tmp=0;
        }
        if(!flag){printf("-1\n");continue;}
        tmp=0;
        for(j=1;j<=n;j++)
        {
            if(j==y) continue;
            for(i=1;i<=n;i++) tmp+=a[i][j];
            if(tmp!=ans)
            {
                flag=0;
                break;
            }
            tmp=0;
        }
        if(!flag){printf("-1\n");continue;}
        tmp=0;
        for(i=1;i<=n;i++) tmp+=a[i][y];
        ll ret1=ans-tmp;
        tmp=0;
        for(j=1;j<=n;j++) tmp+=a[x][j];
        ll ret2=ans-tmp;
        if(ret1!=ret2 || ret1<1){printf("-1\n");continue;}
        a[x][y]=ret1;
        ll c1=0,c2=0;
        for(i=1;i<=n;i++) c1+=a[i][i],c2+=a[i][n+1-i];
        if(c1!=c2 || c1!=ans) {printf("-1\n");continue;}
        printf("%I64d\n",ret1);
    }
    return 0;
}

C.Coloring Trees x1710
题意:有一排树。每棵树有一种颜色或者还没被涂色,如果一棵树原本就有颜色,那么不能改色,只有没被上色的树可以涂颜色。相邻且颜色相同的树属于同一组。p[i][j]表示将第i棵树涂成颜色j的代价。问:通过上色将这些树分成k组的最小代价是多少?
树的数量、颜色的数量均<=100
序列?分组?最优解?直接往dp上去想
dp[i][j][t]表示将前i个分成t组且第i个涂成颜色j的最小代价。
转移如下:
(1)如果第i个是已经有颜色,且颜色为a[i]
dp[i][a[i]][t]=min(dp[i-1][a[i]][t],min of dp[i-1][not a[i]][t-1])(注意t==1时后一项时没有的)
(2)如果第i个没有颜色
dp[i][j][t]=min(dp[i-1][j][t],min of dp[i-1][not j][t-1])+p[i][j];
初始化dp[1][j][1]时也要如上分类讨论,其余初始化为inf。
时间复杂度O(n*m*n*n), 大概10^8数量级,能过。。。
这题耗费了比较多的时间,现在熟练度下降很多~

#include<stdio.h>
#include<string.h>
typedef long long ll;
const ll inf=100000000000000000LL;
int n,m,k,t,s;
ll dp[110][110][110],p[110][110];
int a[110];
ll min(ll a,ll b){return a<b?a:b;}
int main()
{
    int i,j;
    while(~scanf("%d%d%d",&n,&m,&k))
    {
        for(i=1;i<=n;i++) scanf("%d",&a[i]);
        for(i=1;i<=n;i++)
            for(j=1;j<=m;j++)
                scanf("%I64d",&p[i][j]);
        if(k>n){printf("-1\n");continue;}
        for(i=1;i<=n;i++)
            for(j=1;j<=m;j++)
                for(t=1;t<=n;t++)
                    dp[i][j][t]=inf;
        if(a[1]!=0)
        {
            dp[1][a[1]][1]=0;
        }
        else
        {
            for(i=1;i<=m;i++)
                dp[1][i][1]=p[1][i];
        }
        for(i=2;i<=n;i++)
            for(j=1;j<=m;j++)
                for(t=1;t<=k;t++)
                {
                    if(a[i]!=0)
                    {
                        if(j!=a[i]) continue;
                        ll tmp=inf;
                        dp[i][a[i]][t]=dp[i-1][a[i]][t];
                        if(t>1){
                            for(s=1;s<=m;s++)
                            {
                                if(s==a[i]) continue;
                                if(dp[i-1][s][t-1]<tmp) tmp=dp[i-1][s][t-1];
                            }
                        }
                        dp[i][a[i]][t]=min(dp[i][a[i]][t],tmp);
                        continue;
                    }
                    ll tmp=inf;
                    dp[i][j][t]=dp[i-1][j][t]+p[i][j];
                    if(t>1)
                    {
                        for(s=1;s<=m;s++)
                        {
                            if(s==j) continue;
                             if(dp[i-1][s][t-1]+p[i][j]<tmp) tmp=dp[i-1][s][t-1]+p[i][j];
                        }
                    }
                    dp[i][j][t]=min(dp[i][j][t],tmp);
                }
        ll ans=inf;
        for(i=1;i<=m;i++)
            ans=min(ans,dp[n][i][k]);
        if(ans<inf) printf("%I64d\n",ans);
        else printf("-1\n");
    }
    return 0;
}

D.Directed Roads x948
这题其实比上一题简单,个人感觉。
n个点,n条边。没有圈(自环)。每条弧可以反向,问有多少种将边反向的方案可以使得图没有环,两个方案不同当且仅当两个方案中至少存在一条不同的弧。
n<=2*10^5
容易想到对于一个环中的弧,只要不全部反向或者一条弧都不反向,其它方案都可以去掉改环。所以方案数是(2^len)-2.len 是环中弧的数量。
对于不在环中的弧,选不选无所谓,所以针对这些弧,所有方案都行, 方案数是2^k.k是这类弧的数量。最后乘法原理。
最后答案:∏((2^len)-2)*(2^k)
∏ 表示连乘
可见最后是一个简单的快速幂模mod

-_-#速度太慢了,这题没来得及submit。。。

#include<stdio.h>
#include<string.h>
typedef long long ll;
const int mod=(1e9)+7;
int n;
int a[200000+10];
int order[200000+10];
ll cal(int k)
{
    ll ans=1,p=2;
    while(k)
    {
        if(k%2)
        {
            ans=(ans*p)%mod;
            k--;
        }
        p=(p*p)%mod;
        k/=2;
    }
    return ans;
}
int main()
{
    int i,j;
    while(~scanf("%d",&n))
    {
        for(i=1;i<=n;i++) scanf("%d",&a[i]);
        memset(order,0,sizeof(int)*(n+5));
        int cnt=0;
        ll ans=1;
        int m=n;
        for(i=1;i<=n;i++)
        {
            if(order[i]) continue;
            j=i;
            int end=cnt+1;
            while(!order[j])
            {
                //printf("%d ",j);
                order[j]=++cnt;
                end=order[j];
                j=a[j];
            }
            if(order[j]<order[i]) continue;
            int len=end-order[j]+1;
            //printf("%d\n",len);
            m-=len;
            ans=(ans*((cal(len)-2+mod)%mod))%mod;
        }
        ans=(ans*cal(m))%mod;
        printf("%I64d\n",ans);

    }
    return 0;
}

E.ZS and The Birthday Paradox x241

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)个连续位置的值,接下来重复这个查看过程就行。
这个还是有个图比较好解释。。下次加个图。

#include<stdio.h>
#include<string.h>
typedef long long ll;
ll a[110];
ll ans[110],cnt;
inline ll min(ll a,ll b){return a<b?a:b;}
int main()
{
    //freopen("D-large.in","r",stdin);
    //freopen("D-large.out","w",stdout);
    ll i,j;
    int k,c,s;
    int t,cases=0;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d%d%d",&k,&c,&s);
        printf("Case #%d:",++cases);
        if(c==1)
        {
            if(s<k) {printf(" IMPOSSIBLE\n");continue;}
            for(i=1;i<=k;i++) printf(" %d",i);
            printf("\n");
            continue;
        }
        if(k==1)
        {
            if(s<k) {printf(" IMPOSSIBLE\n");continue;}
            printf(" 1\n");continue;
        }
        cnt=0;
        a[0]=1;a[1]=k;
        for(i=2;i<=c;i++)
            a[i]=a[i-1]*(ll)k;
        for(i=1;i<=k;)
        {
            ll tmp=0;
            for(j=-1;j<=c-2;j++)
            {
                if(i+j+1<=k)
                    tmp+=(i+j)*a1;
                else
                    tmp+=(k-1)*a1;
            }
            ans[++cnt]=tmp+1;
            i+=min(c,k-i+1);
        }
        if(s<cnt) {printf(" IMPOSSIBLE\n");continue;}
        for(i=1;i<=cnt;i++) printf(" %I64d",ans[i]);
        printf("\n");
    }

    return 0;
}

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

使用page_address之后发现所有页帧的虚拟地址都是在内核地址空间?what the fuck
__________________________
x86_64的内存地址空间需要研究
——————————————————————————————
读某个内核虚拟地址出错。BUG: unable to handle kernel paging request at ffff880020000000

找到读取物理内存内容的方法了,如下:
前面失败的原因是较新版本的linux内核限制了对/dev/mem的读取,默认只能读取前1M字节的数据。解决方法时修改.config中的CONFIG_X86_PAT=n,CONFIG_STRICT_DEVMEM=n.然后重新编译内核
编译内核过程(抱歉,不要嫌弃我菜,我经常忘。所以记一下)
make menuconfig生成.config(如果要编译的内核和现有内核版本相同,可以从/boot/config-版本号 copy一份放到源码根目录)
make modules 编译一下内核模块
make modules_install 安装内核模块(到/lib/modules目录)
make install 安装内核(copy 生成的内核映像到/boot下面,修改gurb启动项等)

由于/dev/mem是整个物理地址空间的映像,包括了IO端口、ROM的地址,并不全是RAM,所以要先读取/proc/iomem文件得到System RAM的地址分布,之后读取System RAM的部分即可
代码如下,注意不要读到RAM之外的地方,可能会导致出错。

#include<stdio.h>
#include<string.h>
#include<unistd.h>
#include<sys/mman.h>
#include<sys/types.h>
#include<sys/stat.h>
#include<fcntl.h>
typedef long long ll;
const ll max_read=10000000;
char buf[max_read+10];
typedef struct Node{
	ll be,en;
}Node;
Node node[10010];
int cnt;
int main()
{
	freopen("/proc/iomem","r",stdin);
	cnt=0;
	int i;
	while(gets(buf))
	{
		int len=strlen(buf);
        if(strstr(buf,"System RAM")==NULL) continue;
        char *s=buf;
        strtok(s,":");
        printf("%s\n",s);
        char tmp;
        cnt++;
        sscanf(s,"%llx-%llx",&node[cnt].be,&node[cnt].en);
    }
	
    int fdmem,fdout;
    fdmem=open("/dev/mem", O_RDWR|O_SYNC);
	fdout=open("memdump.txt",O_CREAT|O_RDWR|O_SYNC);
    if ((fdmem == -1) || (fdout==-1))
    {
		printf("open err\n");
        return -1;
    }
	for(i=1;i<=cnt;i++)
    {
        ll be=node[i].be,en=node[i].en;
        lseek(fdmem,be,SEEK_SET);
        printf("read %llx-%llx\n",be,en);
        while(1)
        {
            if(en-be+1<=max_read)
            {
                read(fdmem,buf,en-be+1);
                printf("read %llx-%llx\n",be,en);
                write(fdout,buf,en-be+1);
                break;

            }
            read(fdmem,buf,max_read);
            printf("read %llx-%llx\n",be,be+max_read-1);
            write(fdout,buf,max_read);
            be+=max_read;
        }
    }
	close(fdmem);
	close(fdout);
	
    return 0;
}

虚拟化笔记

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

设备模拟

1.guestOS中的驱动程序称为前端(Front-End,FE)设备驱动,而VMM中的驱动程序为后端(Back-End,BE)设备驱动。

硬件辅助虚拟化:硬件本身加入虚拟化功能,就可以截获操作系统对敏感指令的执行或者对敏感资源的访问,从而通过异常的方式报告给VMM,这样就解决了虚拟化的问题。

硬件辅助虚拟化的典型:Intel的VT-x技术。VT-x技术在处理器上引入了一个新的执行模式用于运行虚拟机。当虚拟机执行在这个特殊模式中时,它仍然面对的是一套完整的处理器寄存器集合和执行环境,只是任何特权操作都会被处理器截获并报告给VMM

linux伙伴系统

前段时间由于实验室相关项目的需要+OS课的presentation,看了linux2.6.24内核伙伴系统的源码。写一下总结。

引言
    伙伴系统作为一种古老而历经检验的系统,也被Linux内核所采用。伙伴系统的提出是为了管理和记录内存的分配和使用。在X86架构的Linux内核版本 2.6.24及之后,Linux对原本的伙伴系统做了改进,在原来的基础上加入了反碎片机制,使得内核能够更好的管理内存的外部碎片。
    本文的分析针对X86架构。首先介绍了什么是伙伴系统,以及伙伴系统的相关数据结构。然后分析了X86架构上Linux 2.6.24这个版本对伙伴系统做的改进(加入了反碎片机制)。最后从源代码出发,深入揭示了伙伴系统的内核工作流程。
什么是伙伴系统
    伙伴系统的宗旨就是用最小的内存块来满足内核对于内存的请求。在最初,只有一个块,也就是整个内存,假如为1M大小,而允许的最小块为64K,那么当我们申请一块200K大小的内存时,就要先将1M的块分裂成两等分,各为512K,这两份之间的关系就称为伙伴,然后再将第一个512K的内存块分裂成两等分,各为256K,将第一个256K的内存块分配给内存,这样就是一个分配的过程。下面我们结合示意图来了解伙伴系统分配和回收内存块的过程。
图1 伙伴系统示意图
1. 初始化时,系统拥有1M的连续内存,允许的最小的内存块为64K,图中白色的部分为空闲的内存块,着色的代表分配出去了的内存块。
2. 程序A申请一块大小为34K的内存,对应的order为0,即2^0=1个最小内存块
   2.1 系统中不存在order 0(64K)的内存块,因此order 4(1M)的内存块分裂成两个order 3的内存块(512K)
   2.2 仍然没有order 0的内存块,因此order 3的内存块分裂成两个order 2的内存块(256K)
   2.3 仍然没有order 0的内存块,因此order 2的内存块分裂成两个order 1的内存块(128K)
   2.4 仍然没有order 0的内存块,因此order 1的内存块分裂成两个order 0的内存块(64K)
   2.5 找到了order 0的内存块,将其中的一个分配给程序A,现在伙伴系统的内存为一个order 0的内存块,一个order 1的内存块,一个order 2的内存块以及一个order 3的内存块
3.程序B申请一块大小为66K的内存,对应的order为1,即2^1=2个最小内存块,由于系统中正好存在一个order 1的内存块,所以直接用来分配
4 程序C申请一块大小为35K的内存,对应的order为0,同样由于系统中正好存在一个order 0的内存块,直接用来分配
5 程序D申请一块大小为67K的内存,对应的order为1
   5.1 系统中不存在order 1的内存块,于是将order 2的内存块分裂成两块order 1的内存块
   5.2 找到order 1的内存块,进行分配
6 程序B释放了它申请的内存,即一个order 1的内存块
7 程序D释放了它申请的内存
   7.1 一个order 1的内存块回收到内存当中
   7.2由于该内存块的伙伴也是空闲的,因此两个order 1的内存块合并成一个order 2的内存块
8 程序A释放了它申请的内存,即一个order 0的内存块
9 程序C释放了它申请的内存
   9.1 一个order 0的内存块被释放
   9.2 两个order 0伙伴块都是空闲的,进行合并,生成一个order 1的内存块m
   9.3 两个order 1伙伴块都是空闲的,进行合并,生成一个order 2的内存块
   9.4 两个order 2伙伴块都是空闲的,进行合并,生成一个order 3的内存块
   9.5 两个order 3伙伴块都是空闲的,进行合并,生成一个order 4的内存块
 从上述例子中,我们可以总结出伙伴系统分配内存释放内存的算法:
分配内存
1.寻找大小合适的内存块(大于等于所需大小并且最接近2的幂)
  • 1.1.如果找到了,分配给应用程序
  • 1.2.如果没找到,分出合适的内存块
  • 1.2.1.对半分离出高于所需大小的空闲内存块
  • 1.2.2.如果分到最低限度,分配这个大小
  • 1.2.3.回溯到步骤1
  • 1.2.4.重复该步骤直到一个合适的块
释放内存
1.释放该内存块
  • 1.1.寻找相邻的块,看其是否释放了。
  • 1.2.如果相邻块也释放了,合并这两个块,重复上述步骤直到遇上未释放的相邻块,或者达到最高上限(即所有内存都释放了)
伙伴系统的数据结构
    我们首先来看一下伙伴系统相关的数据结构,首先看一下free_area。
<include/linux/mmzone.h>
struct free_area {
    struct list_head    free_list;
    unsigned long     nr_free;
};
    其中nr_free指定了当前内存区中空闲页块的数目。free_list是用于链接空闲页的链表,页链表包含大小相同的连续内存区。是伙伴系统里非常重要的概念,它描述了内存分配的数量单位,例如2^order,order就是阶,并且其范围从0到MAX_ORDER。order通常设置为11,这意味着一次分配可以请求的页的最大数是2^11=2048。
    free_area[]数组中的各个元素索引也可以理解为索引,第0个链表代表内存管理区里的单页,第1个链表代表内存管理区里的两页。从下图可以看出,free_area[0]每个元素代表单个页帧,free_area[2]的每个元素代表4个页帧。
伙伴系统的反碎片机制
    本文研究的是X86平台Linux2.6.24版本的内核。在该版本中,对于伙伴系统加入了反碎片机制(anti-fragmentation),试图从最初开始就尽可能防止碎片。
    首先我们必须知道,内核将已分配页分为以下三种不同的类型:
  不可移动页(UNMOVABLE): 这些页在内存中有固定的位置,不能够移动。
  可回收页(RECLAIMABLE): 这些页不能移动,但可以删除。内核在回收页占据了太多的内存时或者内存短缺时进行页面回收。
  可移动页(MOVABLE): 这些页可以任意移动,用户空间应用程序使用的页都属于该类别。它们是通过页表映射的。当它们移动到新的位置,页表项也会相应的更新。
  在内存子系统初始化期间,所有的页都被标记为可移动的。在启动期间,核心内核分配的内存是不可移动的。此时内核的策略是分配一个尽可能大的连续内存块,将其从可移动列表转换到不可移动列表。原因如下:
   例如:现有一块可移动的具有16页的连续空闲内存块。当内核需要分配1页不可移动内存页时。分配器选择后8页(而不是一页)转移到不可移动列表,然后从 不可移动列表中选择1页用于分配。如果内核又需要分配1页不可移动内存页则从不可移动列表中选择一页用于分配,下图显示了进行4次分配后内存的分布。
        但如果内核只选择1页用于分配将其加入到不可移动列表,当下次需要分配时又选择一页加入到不可移动列表,下图显示了按照这种方式进行4次分配后内存的分布。
        因此,当没有满足可用于分配的不可移动空闲块时,分配器会在可移动列表中迁移一个尽可能大的连续内存块给不可移动列表。这样避免了启动期间内核分配的内存散列到物理内存各处,从而使其他类型的内存分配免受碎片的干扰。
        内核定义了一些宏来表示不同的迁移类型:
<include/linux/mmzone.h>
    #define MIGRATE_UNMOVABLE     0
    #define MIGRATE_RECLAIMABLE   1
    #define MIGRATE_MOVABLE       2
    #define MIGRATE_RESERVE       3
    #define MIGRATE_ISOLATE       4 /*用于跨越NUMA结点移动物理内存页*/
    #define MIGRATE_TYPES         5
    2.6.24版本对伙伴系统结构的主要调整,是将空闲列表分解成MIGRATE_TYPE个列表,数据结构如下(注意变化的部分):
<include/linux/mmzone.h>
struct free_area {
    struct list_head    free_list[MIGRATE_TYPE];
    unsigned long     nr_free;
};
    也就是说每一个free_area又根据MIGRATE_TYPE分成了5种类型,每种类型里面分别都有一个head_list结构体。
    如果内核无法满足针对某一给定迁移类型的分配请求的话,内核提供了一个备用列表,规定了在指定列表中无法满足分配请求时,接下来应使用哪一种迁移类型:
static int fallbacks[MIGRATE_TYPES][MIGRATE_TYPES-1] = {  
  • [MIGRATE_UNMOVABLE] = { MIGRATE_RECLAIMABLE, MIGRATE_MOVABLE,   MIGRATE_RESERVE },  
  • [MIGRATE_RECLAIMABLE] = { MIGRATE_UNMOVABLE,   MIGRATE_MOVABLE,   MIGRATE_RESERVE },  
  • [MIGRATE_MOVABLE] = { MIGRATE_RECLAIMABLE, MIGRATE_UNMOVABLE, MIGRATE_RESERVE },  
  • [MIGRATE_RESERVE] = { MIGRATE_RESERVE,     MIGRATE_RESERVE,   MIGRATE_RESERVE }, 
}; 
    内核想要分配不可移动页时,如果对应链表为空,则后退到可回收链表,接下来到可移动页链表,最后到紧急分配链表。
    在X86架构中存在着三种内存域ZONE_DMA、ZONE_NORMAL、ZONE_HIGHMEM,那么每个内存域都有一个free_area数据结构:
<mm/mmzone.h>
struct zone {
  • struct free_area    free_area[MAX_ORDER];
}
    而如果是在NUMA架构中,可能存在着多块物理内存,其结构可能是如下图所示:
    基于伙伴系统的内存管理专注于某个节点的某个内存域,例如DMA或高端内存域。但所有内存管理区和节点的伙伴系统都通过备用分配列表链接起来。在首选内存 管理区或节点无法满足分配请求时,首先尝试用同一节点的另一个内存管理区分配,反复尝试下一个结点直到满足请求。

页的分配以及源代码剖析
       就伙伴系统的接口而言,NUMA或UMA体系结构是没有差别的,二者的调用语法都是相同的。所有函数的一个共同点是:只能分配2的整数幂个页。

从函数关系图上可以看到,最终的分配任务落在__alloc_pages()上。我们来看这个函数的代码
————————————————————————————待续————————————————-——————

Shortest Palindrome

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

char str[1000010],ans[1000010];
int r[1000010];
int min(int a,int b){return a<b?a:b;}
int max(int a,int b){return a>b?a:b;}
char* shortestPalindrome(char* s) {
    int i,j,k,cnt;
    int len=strlen(s);
    if(len<=1)  return s;
    r[0]=0;
    str[0]='?';
    for(i=0;i<=len;i++)
    {
        str[(i<<1)+1]=s[i];
        str[(i<<1)+2]='*';
    }
    str[len<<1]='#';str[(len<<1)+1]='\0';
    i=1;j=0;
    while(i<=(len<<1))
    {
        while(str[i-j-1]==str[i+j+1]) j++;
        r[i]=j;
        for(k=1;k<=j;k++)
            if(r[i]-k!=r[i-k]) r[i+k]=min(r[i]-k,r[i-k]);
            else break;
        j=max(0,r[i]-k);
        i+=k;
    }
    for(i=(len<<1);i>=1;i--)
    {
        if(i-r[i]==1) break;
    }
    i=(i+r[i])/2;
    cnt=0;
    for(j=len-1;j>=i+1;j--) ans[cnt++]=s[j];
    for(j=0;j<=len-1;j++) ans[cnt++]=s[j];
    ans[cnt++]='\0';
    return ans;
}

pmfs+nvm与ext4+pmbd+nvm性能比较

这周开始做nvm相关的一个性能测试。nvm是非易失性内存,是一类比较新的存储硬件的总称,其读写速率比DRAM慢,比ssd快。之前看了一些相关的论文,nvm的应用大概分这么几种:

1.用来完全替代DRAM作为主存.(并用DRAM做cache)

2.和DRAM一起构成一个混合的内存模型

3.作为块设备。

4.作为其他块设备的cache(如ssd)

这里把nvm作为块设备。

实验用dram模拟nvm,试验机总共8g内存,前4g仍作为dram使用,后4g作为nvm。

现在存在两种方案来使用它。

一是用新的filesystem来管理,这里使用pmfs这个文件系统.

pmfs项目的github:https://github.com/linux-pmfs/pmfs

二是在现有filesystem的基础上加上一层转换层,使得能够用现有的filesystem,如ext4来管理nvm。

这个中间层在这里是pmbd:https://github.com/linux-pmbd/pmbd

这两种方案下的体系结构图大概如下:

pmbd是作为内核模块启动的,可以按照README进行

pmfs对内核改动比较大,因此github给出的是修改后的整个内核。需要下载后重新编译内核。

注意不要下载zip文件然后解压,会导致文件不全。请用git clone到试验机。

对内核进行编译,请参照:http://zjuedward.blog.51cto.com/1445231/461376

make menuconfig时记得选上File sytems->Miscellaneous filesystems->Persistent and Protected PM file system support

这里声明一点:由于pmfs是基于内核3.11,而pmbd只能运行在3.2.1的内核上,所以我们只能在不同的内核下进行测验,但是内核版本的不同对实验结果影响不大,内存那块的差异非常小。

 
实验主要测试io带宽。使用的benchmark是fio-2.1.10
由于需要多次测试取平均值,并且生成的结果需要以特定格式导入到excel中生成图表,所以我写了个脚本来进行测试(只列举了针对pmbd的测试,pmfs的测试时类似的),如下:

import commands
io_type=["read","write","randread","randwrite"];
blocksize=["1KB","2KB","4KB","8KB"];
job_num=["1","2","4","8"];
result='type-job';
for num in range(1,4):
	for i in blocksize:
		result+="	"+i;
	result+="\n";
	for iotype in io_type:
		for job in job_num:
			result+=iotype+'-'+job;
			for bs in blocksize:
#				commands.getstatusoutput('touch /mnt/1.txt');
				cmd='fio -filename=/dev/pma -direct=1 -iodepth 1 -thread -rw='+iotype+' -ioengine=psync -bs='+bs+' -size=8G -numjobs='+job+' -runtime=30 -group_reporting -name=mytest';
				print str(iotype)+"  "+str(bs)+"  "+str(job)+"  begin\n";
				(status,output)=commands.getstatusoutput(cmd);
				word=output.split();
				bw_val=0.0;
				for i in word:
					if i.startswith('bw='):
						i=i.lstrip('bw=');
						if i.endswith('KB/s,'):
							bw_val=float(i.rstrip('KB/s,'))/1024.0;
							bw_val=float('%0.3f' %bw_val);
							bw_val=str(bw_val);
						else:bw_val=i.rstrip('MB/s,');
						break;
				result+="	"+str(bw_val);
				print str(iotype)+"  "+str(bs)+"  "+str(job)+"\t"+str(bw_val)+"  end\n";
				tmp_result=str(iotype)+"  "+str(bs)+"  "+str(job)+"\t"+str(bw_val)+"  end\n";
				ret1="echo '"+tmp_result+"' >>tmp_fio_log.txt";
				commands.getstatusoutput(ret1);
			result+="\n";
	ret="echo '"+result+"' >>resultlog.txt";
	commands.getstatusoutput(ret);
	result='type-job';

最终得到如下性能:


注意两个图纵坐标的不同,初步的比较可知使用pmfs对nvm进行管理的性能更好。
job=4比job=8性能更好是因为实验机为四核,用8个线程去跑反而增加切换的开销。
顺序读比随机读性能稍好可能是因为预取和cache的原因,我们的nvm实际上是DRAM模拟的,所以cache对其是有影响的
顺序写比随机写性能稍好也可能是cache的原因。
目前进行的是没有虚拟化的情况下的性能比较,后期还要加入kvm,在kvm下进行性能测试,io栈大致如下:

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数组的和加上这个增益就是答案。

#include<stdio.h>
#include<string.h>
int n;
int a[100010],dp[100010];
int main()
{
    int i,j;
    while(~scanf("%d",&n))
    {
        int sum=0;
        for(i=1;i<=n;i++)
        {
            scanf("%d",&a[i]);
            sum+=a[i];
            a[i]=(1890*a[i]+143)%10007-a[i];
        }
        dp[1]=a[1];
        int ans=dp[1];
        for(i=2;i<=n;i++)
        {
            dp[i]=(dp[i-1]>0?dp[i-1]+a[i]:a[i]);
            if(dp[i]>ans) ans=dp[i];
        }
        if(ans>0) sum+=ans;
        printf("%d\n",sum);
    }


    return 0;
}

1002(hdu5587) Array
题意:第一次操作,数列为{1}。总共做一百次操作,每次都是在原先数列末尾增加一个0,并复制原数列增加在0后面。再将新增加的数全部加1.
给出一系列的m,表示求前m个数之和。m<=10^16
第一次:1
第二次:1 1 2
第三次:1 1 2 1 2 2 3
……
解法:因为题意是递推的,比较容易想到用递归去解。对于给定的m,我们可以二分求出最少几次操作可以使数列长度达到m,设为num.设num次操作得到的数列长度为c[num],数列和为s[num].那么前c[num-1]个数的和就是s[num-1],剩余x-c[num-1]个数可以递归解决(设剩余tmp个数,那么转化为求前(tmp-1)个数的和+tmp-1+1)

#include<stdio.h>
#include<string.h>
typedef long long ll;
int t;
ll m;
ll c[110],s[110];
int bs(ll x)
{
    int l=1,r=63;
    while(l<=r)
    {
        int m=(l+r)>>1;
        if(c[m]==x) return m;
        if(x>c[m]) l=m+1;
        else r=m-1;
    }
    return l;
}
ll f(ll x)
{
    int num=bs(x);
    //printf("num:%d\n",num);
    if(num==1) return 1;
    if(c[num]==x) return s[num];
    ll tmp=x-c[num-1];
    if(tmp==1) return s[num-1]+1;
    return s[num-1]+1+f(tmp-1)+tmp-1;
}
int main()
{
    int i,j;
    c[1]=1;
    for(i=2;i<=100;i++) c[i]=2*c[i-1]+1;
    s[1]=1;
    for(i=2;i<=100;i++) s[i]=2*s[i-1]+1+c[i-1];
    //for(i=1;i<=100;i++) printf("c[%d]:%I64d\n",i,c[i]);
    //printf("\n");
    //for(i=1;i<=100;i++) printf("s[%d]:%I64d\n",i,s[i]);
    //printf("\n");
    scanf("%d",&t);
    while(t–)
    {
        scanf("%I64d",&m);
        ll ans=f(m);
        printf("%I64d\n",ans);


    }
    return 0;
}

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]。

#include<iostream>
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define MAXN 9999
#define MAXSIZE 1000
#define DLEN 4
using namespace std;
class BigNum;
istream& operator>>(istream&,  BigNum&);
ostream& operator<<(ostream&,  BigNum&);
class BigNum
{
public:
	int a[MAXSIZE];
	int len;
public:
	BigNum(){len = 1;memset(a,0,sizeof(a));}
	BigNum(const int);
	friend ostream& operator<<(ostream&,  BigNum&);
	BigNum operator+(const BigNum &) const;
};
ostream& operator<<(ostream& out,  BigNum& b)
{
	int i;
	cout << b.a[b.len - 1];
	for(i = b.len - 2 ; i >= 0 ; i--)
	{
		cout.width(DLEN);
		cout.fill('0');
		cout << b.a[i];
	}
	return out;
}
BigNum::BigNum(const int b)
{
	int c,d = b;
	len = 0;
	memset(a,0,sizeof(a));
	while(d > MAXN)
	{
		c = d - (d / (MAXN + 1)) * (MAXN + 1);
		d = d / (MAXN + 1);  a[len++] = c;
	}
	a[len++] = d;
}
BigNum BigNum::operator+(const BigNum & T) const
{
	BigNum t(*this);
	int i,big;
	big = T.len > len ? T.len : len;
	for(i = 0 ; i < big ; i++)
	{
		t.a[i] +=T.a[i];
		if(t.a[i] > MAXN)
		{
			t.a[i + 1]++;
			t.a[i] -=MAXN+1;
		}
	}
	if(t.a[big] != 0) t.len = big + 1;
	else t.len = big;
	return t;
}

int n,k;
BigNum dp[110][110];
int a[110];
int main()
{
    int i,j,t;
    while(~scanf("%d%d",&n,&k))
    {
        for(i=1;i<=n;i++) scanf("%d",&a[i]);
        memset(dp,0,sizeof(dp));
        for(i=1;i<=n;i++) dp[i][1]=1;
        for(j=2;j<=k;j++)
            for(i=1;i<=n;i++)
                for(t=1;t<=i-1;t++)
                    if(a[i]>a[t]) dp[i][j]=dp[i][j]+dp[t][j-1];
        BigNum ans=0;
        for(i=1;i<=n;i++) ans=ans+dp[i][k];
        cout<<ans<<endl;


    }
    return 0;
}

1002(hdu5569) matrix
也是比较简单的dp题,转移方程容易想到,具体见代码。

#include<stdio.h>
#include<string.h>
typedef long long ll;
int n,m;
int a[1010][1010];
int dp[1010][1010];
const int inf=0x3f3f3f3f;
bool judge(int x,int y)
{
    if(1<=x && x<=n && 1<=y && y<=m) return 1;
    return 0;

}
inline int min(int a,int b){return a<b?a:b;}
inline int max(int a,int b){return a>b?a:b;}
int main()
{
    int i,j;
    while(~scanf("%d%d",&n,&m))
    {
        for(i=1;i<=n;i++)
            for(j=1;j<=m;j++)
            {
                scanf("%d",&a[i][j]);
                dp[i][j]=0;
            }
        dp[1][2]=a[1][1]*a[1][2];
        dp[2][1]=a[1][1]*a[2][1];

        for(i=1;i<=n;i++)
            for(j=1;j<=m;j++)
            {
                if((i==1) && (j==2)) continue;
                if((i==2) && (j==1)) continue;
                if((i+j)%2==0) continue;
                int tmp1=-1,tmp2=-1,tmp=0;
                if(judge(i,j-1))
                {
                    tmp1=a[i][j]*a[i][j-1];
                    tmp=inf;
                    if(judge(i,j-2)) tmp=dp[i][j-2];
                    if(judge(i-1,j-1)) tmp=min(tmp,dp[i-1][j-1]);
                    tmp1+=tmp;
                }
                if(judge(i-1,j))
                {
                    tmp2=a[i][j]*a[i-1][j];
                    tmp=inf;
                    if(judge(i-2,j)) tmp=dp[i-2][j];
                    if(judge(i-1,j-1)) tmp=min(tmp,dp[i-1][j-1]);
                    tmp2+=tmp;
                }
                if((tmp1==-1) || (tmp2==-1)) dp[i][j]=max(tmp1,tmp2);
                else dp[i][j]=min(tmp1,tmp2);
            }
        printf("%d\n",dp[n][m]);

    }


    return 0;
}

1003 balls
做不出来,看了题解还没完全清楚。。

bestcoder#61 div2

1001(hdu5522) Numbers
签到题



#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
int a[110];
bool judge(int x,int y,int z)
{
    if((x+y==z) || (x+z==y) || (y+z==x)) return 1;
    return 0;
}
int main()
{
    int i,j,k;
    int t;
    int n;
    while(~scanf("%d",&n))
    {
        bool flag=0;
        for(i=1;i<=n;i++)
            scanf("%d",&a[i]);
        for(i=1;i<=n;i++)
        {
            for(j=i+1;j<=n;j++)
            {
                for(k=j+1;k<=n;k++)
                {
                    if(judge(a[i],a[j],a[k])) {flag=1;break;}
                }
                if(flag) break;
            }
            if(flag) break;
        }
        printf("%s\n",flag?"YES":"NO");
    }


    return 0;
}

1002(hdu5523) Game
简单题,考虑s和t的位置,分情况讨论即可



#include<stdio.h>
#include<string.h>
int main()
{
    int i,j;
    int n,s,t;
    while(~scanf("%d%d%d",&n,&s,&t))
    {
        if((s==t) && n>1){printf("-1\n");continue;}
        if(((s==1) && (t==n))||((s==n) && (t==1))){printf("0\n");continue;}
        if(((s==1)||(s==n)) && t!=1 && t!=n)
        {
            printf("1\n");continue;
        }
        if(((t==1)||(t==n)) && s!=1 && s!=n)
        {
            if((s-t==1) || (t-s==1)) {printf("1\n");continue;}
            printf("2\n");continue;
        }
        if((s-t==1) || (t-s==1))
            printf("1\n");
        else
            printf("2\n");
    }


    return 0;
}

1003(hdu5524) Subtrees
我看了下别人的代码,似乎有很简单的做法。。但是我还没研究。我说下自己的解法
问题是问n个结点的完全二叉树有多少种结点个数不同的子树。n是long long 范围
可以递归来做,由于是完全二叉树,所以以根结点的两个儿子为根的两棵子树一定有一棵是满二叉树,而满二叉树有log2(结点总数)种结点数不同的子树,对于另一棵子树,我们递归求解。
这样。递归次数是树高h(=log2(n)),每次递归都要往结果set中加log2(n)个数据,set加一次数据复杂度log2级别,由于set中数据总数很少,所以看成常数。所以复杂度大概O(lg(n)^2)
易错点:算树高h的时候,浮点函数log()精度不够,要用二分去求树高。。

#include<stdio.h>
#include<string.h>
#include<math.h>
#include<set>
using namespace std;
typedef long long ll;
set<ll> num;
ll pow2(ll k)
{
    ll ans=1,p=2;
    while(k)
    {
        if(k%2)
        {
            k--;
            ans*=p;
            continue;
        }
        else
        {
            k/=2;
            p*=p;
        }
    }
    return ans;
}
ll bs(ll n)
{
    if(!n) return 0;
    ll l=0,r=63;
    while(l<=r)
    {
        ll m=l+((r-l)>>1);
        if((pow2(m)-1>=n) && (pow2(m-1)<n)) return m;
        if(pow2(m)-1<n) l=m+1;
        else r=m-1;
    }
    return l;
}
void f(ll n)
{
    ll i;
    if(!n) return;
    if(n==1) {num.insert(1);return;}
    ll l,r;
    ll h=bs(n);
    ll non_ye=pow2(h-1)-1;
    ll ye=n-non_ye;
    ll xh=pow2(h-2);
    num.insert(n);
    if(ye<=xh)
    {
        l=(non_ye-1)/2+ye;
        r=(non_ye-1)/2;
        ll hr=bs(r);
        for(i=1;i<=hr;i++)
            num.insert(pow2(i)-1);
        f(l);
    }
    else
    {
        l=(non_ye-1)/2+xh;
        r=n-1-l;
        ll hl=bs(l);
        for(i=1;i<=hl;i++)
            num.insert(pow2(i)-1);
        f(r);

    }
    return;
}
int main()
{
    int i,j;
    ll n;
    while(~scanf("%I64d",&n))
    {
        if(!num.empty()) num.clear();
        f(n);
        printf("%I64d\n",(ll)num.size());
    }


    return 0;
}

1004(hdu5525) Product
不知道为什么TLE,按道理不应该啊。。看了下官方解答,基本思路相同,只是我没用费马小定理。有时间再回来改~
待修改

#include<stdio.h>
#include<string.h>
typedef long long ll;
const ll N=100010;
const ll mod=1000000007LL;
ll pr[N],p[N/10];
ll pi[N][20],ki[N][20];
ll cnt,lp;
void gp()
{
	for(int i=2;i<N;i++)
	{
		if(!pr[i])
			p[++lp]=pr[i]=i;
		for(int j=1;j<=lp && i*p[j]<N;j++)
		{
			pr[i*p[j]]=p[j];
			if(i%p[j]==0)break;
		}
	}
	return;
}
void fenjie(ll n)
{
	cnt=0;
	ll num=n;
	memset(ki[num],0,sizeof(ki[num]));
	while(n!=1)
	{
		ll t=pr[n];
        pi[num][++cnt]=t;
        ki[num][cnt]=0;
        while(n%t==0)
        {
            n/=t;
            ki[num][cnt]++;
        }
	}
	pi[num][0]=cnt;
	return;
}
ll ret;
ll pow(ll p,ll k)
{
    ll ans=1;
    while(k)
    {
        if(k%2) {k--;ans=(ans*p)%mod;}
        k/=2;
        p=(p*p)%mod;
    }
    return ans;
}
ll n,a[100000+10],b[100000+10];
ll zyz[20],cc[20];
void scan(ll &num)    //对G++使用
{
    char in;
    bool neg=false;
    while(((in=getchar()) > '9' || in<'0') && in!='-') ;
    if(in=='-')
    {
        neg=true;
        while((in=getchar()) >'9' || in<'0');
    }
    num=in-'0';
    while(in=getchar(),in>='0'&&in<='9')
        num*=10,num+=in-'0';
    if(neg)
        num=0-num;
}
int main()
{
    ll i,j;
    gp();
    for(i=2;i<=100000;i++) fenjie(i);
    /*debug
    for(i=2;i<=100000;i++)
    {
        printf("%d的约数为:",i);
        for(j=1;j<=pi[i][0];j++) printf("%d ",pi[i][j]);
        printf("\n");
        printf("%d的次数为:",i);
        for(j=1;j<=pi[i][0];j++) printf("%d ",ki[i][j]);
        printf("\n");
    }
    */
    while(~scanf("%I64d",&n))
    {
        for(i=1;i<=n;i++) scan(a[i]);
        memset(b,0,sizeof(ll)*(n+2));
        ret=1;
        for(i=2;i<=n;i++)
        {
            for(j=1;j<=pi[i][0];j++)
                b[pi[i][j]]+=ki[i][j]*a[i];
        }
        ll cn=0;
        for(i=2;i<=n;i++)
        {
            if(!b[i]) continue;
            zyz[++cn]=i;
            cc[cn]=b[i];
        }
        for(i=1;i<=cn;i++)
        {
            ll tmp=pow(zyz[i],cc[i]*(cc[i]+1)/2);
            for(j=1;j<=cn;j++)
            {
                if(i==j) continue;
                tmp=pow(tmp,1+cc[j]);
            }
            ret=(ret*tmp)%mod;
        }
        printf("%I64d\n",ret);



    }
    return 0;
}

bestcoder#59 div2

1001 SDOI
简单模拟

#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
int n,m;
typedef struct Node{
    char name[30];
    int sex;
    double s1,s2;
}Node;
Node node[110];
bool cmp(Node a,Node b)
{
    return a.s1>b.s1;
}
int main()
{
    int i,j;
    int t;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d%d",&n,&m);
        char s[10];
        int s1,s2;
        bool flag=0;
        double max1=0,max2=0;
        for(i=1;i<=n;i++)
        {
            scanf("%s%s%lf%lf",node[i].name,s,&node[i].s1,&node[i].s2);
            if(node[i].s1>max1) max1=node[i].s1;
            if(node[i].s2>max2) max2=node[i].s2;
            if(!strcmp(s,"male")) node[i].sex=1;
            else {node[i].sex=0;flag=1;}
        }
        for(i=1;i<=n;i++)
        {
            node[i].s1=node[i].s1*(300*1.0/max1)*0.3+node[i].s2*(300*1.0/max2)*0.7;
        }
        sort(node+1,node+1+n,cmp);
        printf("The member list of Shandong team is as follows:\n");
        if(!flag)
        {
            for(i=1;i<=m;i++)
                printf("%s\n",node[i].name);
            continue;
        }
        int male=0,total=0;
        for(i=1;i<=n;i++)
        {
            int sex=node[i].sex;
            if(total<m)
            {
                if(sex)
                {
                    if(male<m-1)
                    {
                        printf("%s\n",node[i].name);
                        male++;
                        total++;
                    }
                }
                else
                {
                        printf("%s\n",node[i].name);
                        total++;
                }
            }
        }
    }
    return 0;
}

1002 Reorder the Books
题意:给出1-n的一个乱序排列,每次操作只能抽出一个放到开头,请问最少操作几次可以使序列有序。
这题想通了很简单。
我们可以得到以下两个简单结论:
1.抽出数字x放到开头不会改变数字a和数字b的相对顺序(a、b不同于x)
2.当抽出数字x放到开头时显然以后一定要把比x小的数字1,2,3,……,x-1抽出放到开头一次(基于第一点,他们的相对顺序是错误的,但是移动其他元素不能改变他们的相对顺序)。
那么显然我们希望这个x越小越好。
由于从最大数字n为结尾的相对顺序正确的几个数不需要移动,所以x其实就是从n开始往回看的第一个顺序错误的数。
考虑以下情况:3,1,4,2,5
由于3,4,5三个数字相对顺序是正确的,所以x就是2,我们第一次将2放到开头,第二次将1放到开头就行。(显然上面的第二点指出比2小的数字一定至少移动一次,然后,我们可以发现,它们事实上只需要移动一次就可以使未被移动的那些数字连续且有序)
我发现有些想法大脑里过一遍是是快速而跳跃的,但是要通俗易懂地写出来且在逻辑上很严格会很麻烦。。。

#include<stdio.h>
#include<string.h>
int a[30],pos[30];
int main()
{
    int i,j;
    int t,n;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d",&n);
        for(i=1;i<=n;i++)
        {
            scanf("%d",&a[i]);
            pos[a[i]]=i;
        }
        int ans=1;
        for(i=n;i>=2;i--)
        {
            if(pos[i]>pos[i-1]) ans++;
            else break;

        }
        printf("%d\n",n-ans);
    }

    return 0;
}

1003 The Highest Mark
这题比赛时没做出来,特么为什么我现在这么菜!(好吧,其实以前也很菜)
题意:n个题目原始分数ai,每分钟减少bi(从比赛开始算起),完成需要ci,问t分钟最多可以得到几分(从中选择一些题目做)
n<=1000,t<=3000
如果没有bi这个量,那么这题就是一个0/1背包。
假设现在顺序已经确定,那么

#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
typedef long long ll;
typedef struct Node{
    int a,b,c;
}Node;
Node node[1010];
int n,m;
int t;
bool cmp(Node x,Node y)
{
    return (ll)x.b*(ll)y.c>(ll)y.b*(ll)x.c;
}
inline int max(int a,int b){return a>b?a:b;}
int dp[3010];
int main()
{
    int i,j,T;
    scanf("%d",&t);
    while(t–)
    {
        scanf("%d%d",&n,&T);
        for(i=1;i<=n;i++)
            scanf("%d%d%d",&node[i].a,&node[i].b,&node[i].c);
        sort(node+1,node+1+n,cmp);
        //for(i=1;i<=n;i++)
            //printf("%d  %d  %d\n",node[i].a,node[i].b,node[i].c);
        memset(dp,0,sizeof(dp));
        for(i=1;i<=n;i++)
            for(j=T;j>=0;j–)
            {
                if(node[i].c>j) continue;
                dp[j]=max(dp[j],dp[j-node[i].c]+node[i].a-node[i].b*j);
            }
        int ans=0;
        for(j=1;j<=T;j++) ans=max(ans,dp[j]);
        printf("%d\n",ans);

    }
    return 0;
}

1004 Candy Game

bestcoder#55

这几个礼拜忙着实习离职和研究生开学的事情,so。。没打比赛
bc#55这场也错过了(其实去打台球了。。逃~)
hdu5432
简单题,二分

#include<stdio.h>
#include<string.h>
#include<math.h>
const double eps=1e-8;
int t,n;
int h[10010],w[10010];
int bsearch(int l,int r,double s)
{
    int i;
    while(l<=r)
    {
        int m=(l+r)>>1;
        double ss=0;
        for(i=1;i<=n;i++)
        {
            double tmp=w[i]*(h[i]-m)*1.0/h[i];
            if(m<=h[i]) ss+=tmp*tmp*(h[i]-m);
        }
        if(ss*2-s>eps) l=m+1;
        else if(ss*2-s<-eps) r=m-1;
        else return m;

    }
    return r;
}
int main()
{
    int i,j;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d",&n);
        double s=0;
        int maxh=-1;
        for(i=1;i<=n;i++)
        {
            scanf("%d",&h[i]);
            if(h[i]>maxh) maxh=h[i];
        }
        for(i=1;i<=n;i++) scanf("%d",&w[i]);
        for(i=1;i<=n;i++) s+=w[i]*w[i]*h[i];
        printf("%d\n",bsearch(0,maxh,s));
    }

    return 0;
}

hdu5433
待补
hdu5434
待补
hdu5435
待补
hdu5436
待补