10.31心得

我穿过高山与大海,也穿过人山人海,当我蓦然回首,却发现——DJ比SPFA还好用!

题目描述

小红学姐手头上的电话号码太多了,于是她决定要做一个电话簿。她所在地区的电话号码都是四位数字并且第一位不会是0或者8。
小红学姐稍微有一点点强迫症,她的电话簿前两页一定要写一点有趣的笑话,不然她绝对不想打开这个无聊的电话簿。所以,电话号码会从第三页开始记录。为了格式的美观(以及满足他的强迫症),每页最多可以记录k个号码并且一定要是同一个数字开头的。同一页中的号码需要按字典序从小到大排序。
现在,小红学姐嘿嘿一笑,问你:他的电话簿有多少页?

题目解析

水题,略。

题目描述

题目解析

乘法分配律完,还用说什么?

题目描述

 一个公司有n个编号为1到n的员工。每个员工或者没有直接主管要么恰有一个编号不同的直接主管。如果一个员工A满足以下至少一个条件,那么他被称为另一个员工B的上司:
1.员工A是员工B的直接主管
2.员工B的直接主管是员工C且员工A是员工C的上司。
这家公司没有管理上的环。即,不存在一个员工是他/她直接主管的上司。
今天这家公司将安排一场聚会。这需要将所有n个员工分成几组:每个员工必须恰属于一个组。而且,在任何一个单独的组中,必不存在两个员工A和B满足A是B的上司。

题目解析

题目讲得天马行空,就是一个员工的上司是他的上司,上司的上司也是他的上司。深搜一下就能过了。

题目描述

zjc是一只喜欢探险的猴子。有一次,她在森林里迷路了(不仅仅是去探险,还要去找香蕉和桃子),森林里的每个地方都有一个编号1~n。幸好她所在的森林有路标,这些路标会告诉她从她所在的地方可以到达哪里,以及到达另一个地方的时间。zjc所在的地方为s地,他想去k地玩,这个森林的出口是t地。但是zjc找了一天的香蕉和桃子,很累了,更重要的是她也很饿……她必须在m时间内到达k地再出森林。所有的路标的起点终点值均包含上文的s,k和t。

题目解析

首尾呼应,现在开始。这题最优解是DJ,其实DJ不管是复杂度,还是空间都比SPFA好,但我受了早上讲座的蛊惑(气得我屁滚尿流),花两个小时打后者,结果啊不要。现在郑重地附上DJ算法关键部分——


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
for(i=1;i<=n-1;i++)
    {
        //找到离1号顶点最近的顶点
        min=inf;
        for(j=1;j<=n;j++)
        {
            if(book[j]==0 && dis[j]<min)
            {
                min=dis[j];
                u=j;
            }
        }
        book[u]=1;
        for(v=1;v<=n;v++)
        {
            if(e[u][v]<inf)
            {
                if(dis[v]>dis[u]+e[u][v])
                    dis[v]=dis[u]+e[u][v];
            }
        }    
    }

 

《10.31心得》有1个想法

发表评论

电子邮件地址不会被公开。 必填项已用*标注