over 4 years ago

随便写写了...
很多图好像都是横的我还不知道怎么转过来orz

0 - 突如其来的计划

3月2号收到八云发来HK要举办MD的消息后,就一直在低保和刷两排之间徘徊。4月初收到鲁蓝要举办AP大赛的消息,激动的一拍大腿「不能再咸鱼了我要努力制霸全场」。然后愉快的将目标定在了12个。

1 - 九点多才勉强出门的尖沙咀低保

逃课学第一定律:只要逃课就能遇到同学。

是的去地铁站的路上,我居然能遇到两个来上课的同学,当然这并不能阻止我去MD的决心。过了两趟爆满的地铁后,尼酱来的那趟地铁出人意料的人并不怎么多。顺利在地铁上会合,并赶到了第一站 —— 尖沙咀。

出站时遇到了第一个问题:d2出口没了。不过好在出站口多,七转八折的也算是走到了第一个任务处,随便吃点早餐顺便开刷625。

很喜欢出前一丁的早餐

尖沙咀的玩家超多,应该大部分人都是为了低保。一出门就遇到了王维,被递了biocard。(或许这就是大佬.jpg)

625还没怎么刷就没脚了(hack的速度跟不上的)

一小时刷完尖沙咀的四个任务,在最后一个任务处开启游客模式。

这种风格的徽章总是好看

2 - 从金钟到上环的步行爬山

尖沙咀的顺利完成很容易带来一种「这场md很轻松」的错觉,结果金钟一开始就走错路了。多走了一个漫长的上坡才到任务的起点处。完成任务的玩家人数比尖沙咀少了很多,不过依旧能遇到不少正在做任务的agent。

这里就是任务的起点啦

一路上坡,一直绕远路。有一个portal怎么也找不到位置然后突然发现前面有一条小路,抱着试试看的心态走上去,转弯突然撞上一个教堂,定位也在po的中心点了。

隐匿在高楼中的教堂,后面的塔吊很高啊

人群中的agent还是比较好认的,大多数背包上都会有明显的挂件(我也不例外)。走在路上和别的agent擦肩而过是一件非常有趣的事情,同时还可以用来判断走没走错路。

上环看到的涂鸦

上环的任务明显难做了很多,一个半小时完成五个。走到地铁站已经快两点了,(第一次)与合影擦肩而过。

3 - 签退点

赶到签退点是两点多,签退的人群排起了长队。

很动漫风格的标示牌(还有一张同款的biocard)

索性一鼓作气把签退点的两个任务做完,然后缩在星巴克里休息。星巴克是抵抗菌的好朋友。

签退完看到一群人围在一旁换卡。凑过去找却没有找到嘤嘤嘤樱花卡,只能先嘤嘤嘤为敬。

偷偷夹杂点私货(摆进去自己的卡)

4 - 最后一站炮台山

签退点没法休息,索性去炮台山做完最后一个任务。

之前都忘打卡了,来打个卡吧

一下地铁就开始下小雨,好在任务距离很短,顺利完成十二个后开始寻找晚餐。

十二个任务果然累啊

最近疯狂喜欢河粉,任务完成后发现旁边有一家河粉店,果断前往之。

第一次吃蕃茄味的,决定给99%好评。(如果没有突然掉落在桌子上的蜚蠊好评可以是100%的)

5 - 后记

本来还考虑要不要再刷一个任务(毕竟AP大赛),得知优衣库有新UT后,果断地铁前往铜锣湾。(为什么铜锣湾没有铜锣烧呢)

最后放个结晶结束

 
about 6 years ago

