poj 2342 Anniversary party (基础树形dp)

题目链接

题意:n个人的上下级关系形成一棵树..每一个人有一个val(可正可负),要选若干个人参加一个party,要求是一个人和他的直接上级不能同时在场。问参加party的人最大的val之和。

思路:树形dp入门题。

 

dp[i][0]和dp[i][1]分别表示第i个人不参加和参加party对应的val和。

注意dp转移方程是放在每次dfs之后的回溯位置的。。。

这样做的话访问是从根节点到叶子节点,更新就成了从叶子节点到根节点。。。

联想到数字三角形…其实是一样的。。

sad…dp苦手如我也开始刷dp了吗。。。。

 

geekos project 1 (ELF文件相关)

一、目的
熟悉ELF文件格式,了解GeekOS系统如何将ELF格式的可执行程序装入到内存,建立内核进程并运行的实现技术。
二、流程
1、修改/geekos/elf.c文件:在函数Parse_ELF_Executable( )中添加代码,分析ELF格式的可执行文件(包括分析得出ELF文件头、程序头,获取可执行文件长度,代码段、数据段等信息),并填充Exe_Format数据结构中的域值。
2、在Linux环境下编译系统得到GeekOS镜像文件。
3、编写一个相应的bochs配置文件。
4、在bochs中运行GeekOS系统显示结果。

 

编译以及启动bochs同project0…
project0遇到的那些错误还是都会遇到一遍233.

然后在project1/src/geekos/ 目录下的elf.c中添加函数:int Parse_ELF_Executable(char *exeFileData, ulong_t exeFileLength,
struct Exe_Format *exeFormat)

原理部分不过多阐释,具体可见我参考的博客。

最后实现为:

 

然后由于编译之后比project0多生成了一个diskc.img文件

所以还需要相应得修改配置文件.bochsrc

最后内容如下:

project0遇到的启动bochs的那些问题project1也会遇到一遍233

 

然后。。。启动。。。

报错如下:

选区_123

 

查了好多。。。一无所获。。。

最后看到一遍博客: 参考博客1

那篇博客里虽然和我遇到的问题不一致。。。

但是死马当做活马医。。。

objdump -d a.exe 查看了反汇编代码。。。。a.exe的路径是project1/build/user/

 

可以看到在_Entry入口处的汇编,首先

sub    $0x1c,%esp

然而程序却抢先在

add    $0x1c,%esp

之前使用leave和lret长跳转返回了,这样程序当然出错了。

我这里是将
  __asm__ __volatile__ (“leave”);
__asm__ __volatile__ (“lret”);
改成了
  __asm__ __volatile__ (“add $0x1c, %esp”);    (注意,原文作者这里把%esp写成$esp,坑死小白啊。。还写错两次)
  __asm__ __volatile__ (“lret”);

就能正常工作了。

 

选区_125

geek OS project 0 (下)

现在我们环境已经搭好了,参考 geekos实验环境的搭建

在main.c中新加个函数,命名为projecto,函数的代码如下:

 

 

