ZOJ 3365 Integer Numbers

January 21, 2014 at 8:24 pm

原题地址:http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=3365 今天由于外力因素,没法干其它的事,于是在ZOJ上又水了水,算上这题,终于是AC400题了。回头想想,这个目标应该是在去年,还是前年就应该达成的,时间过得真快,不知不觉又被我水过去了两年么,果然已是拖延症晚期。 题目的大意是说小男孩写了一个连续的整数序列(n <= 50000),然后被腹黑的小女孩修改了一些数字,使得序列不再连续了。小男孩很伤心,希望你在修改尽量少的数字的前提下恢复序列的连续性,要求输出被修改的数字的个数和最终的序列,任何可行解都可接受,是个special judge。 考虑元素array[i],如果保持它不变,那么array[0]必须等于或者修改为array[i] - i,这是确定的,即所有元素都有保持它不变所需要的一个初值。拥有共同初值的元素构成一个等价类。元素最多的那个等价类中的所有元素就是需要保持不变的元素。使用O(n)的时间计算出所有元素的初值,问题就转化为求众数了。 一开始想用hash,后来想想C++没有hash,所以就有map求了一下,220 ms AC.后来发现ZOJ已经支持C++11,托STL设计者的福,仅修改了几行代码就有了unordered_map版本,150ms AC.但作为一个平均复杂度O(n)的算法来说,unordered_map在这个数据量上的表现并不理想。   #include <cstdio> #include <unordered_map> using namespace […]

ZOJ 3710 Friends

January 20, 2014 at 10:02 pm

原题地址:http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=3710 已经很久没有在ZOJ上刷题了,这算是回来刷的第一题,算是一个新的开始。 题目的大意是说有n(<=100)个人,他们之间的某些人互为朋友,这是初始条件。然后如果两个人有共同的k个及以上的朋友,他们就会变成朋友。要求的是通过这种方式形成的新朋友的对数。 最简单的方法莫过于模拟整个过程,把符合条件的人设为朋友,然后更新相应的状态。这里遍历所有的人是O(n^2)的,判断符合条件是O(n)的,然后外层加一个while(changed){}的循环。但这样复杂度就比较难以分析[分析不出来,sigh],就最坏的情况来看,如果每次只有一对新人符合条件,最后又是所有人都成为朋友,那么这个while循环就是O(n^2)的,所以整个算法是O(n^5)的。这个最坏的情况是否能达到,暂时分析不出来了。 这时候我是这样的两个思路: 1.把模拟的代码码出来,提交看是否AC,过了万事大吉。 2.想一个复杂度更小一点的算法。 我想着出题者一定不会只给这么一个模拟的复杂度都看不到的算法出来,而且说不定会把直接模拟的给卡死,所以直接跳过了第一步[事实证明是我想太多了,直接模拟是可以AC的] 幸好这道题也算有一个我比较满意的,以我的智商也能快速想到的O(n^3)的算法。当两个人有共同的k个及以上的朋友时,他们会变成朋友,并且它们变成朋友影响到的关系是O(n)的。比如A和B变成了朋友,那么唯一影响到的是所有A的朋友和B多了一个共同朋友A,所有B的朋友和A多了一个共同朋友B。所以只要维护一个记录两人共同朋友个数的数组common[][],初始化时把>=k的两个人存入队列(或者堆栈)中,每次从中取出两人,O(n)地更新,并把其中大于等于k的两个人存入队列中,重复上述操作直至队列为空。由于关系对最多O(n^2),所以队列里最多这么多个元素,而每次更新是O(n)的,是个O(n^3)的算法。 AC的时间是260ms,暂时还没有想到更好的算法,代码还可以做一些优化,但达不到目前最优的20ms,不知是如何实现的。 #include <cstdio> #include <cstring> #include <queue> using namespace std; int […]

ARP协议简介[摘自计算机网络总结第五章--网络层]

January 1, 2014 at 7:09 pm

在Internet上每一个机器都有一个或者多个IP地址,但IP地址并不能直接用于发送包,因为数据链路层的NIC[Network Interface Card, 网卡]不识别IP地址。对于以太网卡而言,每一张以太网卡有IEEE所提供的一个唯一的48位的以太网地址,我们需要把IP地址通过某个方式转化为以太网地址。 我们考虑一下的一个简单的局域网: CS网络和EE网络通过路由器连接,各自网络内则通过以太网交换机连接。我们考虑主机1要向主机2发送一个包。[注:通常主机1首先访问的是主机2的域名,然后发生域名解析,这个过程我们在第七章中讲述]目前,我们认为主机1直接访问的是主机2的IP地址。主机1的IP软件可以知道主机2和它在一个网段,这意味着可以不与路由器(网关)打交道,但是主机1的IP软件并不知道主机2的以太网地址,所以无法发送包。一个可行的方法是在某个地方保存一个IP地址到以太网地址的映射表,但对于大型网络来说,要维持这个映射表的实时性很不容易;一个更好的主意是主机1向自己所在的以太网段进行广播,询问谁拥有了这个IP地址。这个广播会发送到以太网段的每一个主机上,每个主机检查自己是否拥有这个IP。上例中,主机2会应答,并返回自己的以太网地址E2,由此主机1便可以向E2发送包。用来进行广播询问和获取应答的协议就是ARP[Address Resolution Protocol]。几乎所有Internet上的机器都运行这个协议。ARP相比于维护一个映射表文件简单许多,它大大减轻了系统管理员的负担。 上面描述的ARP协议的简单运作可以进行很多优化。首先,ARP协议要对返回的结果进行缓存,这样在短时间内访问同一地址时就可以不用发送第二次广播。当主机2要给主机1应答的时候,它同样需要进行一遍广播,这可以通过主机1在广播时包含自身的一个IP到以太网地址的映射来避免,当主机1的ARP包发送到主机2时,这个映射就写入了主机2的缓存[所有被询问到的主机都可以缓存这个映射]。为了保证映射表的实时性,一种方法是在几分钟后清空缓存;一个更聪明并可以优化性能的方法是当一个主机的以太网地址发生变化时向所有机器发送广播,这个过程通常是以一个询问自己IP对应的以太网地址来实现。正常情况下,询问自己IP对应的地址不会收到任何应答(因为其它人都不是这个IP,这就好比在一群互不相识的人中询问自己的身份证号对应的名字一样),但会产生让所有主机更新自己的IP-以太网地址映射的附带效应,这通常被称为无故ARP[gratuitous ARP]。无故ARP还具有查错的功能,如果真的获得了应答,说明当前网段存在了冲突的IP地址,这可以警告管理员马上修复这个问题。 下面我们考虑不同网段间传输时ARP协议的工作,假设主机1想要向主机4发包。当主机1试图向主机4发包时,IP软件可以识别出主机4在不同网段,此时就会试图把包先发给路由器,也被称为缺省网关[default gateway],通常缺省网关的IP地址是当前网段的最短地址,对于面向CS网络的端口的IP而言,是192.32.65.1。要向缺省网关发包,需要知道网关在CS端接口的IP地址,这通过一个正常的ARP广播实现,于是获取了E3。路由器如果路由器不知道主机4,它同样会使用ARP广播,最终路由器可以把包正确地发给主机4。 如果主机1没有设置缺省网关,或者IP软件并不讲包发给缺省网关,同样可以在主机1不知道主机4在不同网段的情况下发送包给主机4,我们讲讲这个的实现。主机1不知道主机4在不同网段,于是发送ARP包,此时E3收到了ARP包,并告诉主机1它即是主机4。然后E3获取主机1发送的包并发送给主机4,这个解决方案称为代理ARP[proxy ARP]。