第一章

  1. 冯诺依曼计算机的特点

    [From 作业]
    1)计算机由运算器、控制器、存储器、输入设备、输出设备五大部件组成;
    2)指令和数据以同等地位存于存储器,可按地址寻访;
    3)指令和数据均用二进制数表示;  
    4)指令由操作码和地址码组成;   
    5)采用存储程序思想。指令在存储器内顺序存放,通常自动顺序取出执行;
    6)机器以运算器为中心。
    
  2. 计算机硬件的主要技术指标

    [From 作业]
    机器字长、存储容量和运算速度
    

    第四章

  3. 存储器的层次结构

  4. 静态RAM和动态RAM的特点

  5. 动态RAM为什么要刷新?刷新方式有几种?每种方式的特点?具体过程?

  6. 半导体存储器扩展 会连线绘图 会分析

  7. Cache的基本工作原理

  8. Cache的几种地址映射方式

  9. 如何给主存地址 Cache地址分段

  10. 主存如何映射为Cache地址

第五章

  1. 什么是I/O接口

  2. 程序查询方式特点 工作流程

    [From homework]
    控制简单,硬件开销小;
    CPU与外设是串行工作的,系统效率低;
    适用于CPU不太忙且传送速度要求不太高的场合。
    
  3. 什么是程序中断方式

  4. CPU响应中断的条件

    [FROM HOMEWORK]
    CPU响应中断的条件可以归纳为三条:
    1)有中断请求;
    2)CPU允许中断,即中断允许状态IF=1(或EINT=1);
    3)一条指令执行结束。
    
  5. I/O中断处理过程

  6. 中断服务程序的流程

  7. 单重中断 多重中断

    [FROM HOMEWORK]
    1)二者的比较可用两种中断的服务程序流程图(见教材P201)的对比来说明,此处略。
    2)单重中断和多重中断的区别在于“开中断”的设置时间不同。对于单重中断,开中断指令设置在最后“中断返回”之前,意味着在整个中断服务处理过程中,不能再响应其他中断源的请求。而对于多重中断,开中断指令提前至“保护现场”之后,意味着在保护现场之后,若有更高级别的中断源提出请求,CPU也可以响应,从而实现中断嵌套,这是二者的主要区别。
    
  8. DMA访存有哪几种方式

  9. DMA的工作过程

    [FROM HOMEWORK]
    DMA的数据传送过程可分为预处理、数据传送和后处理3个阶段。工作过程如下图所示:
    各阶段完成的工作如下:
    1) 预处理阶段:CPU执行主程序实现DMA传送的初始化设置;
    2)数据传送阶段:由DMA控制器实现内存和外设间的数据传送。
    3)后处理阶段:中断处理程序判断传送的正误,对写入主存的数据进行校验,完成善后工作。
    
  10. DMA与程序中断的相同点/不同点 响应过程有什么不同

  11. I/O设备与主机信息传送的控制方式

第六章

  1. 进位计数制之间的转换 二进制 八进制 十六进制

  2. 定点数原码 反码 补码的转换

  3. 浮点数格式 写出真值

  4. 二进制补码加减运算及溢出判断

  5. 浮点加减运算步骤

  6. ALU电路的功能和组成

第七章

  1. 指令的一般格式 操作码的扩展

  2. 寻址方式的含义 共几种方式 如何计算每种方式的有效地址 及分析

第八章

  1. CPU的组成和功能

  2. 什么是指令周期

  3. 中断周期内CPU要完成哪几项操作

  4. 借助中断技术改变优先级 及绘图

第九章

  1. 指令周期 时钟周期 机器周期之间的关系

  2. 给定一条指定寻址方式的指令,写出全部微操作流程 最好结合节拍

第十章

  1. 两种控制器各自的优缺点

  2. 微程序控制的工作原理

  3. 微指令的编码方式

  4. 后继微地址的方式 如何根据指令操作码形成后继地址?

补充

卡诺图的化简 及根据化简后的表达式绘制电路图

计算题 4个小题 20分

问答题 6个小题 36分

分析设计题 4个题 42分

 
about 6 years ago

数据结构提纲