再修改Main函数,将TODO(“…..这一行替换为以下代码:

struct Kernel_Thread *thread;
thread = Start_Kernel_Thread(&project0,0,PRIORITY_NORMAL,false);

替换的意思是,要把TODO那一行注释掉。。。

TODO语句的定义在src/project0/include/geekos/kassert.h中

可以看到,这是一个宏打印错误提示后,就直接进入一个死循环中,也就是执行到TODO之后程序就不会继续往下运行了,所以要继续进行调试project0就必须删除或者注释掉那条TODO。

 

保存代码,按上一篇文章中的方法编译,并在bochs中引导系统。
运行效果如下图所示:

选区_121

 

 

参考博客:参考博客1
参考博客2

geekok project0(上)(实验环境的搭建)

此处下载的bochs应该是比较新的…如果之后遇到

failed assertion in init_idt :g_handlersizenoterr == g_handlersizeerr

这个错误,建议安装比较老的nasm版本,比如2.08.02链接

 

下载geekos-0.3软件包,地址为:
geekOS下载地址

然后解压到~/work目录。

然后进入到 /work/geekos-0.3.0/src/project0/build 目录下

之后的操作都是在这个目录下进行的。

 

 

然后执行 make

报错,原因是编译检查过于严格。。我们修改makefile文件,取消把warning当成错误看待。

makefile 的路径就是当前路径,也就是:

rkz2013@111qqz-ThinkPad-X200 ~/work/geekos-0.3.0/src/project0/build $ vim Makefile

把149行的 -Werror 去掉。

然后再次make

解决办法是把makefile文件中第148行添加编译选项

-fno-stack-protector

然后把makefile文件中的100行至109行修改为如下内容
(修改了100行,106行,109行,条件编译什么的。。可能遇到依赖的库不全的情况。。。安装就好)

然后要把以前失败的清理干净。。重新编译。。。

编译成功。。。
检查一下:

然后启动bochs

报错:

因为配置文件.bochsrc 太古老了。。。路径什么的都是错的。。。

最终修改为如下:

然后继续启动。。报错:

这是由apt-get install bochs-x 得到的 libbx_x.so不完善造成的
解决办法: 换个显示方案。

sudo apt-get install bochs-sdl

然后在.bochsrc文件中添加

display_library: sdl

再次运行bochs  。。终于可以了。。。感动

选区_120

OS课设之geek os 非最终版

参考了这篇博客

流程部分不再具体描述,可以参考上面的博客。

只详细给出我遇到的问题。

我的pc环境是:Linux 111qqz-ThinkPad-X200 3.16.0-38-generic #52~14.04.1-Ubuntu SMP Fri May 8 09:43:57 UTC 2015 x86_64 x86_64 x86_64 GNU/Linux

linux mint 17.2 cinnamon

http://sourceforge.net/projects/geekos/files/ 下载geekos软件包并且解压

报错。。

解法办法:修改/home/rkz2013/geekos-0.3.0/src/project0/build

目录下的Makefile文件。

 

make后再次出现错误:

解决办法:

 

然后又报错

 

解决办法:

修改/home/rkz2013/geekos-0.3.0/src/project0/build目录下的Makefile的100行至109行如下。
(改动了100行,106行,109行。。。交叉编译什么的,因为做OS大作业的时候搞过这个。。。如果之前没有交叉编译过可能出现库依赖不全的情况。。。? 缺什么安什么就好了。)

新建一个.bochsrc的配置文件

放入一下内容

保存在主目录下。

然后再启动bochs
再次报错

解决办法:

 

华科软院计组概念复习

noip初赛加强版既视感…

自己手动整理的

第二章
机器数:正负符号数码化后的数据称为机器数。
BCD码:用二进制编码的十进制数称为bcd码。
有权码:每位二进制数码元都有确定权值的编码。
校验码:为了发现或纠正数据传送中出现错误的编码。
浮点数的精度由尾数的位数决定。
第三章
溢出:运算结果超出了机器能表示的数据范围。
溢出的特征:结果的符号与操作数的符号不同。
变形补码:两个符号位的补码(用来检测溢出,00,11说明没有溢出,10,01说明有溢出)
对阶:使阶码相等的过程(原则是小阶码向大阶码看齐)
结果规格化:将非规格化数处理为规格化形式。

*根据指令中所含操作数地址的数量可分为(4种):
三地址指令
双地址指令
单地址指令
零地址指令

第四章
存储位:存储器记忆信息中的最小单元。
地址:每个存储单元的编号。
主存储器的技术指标:存储容量,存取时间,存储周期,存储器带宽。(两类:存取速度和存储容量)
存储体:存储器中的记忆部件,通常由大量的存储单元组成。
MROM:掩膜型只读存储器。
PROM:可编程只读存储器。
EPROM:可擦写可编程只读存储器。
EEPROM:电可擦除可编程只读存储器(扩展)
CACHE对程序员是透明的。
内存:Cache 与主存合称为内存。
全相联映射:将主存分成若干块,主存的任意一快可定位于Cache的任意一块中。
组相联映射:将主存分成若干区,每一区包括若干组,每一组包含若干块;将Cache也分成若干组,每组若干块。
组之间用直接映射方式,组内的块采用全相联映射方式
替换策略:最不经常使用(LFU,近期最少使用(LRU,随机替换
写操作策略:全写法(命中时既写入Cache,又写入主存)
写回法(命中时只写入Cache,不写入主存)
写一次法(第一次采取全写法,之后采取写回法)
硬盘存储器的主要指标包括存储密度、存储容量、存取时间及数据传输率。
平均存取时间:从发出读/写命令后到开始从盘片表面读出或写入信息所需要的平均时间。
平均存取时间=平均寻道时间+平均等待时间。

数据传输率:存储器在单位时间向主机传送数据的字节数。

*DRAM刷新方式:
集中刷新方式
分散刷新方式
异步刷新方式
第五章
机器指令:计算机能够直接识别,执行的指令称为机器指令,简称指令。
指令集;一台计算机中所能执行的指令的集合称为指令集(指令系统)
指令包含两种信息:指令和数据。
寻址方式:根据指令中的信息寻找物理地址的方式。
寻址方式包含指令寻址方式和操作数寻址方式两大类。
指令寻址方式:顺序寻址方式和跳跃寻址方式。
操作数寻址方式:直接寻址,寄存器相对寻址,寄存器间接寻址,基指+变址等
为什么多种寻址方式:效率和方便性上达到平衡,满足各种需要。
RISC指令系统特点:
指令系统简单,指令条数少;
寻址方式少;
指令格式简单,指令长度固定
cpu中设置大量寄存器以减少对存储器的访问。

**cache的工作原理:
当cpu访问的内存地址给出后,该地址先与相连存储器中存放的地址比较,
判定要访问的字是否在Cache中,在则访问Cache,称为命中;
不在则访问主存,称为未命中。
命中时需要先产生访问Cache的地址
未命中时根据cpu给出的地址访问主存。
第六章
中央控制器的主要功能:
指令序列控制
操作控制
时间控制

程序计数器(PC):给出下条指令在存储器中的地址。
指令寄存器(IR):用来保存当前正在执行的指令。
地址寄存器(AR):用来保存当前所访问的内存地址。
指令功能译码器(ID):对当前要执行的指令进行译码分析并指出指令功能。
操作控制器(OC):产生控制信号的功能部件。
根据设计方式的不同,OC分为硬布线控制器和微程序控制器。
硬布线控制器的核心部件:操作控制器。
时序产生器(TG):用来产生时序信号。

控制方式:
同步控制方式:选取执行部件中最长操作时间作为统一的时间标准。
异步控制方式:每条指令需要多少时间就给多少时间。
联合控制方式:同步异步相结合。
微程序控制器:用微程序方式设计的操作控制器。
微命令:在微程序控制的计算器中,打开或关闭控制门的控制信号。
微操作:微命令控制执行部件进行的操作。
*微(指令)周期:从存储器取出并执行一条微指令需要的时间。
微命令的表示:
直接表示法
编码表示法
混合表示法(前两种混合用)
微命令分类:
互斥性微命令:某时刻不能同时给出。
相容性微命令:某时刻可以同时给出。

微指令格式:
水平型微指令(直接表示法)
垂直型微指令(编码表示法)

微地址的形成:
下址字段法
计数器法

**微程序控制器的设计思想:
将指令系统中所有指令功能实现所需要的控制信号以微指令为单位存储,每条机器指令对应一段微程序。
**微程序控制器的设计“采用了存储技术和程序设计技术。
流水CPU:采用流水线技术对指令和数据进行处理的CPU
并行处理技术(三种):
时间并行
空间并行
时间-空间并行
流水线分类(3类):
指令流水线
运算流水线
处理器流水线
RISC的3个要素:
有限的指令集
大量的寄存器
强调对指令流水线的优化。

第七章
*总线:计算机系统内部的各个设备或部件间相互通信的公共通路。
总线分类:地址线(单向线),数据线(双向线),控制线(单向线)。
总线结构:单总线结构,双总线结构,三总线结构等(越来越好
*总线的仲裁方式解决总线的使用权问题。
总线的仲裁方式:集中仲裁方式(主流)(总线控制逻辑集中在一起),分布仲裁方式(总线控制逻辑分散在各个部件)
集中仲裁方式分类:
串行链接方式:从头开始一个一个问
定时查询方式:从某一个开始一个一个问
独立请求方式:非常快,优先次序控制灵活,n条BR,n条BG
总线通信方式:
同步通信:无应答通信,有同步脉冲。
异步通信:应答通信,“握手”,“当慢则慢,当快则快”
总线信息传送方式:
串行传送:一位一位传送,就一条传输线,慢。
并行传送:n位一起传送,n条传输线,快。
串并行传送:分组,组内并行,组间串行。
总线复用:地址线和数据线不严格区分,增加效率。
第八章不考。。。

第九章

CPU与外部设备交换信息的方式(三种):
程序查询方式
程序中断方式
直接存储器存取控制方式(DMA)
中断识别的方法(三种):
程序识别
单线查询识别
中断向量法识别

多模块存储器基本结构

多模块存储器基本结构

硬布线控制器基本结构

硬布线控制器基本结构微程序控制器的组成

微程序控制器的组成

 

独立请求方式

独立请求方式定时查询方式

定时查询方式串行链接方式

串行链接方式

codeforces 660 C. Hard Process (ruler)

cf660C

solution:ruler.1A

 

(转)树形dp题目集

树,一种十分优美的数据结构,因为它本身就具有的递归性,所以它和子树见能相互传递很多信息,还因为它作为被限制的图在上面可进行的操作更多,所以各种用于不同地方的树都出现了,二叉树、三叉树、静态搜索树、AVL树,线段树、SPLAY树,后缀树等等..

枚举那么多种数据结构只是想说树方面的内容相当多,本专辑只针对在树上的动态规划,即树形DP.做树形DP一般步骤是先将树转换为有根树,然后在树上进行深搜操作,从子节点或子树中返回信息层层往上更新至根节点。这里面的关键就是返回的信息部分,这个也没一般性的东西可讲,因为每道题目要求做的事都不尽相同。

这个专辑暂时氛围3哥部分,分的可能不是很好,后面题目做多了理解更深了可能会更改,但那都是后话了。

一、常规树形DP

1、 Hdu 1520 Anniversary party  每个节点有权值,子节点和父节点不能同时选,问最后能选的最大价值是多少?解题报告Here

      2、Hdu 2196 Computer  经典题,求树每个点到其他点的最远距离,转化为有根树,深搜两次,一次记录到叶子的最远距离,一次更新最终答案。解题报告Here
      3、Poj 1741 Tree(难)  经典题,求树上两点间距离小等于K的方案数,树上分治。解题报告Here
      4、Poj 2152 Fire(难)  罕见的O(n^2)的树形DP,在树上建消防站,要求每个节点离最近的消防站距离小于K,问最小花费。解题报告Here
      5、Poj 3162 Walking Race(难)  树形DP找最远距离+线段树查询最大最小值,然后再维护两个指针遍历整个序列。解题报告Here
      6、cf 218D. Choosing Capital for Treeland 把边方向转变成边权,正向为0,反向为1.经过转换,问题变成求某点为根到所有点的边权总和,求边权总和最小的那些点。

二、树形背包问题(在树上进行分组背包处理)

1、Poj 1155 TELE  把每个节点的子节点看成一组背包,最大容量是这点的叶子子孙数量,选几个节点就是选择的容量,价值就是用户给的Money-中转费用。解题报告Here

      2、Hdu 1011 Starship Troopers 和上题相似,要选择父节点必先子节点,特判m为0的时候。
      3、Poj 1947 Rebuilding Roads 求最少删除几条边使得子树节点个数为p,具体的模型和上题很像。解题报告Here
      4、Hdu 1561 The more, The Better 在一棵树上选择若干个点获得的最大价值,选子节点必须先选父节点,求解情况和上两题相同。解题报告Here
      5、Hdu 4003 Find Metal Mineral (推荐,好题) 树形DP+选且只能选一个物品的分组背包,状态转移方程难想。解题报告here
      6、Poj 2486 Apple Tree 树形DP+分组背包,但是状态转移方程要分三步,较为难想。解题报告Here
      7、Poj 3345 Bribing FIPA  树形DP+分组背包,和前面几题相比没有特殊的地方,只是要注意输入。具体可见Here
      8、Hdu 4044 GeoDefense 树形DP+分组背包,要求从每个儿子结点获取最小的hp,然后找这些儿子的最大组合,不是特别好想。解题报告见Here
      9、Zoj 3627 Treasure Hunt II  树形DP +分组背包,浙大月赛的水题,很普通的树形背包。
      10、4276 The Ghost Blows Light  有两种写法,一种是把一棵树压缩成一条链,然后在链上DP,一种和 Apple tree差不多,具体见Here

三、删点或者删边类树形DP

1、Hdu 3586 Information Disturbing 二分Upper power limit,然后从叶子节点向上更新,边权与limit比较再进行状态转移。解题报告Here

      2、Poj 3107 Godfather  删点,使剩下的分支中最大的节点数最小,深搜一次记录到叶子节点距离,再进行枚举求最大值,再更新答案。解题报告Here
      3、Poj 2378 Tree Cutting 删点,使剩下的分支中有最大节点数的分支小等于总数一半,问有几种方案,和上题差不多。解题报告Here     
      4、Poj 1655 Balancing Act  删点,使剩下的分支中最大的节点数最小,深搜一次记录到叶子节点距离,再进行枚举求最大值,再更新答案。解题报告Here
      5、Poj 3140 Contestants Division  删边,求删去某条边后两个分支的最小差异值,也是深搜两次。解题报告Here

    这篇文章将会不断更新,以后每遇到树形DP我都会整理进这个专题,希望大家保持关注。
     本文ZeroClock原创,但可以转载,因为我们是兄弟。
3

匈牙利算法总结

学完了km..感觉匈牙利真是非常的。。easy…
匈牙利算法学习链接

 

有一种题目会用1*2的小格子填充大的,问能不能填满之类的,可以用匈牙利搞。hdu 4185解题报告 poj2446解题报告

其实主要是关于建图的启示,上面两个题,还有这道题: poj1325解题报告

还有就是一些有用的结论:

(1)二分图的最小顶点覆盖 

最小顶点覆盖要求用最少的点(X或Y中都行),让每条边都至少和其中一个点关联。

Knoig定理:二分图的最小顶点覆盖数等于二分图的最大匹配数。

(2)DAG图的最小路径覆盖

用尽量少的不相交简单路径覆盖有向无环图(DAG)G的所有顶点,这就是DAG图的最小路径覆盖问题。

结论:DAG图的最小路径覆盖数 = 节点数(n)- 最大匹配数(m)

(3)二分图的最大独立集

最大独立集问题: 在N个点的图G中选出m个点,使这m个点两两之间没有边.求m最大值

结论:二分图的最大独立集数 = 节点数(n)— 最大匹配数(m)

还有一个比较常用的角度:n个数的某种排列,可以看做是一个位置集合{1..n}和数字集合{1..n}的二分图最大匹配。可以用来剪枝什么的。hdu3225解题报告

 

选区_079 选区_078

KM算法总结

km算法我的理解

 

刷了不到20道题。。。回来总结一发。。

如果题目求的是最小权值匹配,比较好的做法是将权值取取值,最后res再取负就好。需要注意的是初始化的时候w和lx要比所有值都小,所以要ms(lx,0xc0)

最正确解最小权匹配的办法是用一个很大的数-当前边权值,而不是直接对边权取反(这样只能处理左右点相等的完全二分图,即K(n, n)(bin神博客看到的)

有时候需要考虑无解的情况,一般如果有无解的情况,对应了存在lx[i]=初始化的值。

不少题目有一个点都是先用一种暴力或者不暴力的方法处理出w,然后裸的km  hdu3722解题报告

有向图的覆盖可以对应二分图最佳匹配的模型,用km算法搞 hdu1853解题报告

遇到了一种题是之前有一些已经安排好了,然后仍然求最优匹配,并且尽可能少得改变原有的安排。hdu2853解题报告 不得不说做法很厉害。

 

还有一些网络流的题似乎也可以转化成km来做,打算先去搞一发网络流再去A.

选区_077

这些题里就两个比较好,一个是对于有向环覆盖的,第一次遇到真想不到,还有一个就是那个权值×k的。。。佩服。。。

其他的都是套路。

HDU 3523 Image copy detection (二分图最佳匹配,KM算法,题意杀)

hdu 3523 题目链接

 

题意:有m个排列,每个排列有n个,然后要找一个长度为n的排列(1..n每个数字恰好出现一次),使得这个排列到其他m个排列的距离之和最小。 两个排列之间的距离是对应位置上数字差的绝对值的和。

 

思路:妈蛋,什么鬼题面。。。看不懂。。。然后看了题解。。。知道了题意。。

的的确确做过相当类似的一道呢。

先n*n*n的复杂度(1E6)处理权值,然后KM.

1A.

 

 

 

 

hdu 3315 My Brute (二分图最佳匹配,KM算法)

hdu3315 题目链接

题意:两个人分别各有n个怪物。进行n场pk.每只怪物必须恰好进行一场pk.如果先手的第i只怪物赢,会获得v[i]的val,输会减少v[i]的val.给出两个人n只怪物的血量和攻击力。先手的初始战斗顺序为1,2,3..n(后手的战斗顺序一直都是1,2,3..n) 现在问能否通过调整顺序使得先手获得的val最大,如果这个val大于0,表示先手可以赢。如果可以赢,那么还要求调整后的顺序和原始顺序的相似度,并且使得相似度尽可能大(If there are multiple orders, you should choose the one whose order changes the least from the original one)

 

思路:先根据血量和攻击力,n*n的时间处理出每场战斗的输赢信息,然后结合v[i],得到每两个怪物战斗的先手得到的val的值。

然后和hdu 1853类似,依然希望尽可能多的安排不改变。

我们的做法仍然是把w*N,然后钦定的w再+1

然后改变个数,由于存在负数。。。和hdu 1853的处理有区别。。。

想了一下。。。其实用link数组对照初始钦定顺序就好了啊。。。

1A.爽上天。。。

最近各种1A…?好开心。

 

选区_075

 

 

 

hdu 2853 Assignment (二分图最佳匹配,KM算法+数论,做法太神)

hdu 2853题目链接

题意:n个公司,m个任务(m>=n),一个公司只能对应一个任务,一个任务也只能对应一个公司。给出一个n*m的mat,表示每个公司对应每个任务产生的val。  然后给出n个数,表示初始钦定(雾)这n个公司分别做哪些任务。 但是可能初始的安排得到的val表示最大的。我们现在想得到最大的val,并且保证改变的安排数最少。求安排后得到的 val比初始安排大多少,以及需要改变的安排数量。

思路:最大val很好求,KM就好。。。但是,怎么才能保证改变的安排数最少呢? 尤其是当两个安排val一样的时候,如何才能保证优先选已经安排好的,而不取选另一个呢?

并没有想出来,看了题解T T

太神辣。

由于KM算法会根据权值来选取,权值大的会优先。

如果我们把每个权值*k(k>n),然后对于已经钦定的安排,每个权值再+1.

这样,钦定的安排就会有更高的优先级,最后统计的时候除以k,那么权值答案不会有影响(利用到了初等数论的整除知识。。。?)

然后这样做该有一个好处。

不除以k的权值和再模k,就是没有改变的安排数。

原因是由于没有钦定的安排的权值每个都乘了k,最后%k都为0,只有那些钦定的安排每个会贡献1.

又由于k>n,这样就保证了正确性。

 

这做法太神了。。。。。吓傻了。。。。

我试着推广一下。。。?

对于根据权值来决定优先顺序,但是权值相同的时候还是需要对一些赋有更高的优先权的模型。。。?

除了再增加一维的大家都能想到的做法。。。这样的做法是不是有通用性呢。。。?

做法太神,我得慢慢体会。。

 

 

 

 

hdu 2448 Mining Station on the Sea (floyd+KM)

hdu2448 题目链接

题意:n个船n个港口,一个港口只能承接一个船,m个油田,给出n个船各自在哪个油田,然后给出m个油田之间的无相图,然后给出油田和港口之间的有向图。求n个船到达港口的最小距离之和。

思路:想到了用floyd先更新一下距离,然后KM.不过思维不够严谨,只更新了港口通过油田到达油田的距离,而没有更新油田通过油田到达油田的距离QAQ.

所以应该先更新油田通过油田到达油田的距离,然后再更新港口通过油田到达油田的距离。。。

哦,还有。。。不要把n个船所对应的港口作为下标。。而是转化成1..n,这样写KM里会比较好写。。。不然总得带着那个id[i].

 

选区_074

 

 

 

hdu 3718 Similarity (二分图最优匹配,KM算法)

hdu 3718题目链接

题意:东西分类作业,有n个东西,k组,m个学生,不同种类的东西用不同的字母表示,相同种类的用同一个字母表示。不同学生和标准答案之间可能表示同一类东西用的字母不同,但是字母只是一个标号(But the LABEL of group doesn’t make sense and the LABEL is just used to indicate different groups. ) 给出事物分类的标准答案和每个学生的答案现在问每个学生的正确率是多少。

思路:用map<char,int>把字母转化成点的标号。然后初始化权值为0. 对于每个学生,o(n)扫一遍统计出w。然后做一遍KM求最大正确数。从而得到正确率。 因为一个map忘记每次清空,WA了一次。。。2A..