第零章:引论

  1. 理解数据结构的逻辑表示和物理表示,能结合具体的数据结构解释,如 2 维数矩阵、 栈、队列的逻辑描述和对应数组和采用数组(链表)的存储表示。
  2. 知道线性结构和动态结构的区别,前者要求元素总有前、后面的元素的概念,如,一维数组、队列和栈;后者则没有前后的概念,如图和树,一个元素可以和多于2个的元素有位置上的关系。
  3. 存储结构上分为顺序存储(数组)和链接存储(链表和树)。
  4. 对给定的数据,知道并有能力给出其抽象的数据结构,即给出数据说明和在其上的操 作说明。最好能给出 C++的类表示。 ##第一章:C++
  5. 类的定义方法;基本的程序设计、递归函数的设计(知道递归程序是通过栈实现的;new的使用和友元函数。我们的理想是大家能用 C++描述数据结构和程序实现,但若做不到,可以和自然语言等混合描述,称为伪代码。

New的使用:

1) int *y; y = new int;
2) int *y = new int; *y = 10;
3) int *y = new int(10);
4) int *y; y = new int(10);

友元函数:

一个类的private成员的访问权授予其他的类和函数,做法是把这些类和函数定义为友元(friend)。
eg:A需要访问B的private成员,则需要在B中将A写成友元。

异常

//内存不足
class NoMem{
    putlic:
        NoMem(){ }
}

第二章:程序性能评估(算法性能)

  1. 知道程序有两个重要的测度,即时间复杂性和空间复杂性。

  2. 时间复杂性:指定一个基本操作,把算法输入数量 n 作为参数,用算法需要的基本操 作数量的关于 n 的渐进逼近函数来描述算法复杂性的级。知道符号 ,O(n),和 函数 的理论上的定义,以及实际上的作用(下界,上界和精确界)。对简单的算法自己能估计 O(n). 时间复杂性又分最坏和期望时间复杂性,若不特殊说明,一般指最坏情况下的时间复杂性。即找一个特例,算法中基本操作最多。

    说明:

    O(n^2)就是顶破天了搞个n^2次;
    o(n^2)就是天花板不到n^2,比n^2矮一点(比如希尔排序就是o(n^2),因为它再倒霉也达不到n^2);
    Ω(n^2)就是说某个算法随便怎么至少都要耗费n^2,比如所有基于比较的排序都是Ω(nlogn);
    Θ(n^2)就是说它即是O(n^2)又是Ω(n^2),被天花板和水泥地夹在中间了,动不了了,就是它了。
    
  3. 空间复杂性:指一个算法(程序)所需的内存空间,主要是指数据所使用的空间(虽然也包含指令和程序栈等)。也是用算法需要的基本存储单元的关于 n 的渐进逼近函数来描述算法复杂性的级表示。在表示上也用符号 ,O(n),和 ,但精确时,要和数据的类型联系起来计算,如整型(2byte)、实数类型(4byte)等。

    空间复杂性 S(P)= c+ Sp(实例特征)
    
  4. 掌握基本的排序算法和它们的最坏和期望时间复杂性,即能用自然语言给出下面算法 的思想和具体的实现步骤。最好能给出 C++程序。

+  基于比较的排序
 +  内排序:冒泡、快速、插入、堆排序、归并排序
 +  外排序:赢者树排序 
+  基于存储的排序
 +  BOX 排序和基数排序

第三章:数据表示: (重点是单链表上的操作)

  1. 线形表的两种表示方法(基于公式的和基于链接的),C++类的表示和对应的基本操作。(search, insert和 delete实现的算法。能用图和程序给出基本操作的描述和实现。特别是对指针的使用和具体操作中对指针的修改要熟练,知道需要辅助的指针帮助实现 insert, delete。)

    int LinearList<T>::Search(const T&x)const{
    //查找x,如果找到则返回x所在的位置
    //如果x不在表中,则返回0
    for(int i = 0 ; i < length ; i++)
        if(element[i] == x) return ++i;
    return 0;
    

    创建一个整数线性表:LinearList<int> y(100)
    * 省略的代码可以见电子书P79
    

  2. 对链表函数功能的扩展,有实现能力(append, iterator, reverse ,alternate)以及两个有序链表的归并等。

  3. 掌握循环链表和双向链表的结构和对应基本操作的实现。知道它们的特点和在什么情形下用它们比较好,对编程带来的简化。知道循环链表的空和满的判断,和增加一个虚拟头节点在编程带来的便利。

  4. 掌握采用C++描述的Chain的表示和基本操作的实现。知道通过对类T的不同类的替换,得到后面应用赋权图的邻接链表的表示。

  5. 掌握箱子排序和基数排序算法和程序。知道这是一种不需要比较操作并且具有O(n)时间复杂性的排序算法,但也是一种应用受限算法(元素为整数)。

    箱子排序 —— P111 ; 
    基数排序 —— P116 ;
    
  6. 集合的表示和操作Union, Find的实现方法。

第四章:数组与矩阵

  1. 一维和二维数组的抽象数据表示方法,建立在类定义下的操作和对应的C++实现。

  2. 二维矩阵的行主映射和列主映射的存储方式和对应的数组元素的逻辑位置和具体存储位置的映射函数。

  3. 矩阵抽象数据描述和物理存储。

  4. 特殊矩阵的存储(对称、上下矩阵和稀疏矩阵)及映射函数。

  5. 稀疏矩阵的链表表示和后面图的邻接链表表示的异同点是什么?

    相同点:行列双向链表实现的不等长二维链表。
    不同点:1)一个表示值,另一个表示通路。
           2)稀疏矩阵全零行可省略,图不可(所以图邻接链表的首列也常用一维数组)
    

    *稀疏矩阵非零的数目应该小于n^2/3.
    

第五章:栈 ( LIFO )

  1. 栈的定义和逻辑上的功能描述

  2. 栈的抽象数据描述和 C++类的表示(自定义)

  3. 采用一维数组或链表的栈的表示和操作的实现 (add, delete)

  4. 栈的应用,算数表达式中的括号配对,表达式的前缀和后缀表达式的计算,Hanoi 塔的可视化描述。知道递归函数的实现是通过栈实现的。以及后面的图的深度优先遍历的实现等。

    汉诺塔问题:
        void Tower(int n, int x,int y, int z){
            if(n>0){
                Tower(n-1,x,z,y);
                cout<<"the top of "<<x<<" to the top of "<<y<<endl;
                Tower(n-1,z,y,x);
            }
        }
    

第六章:队列 ( FIFO )

  1. 队列的定义和逻辑上的功能描述

  2. 队列的抽象数据描述和 C++类的表示

  3. 采用一维数组或链表的栈的表示和操作的实现 (add, delete),各自的优缺点是什么? 采用一维数组时,如何把数组看做是环状的数据结构,此时队列满和空是如何判断的?

  4. 当采用链表表示队列时,add 和 delete 是怎么实现的?在表头和表尾的选择根据是什么?

  5. 列举一些书中有哪些队列的应用。知道对图的广度优先遍历是通过队列实现的。

第七章:跳表和 hash

  1. SortedChain 的面向对象的描述、特点和基本函数 search, insert, delete 的实现。

    见P219
    
  2. SkipList的组织结构、主要的特点 (利用链表元素已经排好序的特点,采用和一维数组折半查找的思想,缩小检索空间。在实现技术上是采用链表实现的)。

    n个元素时,搜索插入删除的复杂性均为 O(n+MaxLevel)。(最坏情况)
    每种操作(搜索,插入,删除)的平均复杂性均为O(logn) 。
    空间复杂性:最坏情况(n个元素 n * sizeof(element) + 链指针 O(n*MaxLevel));
    平均空间需求大约是2n个指针的空间。
    
  3. 采用 Hash 的基本思想(大空间数据到小空间存储空间的映射),常用 hash 函数是什么? Hash 表的两种基本的表示( hashing with linear open addressing 线性开型寻址散列和链表散列)方法能叙述。对应两种表示各自对 search, insert 和 delete 的实现方法,特别是发出冲突时的处理方法。

第八章:二叉树和其他树

  1. 关于树的定义和基本术语(根、树的高度、孩子、双亲、叶子、顶点的度);

  2. 二叉树的定义和基本术语 (根、左子树、右子树、空树、满二叉树和完全二叉树)。

  3. 数学表达式的二叉树表示(相互转化的对应关系)

  4. 二叉树的性质(高度和顶点个数的关系,满和完全二叉树高度和顶点个数关系、双亲和孩子标号的关系,以及采用一维数组的存储对应方式)。

  5. 二叉树的存储 (线性数组和链表)和 C++的类的表示方法;

  6. 知道二叉树是一种递归的动态存在结构,能够熟练地采用递归程序解决二叉树的编程, 如二叉树的三种遍历方式(会走例子)和写出对应的程序,树的高度计算等;

    二叉树的删除用后序遍历。        P264
    
  7. 其他树(森林)的二叉树表示,以及利用二叉树表示集合时,对集合操作的实现。

第九章:优先队列 ( Priority Queues ) heap

  1. 最大(最小)树以及 Heap (堆)的定义和表示;

    最大(小)树:每个节点的值都大于(小于)或等于其子节点(如果有的话)值的树。
    最大(小)堆:最大(最小)的完全二叉树。
    最大树不必是二叉树。
    n个元素的堆的高度必为log2(n+1)。
    
  2. Heap 的一维数组存储方式、类定义和基本操作(search, delete, insert)和 Initialize的实现;

  3. 高度优先左高树 (HBLT)定义以研究意义是什么(树的合并等操作更加方便)

  4. Heap sort 实现算法和程序;

  5. 霍夫曼编码的思想、霍夫曼树及实现算法。给定一组字符和出现的频率,有能力建立霍夫曼树.

第十章:竞赛树( Tournament Tree )

  1. 赢者(输者)树的定义;

  2. 采用上述树的排序算法思想描述

  3. 采用赢者树实现外部排序的算法描述;

第十一章:搜索树( Search trees )

  1. 二叉搜索树、AVL 树 、B 树 和 B+树的定义;

  2. 二叉搜索树的表示和基本操作(search, insert, delete) 的实现算法即走例子描述其过 程;

  3. AVL 树的性质(高度和节点数关系)、平衡因子的定义,在 insert 后不平衡的类型及对 应的旋转修正方法描述(可以用图);

  4. m 叉搜索树和 B 树的定义,性质和关于 insert,delete 操作后对树的修正算法的思想描 述(图描述)

  5. B 树和 B+树的异同点是什么?B+树的搜索和插入和删除操作实现的思想。

第十二章:图( graph )

  1. 图的定义和分类(网络、有向(赋权)图、无向(赋权)图、术语(顶点度、路径、 回路),和第八章定义的区别。最短路径和最小生成树。

  2. 图的两种表示方法和对应的采用图和 C++描述。

  3. 图的性质(顶点数和边数),稀疏图适合的表示方法;

  4. 图的深度和广度优先遍历算法的描述和实现程序。算法的时间和空间复杂性分析。 e) 图遍历算法的应用:图的连通分支的计算、深度和广度优先生成树。

第十三章:贪婪算法( The Greedy Method )

  1. 贪婪算法的思想及特点;

  2. 算法及实现:拓扑排序、二部图顶点覆盖、单原点到其他所有顶点的最短路径 Dijkstra
    算法、最小生成树算法(Prim 和 Kruskal)的思想描述(伪代码)。

第十四章:分而治之算法

  1. 该方法的思想描述

  2. 主要应用算法:归并排序、快速排序和找无序数组中第 k 大(小)元素。

第十五章:动态规划

  1. 该算法的思想已经和分而治之算法的区别

  2. 矩阵链的计算和所有顶点之间最短路算法。

 
about 6 years ago

PowerSet

mathematical foundations

  • full intersection 只要是对应元素集合的交集就行,不管是否有其它集合存在
  • expected size 用来预估大小,假定它们无关,通过比较预测数值和实际数值的大小关系判断over- or under-represented e(X) X的期望大小 deviation_raw(X) X的原始残差 deviation(X) 对于大的交集仍然存在偏差,因此需要归一化残差
Read on →
 
over 7 years ago

题目

题意

给定一棵树,要求在这棵树的n个节点上分别放上1~n的数字。
对于任意一棵子树,其部长是这棵树上的最大值,求所有的子树,部长的个数为k的数字的摆放数量。

思路

官方题解

可以用求概率的思想来解决这个问题。令以i号节点为根的子树为第i棵子树,设这颗子树恰好有sz[i]个点。那么第i个点是第i棵子树最大值的概率为1/sz[i],不是最大值的概率为(sz[i]-1)/sz[i]。现在可以求解恰好有k个最大值的概率。
令dp[i][j]表示考虑编号从1到i的点,其中恰好有j个点是其子树最大值的概率。 很容易得到如下转移方程:dp[i][j]=dp[i-1][j]*(sz[i]-1)/sz[i]+dp[i-1][j-1]/sz[i]。这样dp[n][k]就是所有点中恰好有k个最大值的概率。
题目要求的是方案数,用总数n!乘上概率就是答案。计算的时候用逆元代替上面的分数即可。

补充

求概率先求方案数的题目很多,求方案数先求概率的题目倒是第一次见。
乘法的逆元由于取余是质数,所以根据费马小定理可以直接求对应数值的mod-2次方。

代码

Read on →
 
over 7 years ago
题目

CF567F

题意

给n个数字,每个数字使用两次,最终构成一个递增和一个递减序列(递增或者递减序列可以不存在),给定k个限定条件,求构造的个数。

思路

从外向里填,dp[i][j][k]表示填区间[i,j]用数字k来填充。
【注意mx=70而不是35,摔

Read on →
 
over 7 years ago

题目:
HDU1533
题意:
n个人到n个屋子,求最短距离。
思路:
KM本身是求最大值的,因此对所有距离取反,然后输出-ans就可以啦。
题不难,不过首次尝试了下pair,感觉比struct好用多OJZ

Read on →
 
over 7 years ago
题目

HDU2853

题意

给定一个二分图和一种匹配。求最优匹配和移动最小次数。

思路

未匹配的边权值变为k倍,匹配的边的权值变为k倍+1,这样可以保证最先选择匹配好的边。
sum/k是最终匹配成功的值,sum%k是未改变的匹配的个数。

Read on →
 
over 7 years ago

链接

HDU4281

题意

给出N个点,第一个点是裁判,其他N-1个点需要裁判过去回答问题,每个点需要的时间不一样,而每个裁判最多能回答M分钟的问题。题目分两问,第一问是如何分配可以使使用的裁判数最少,第二问是如何分配裁判,使裁判走过的欧几里得距离和最小,裁判一开始都在1,最终也要回到1(要回到1啊!)。

思路

一共两个问题,第一问是状态压缩,第二问是mTSP问题,dp[i][j]表示状态为i,在位置j的最小花费,然后开一个一维数组来保存最有状态,最后枚举子集,DP合并环即可。
枚举子集的循环可写为:for(int sub = s&(s-1);sub;sub=s&(sub-1))

Read on →
 
over 7 years ago

概述

一般是求小于等于数字N的某些特征数字个数,或者是区间[L,R]的之间的某些特征数字个数,后者一般可以转换成求差的方式来做。

Read on →