作者归档:Eurce

果壳万有青年大烩杂记

上周天跑去参加了下果壳三周年庆,挺有意思的,趁现在有时间了也稍微写写。

果壳网算是我平时最常刷的网站之一了,很多有意思的文章。这次得知他们在做三周年庆,却是在byr上看到有人发帖子在讨论。大概看了下活动,发现都挺有意思,心血来潮之下便约了克劳汀小姐陪我一起去玩。但由于各个子活动是要分别买票的,我又动作太慢,就只买到了iOS音乐坊指哪儿打哪儿工作坊万有青年烩之“场”的票。但就时间上来说,却是刚好没有冲突地分布在一天的各个时段,于是行程就确定啦。

跟克劳汀小姐见面是在10:30,离上一次约她出来玩已经过了快一年了呢……时间过得实在太快。音乐坊是11点开始,提前入场之后就闲聊了下。此时我才知道她下周竟然要去联合国实习了,在纽约待整整半年!虽然知道克劳汀小姐能力很强,平时也喜欢满世界跑,但能申请到联合国的实习,实在是让我吃惊不小(当然很好地藏在了我深邃平静的外表之下)。

很快主角们就入场了,带着一堆键盘音箱和ipad。总共是5人,其中“键盘哥”(也就是活动主讲人)应该是老大,是北京一所中学的音乐老师。开场调试了下设备,便为我们演奏了一曲加勒比海盗。效果实在是,大赞!!!(可惜没有拍下来……)随后键盘哥也跟我们简单介绍了下他们乐队(Sound Energy)的故事,又讲了讲ipad上创作电子音乐的一些软件。看起来很棒哦,但可惜我实在是对音乐一窍不通……现在的小朋友能有这样的音乐老师,实在是很幸福的事……

音乐会结束后,便跟克劳汀小姐简单吃了下午餐。由于时间上不允许走太远,就近找了间沙县小吃。吃饭的时候也听她讲了讲学校的事啦(老师如何如何push),律师行业的一些事情啦(原来律师和程序员一样,加班很严重,但相应薪水也不低)等等等等。相应的她也对IT行业不太熟悉呢,没有旁人在的情况下我也就毫无顾忌的一通乱吹(千万不要信我啊)……

午饭过后就回到了冈措咖啡继续参加活动。和之前不同的是,这次的指哪儿打哪儿需要切切实实动手参与了。(这次有拍照)

444_0

右上角是电烙铁,那个枪一样的东西是热熔枪,还有一堆镊子芯片导线云云的,动手能力一向不强的我只能强装镇定,不能在女生面前丢我们理科生的脸面啊。总而言之,这次的任务大概如此:芯片内含一个陀螺仪和加速器,需要为它加装一个音频接口,并刷一个开源的Arduino程序进去,这样该芯片便能将运动数据传输出来,进而可以实现对其他设备的控制……不过呢,克劳汀小姐完全没有在听的样子“那个人讲的东西我都听不懂哦,全靠你了”,但我也只是懵懵懂懂。又看到旁边几位仁兄理所当然般二话不说拿起电烙铁就开始各种操作,当时只能说是亚历山大……

无论如何,硬着头皮也是要上的。其实边看示意图,边问人,边有现场技术人员指导,操作起来也还不算太难……当时大概就是这个挫样:

444_1

说起来我好像也是第一次玩电烙铁,其实也不算难用哦,先预热到一定温度,然后把焊锡预先熔解或是边焊边添加在焊接位,稍微小心一点不要短路,就可以了。还有热熔胶枪,其实就是将一根胶棒加热后变成类似胶水样的熔胶,再滴在芯片上以粘合固定音频接口,就可以了~ 旁边的克劳汀小姐虽是文科生,也没有太多阻碍地进行着操作:

444_2

顺便提一下,这次活动的主持人于峰老师也是文科出身的(北大毕业),包括各种开源程序也玩得很溜的样子……实在是……不好意思说自己学的是计算机呢。

大概2个小时之后…………终于做出成品啦!!

444_3

随后便是把芯片交给老师,刷入Arduino程序。上一张老师酷酷的背影:

444_4

刷程序的时候还有点小插曲……由于很多人要刷程序,我便排队等在后面。但看着前面不少人都·失·败·了·。也就是刷程序进去后,无法读取运动数据。实在是很悲惨的事情,老师也无可奈何地说,可以再给你们一套材料,但可能要自己回去做了(时间不够)。终于轮到我了,双手颤抖地交出了我的两颗小芯片。随后悲剧发生了,插上线之后完全没有反应!两个都是!老师还调侃到“这两颗芯片恐怕出自一人之手吧”,我也只能一遍遍默念“注意保持微笑注意保持微笑”。但老师灵机一动地想到可能是USB线的问题。果然,换了另一条数据线后,两颗芯片都能正确工作了!

444_5

可以在屏幕中看到,下方的波浪线是读取到的芯片中陀螺仪记录到x、y、z三个方向的运动情况。实在是很开心……随后也看老师演示了如何用芯片控制摄像头:

444_6

以及四轴飞行器:

444_7

实在是让我大开眼界……尤其是了解到这些芯片设备等等其实一点也不贵……受限的更多是思想而不是物质条件呢……

晚餐是去了克劳汀小姐推荐的糖朝,没办法除了粤菜其他真的吃不太惯……点了牛肉肠、煎萝卜糕、扬州炒饭以及蒜蓉菜心,味道还算可以吧,但茶水有点小失望……(回木马剧场的路上看到了一台白色Ferrari 458 Italia新车…太美了)

晚上的万有青年烩之“场”也是这次果壳三周年活动的最后一幕,就嘉宾知名度来说,确实不如之前的“聚”和“力”,但听完之后还是觉得不少嘉宾很有意思(但很可惜我都没照/录相……),包括开场的二师兄乐队一段他们以前活动的视频)、边周游世界边画画的Odding来自台湾的剧作人小令等等等等……场内的音效则是中午才为我们表演过的“键盘哥”负责的,两个主持人加菲众和小姬也是各种逗趣……实在是太过开心的一晚,真的很久没有这样大声笑出来了。

期间也和克劳汀小姐闲聊了下,发现她的阅读量真的很大。我随口说出的书名、作者,她统统知道。包括最近读的毛姆、加缪,以及王小波、刘瑜、周濂等等。当我试探着问她,“你知道章诒和吗?她的《往事并不如烟》?”,得到回答“废话,这本书还有新版的《最后的贵族》呢”时,真的是发自内心的很开心……这种感觉,仿佛就是来到了另一颗星球,但却发现这颗星球的人竟然和你说同一种语言。

如果要说这次大烩有什么不足的话……大概就是不太守时了。包括各种活动的开始、结束时间基本都延后了……这次的“场”竟然拖到快22点才完。匆匆从会场出来之后,只能打车回去了。按照惯例,还是先送了克劳汀小姐回外交学院。期间路过的长安街,也还是一如既往的美。一年半前给我印象最深的这条街,大概也算是想留北京的一点动因了吧……

最后回到北邮已经22:40了,短信报过平安后也就洗涮休息了。

[POJ 3169]

Layout

差分约束系统。

有n只牛,每只牛i对应x轴上一点di,对于i < j,有di <= dj。存在ml个关系di >= dj – k,其中i < j;又存在md个关系di <= dj - k,其中i < j。要求d[n] - d[1]最大值。若关系无法满足,输出-1;若最大值为无穷,输出-2。 由于题目所求的是限制约束下的最大值,也即需要取大于等于号建立差分约束系统,那么3种边分别有: dj >= di
di + k >= dj
dj – k >= di

初始化除d1外的di值为无穷大,便可以用SPFA求解了。每次当 di + k < dj 时,进行松弛 dj = di + k。 但是……用栈跑SPFA时却无限WA。换成队列一下就AC了。找到了原始数据后又看了别人的程序,最后发现问题出在了判负环上。 基于队列的SPFA是用入栈次数>n来判断是否存在负环的,而姜碧野的《SPFA算法的优化与应用》中深搜的SPFA通过节点是否在栈中判负环是针对递归实现的。而我写的是基于栈的非递归SPFA,用的还是根据入栈次数>n判负环,但却发现很易出现误判。猜测由于深搜SPFA可以说是“盲目”推进的,也即有可能过多地沿回边更新,而导致入栈次数超过n,但实际却不存在负环。例如下图的例子:

435_0

最后的解是d[1..5] = {0, 4, 6, 10, 3},其中结点5的入栈次数高达8次,但仍是无负环的。

在这题中,如果改变邻接表中边的顺序,让深搜SPFA尽量往图的深处推进,就能使用入栈次数来正确地判断负环了。可惜没有找到通用的严格证明……

结论就是:下次还是老老实实用队列判负环吧……

[POJ 2165]

Gunman

计算几何。

题意是,在一个三维直角坐标系上,有平行于xOy平面的n个矩形,其边与x、y轴平行,坐标取值范围(0,1000)。问在x轴上是否存在一点能引出一条直线与所有矩形都相交。

这题读完后,并没有太直观的思路。但由于数据规模不大,考虑用三分法。每次对枚举的double m,按z值的增序遍历所有矩形,维护一个窗口作为能与所有矩形都相交的区域,最后返回相交矩形的数目。基本的想法是,由于矩形是连续且规则的图形,那么若解存在,则必定有最大值为n的单峰存在。但WA了数次后发现,由于返回值是离散的,就无法通过严格单调性来对三分法上下界进行修改了。

随后又发现,m值的所有可能取值其实是有限的,为某两个矩形i和j间(xi,0,zi)与(xj,0,zj)所确定的直线与x轴的交点,这里xi或xj可以是矩形的左或右边界。因此枚举的m值总数是O(n^2)的。而用前面描述的遍历方法便能确定从该点出发是否与所有矩形相交。所以总复杂度是O(n^3)的。在n=100的情况下,是可以AC的。最后跑了235ms。

[POJ 2043]

Area of Polygons

计算几何。

题意是,给出一个多边形的顶点(坐标都为整数)描述,要求该多边形在网格上覆盖的格子数目。

基本思路是扫描线,从左到右,同时维护一个有序数组s,记录当前区间内存在的线段的y值,线段必定是成对出现的,且每对线段间的区域为多边形内部。这样就可以计算每个区间内被覆盖的格子数了。

具体的实现上,首先初始化所有的n条线段,并放入一个表头大小为4001的邻接表中,方便扫描线时将新扫到的线段加入。垂直的线段直接忽略。对线段结构体记录其当前y值,斜率k,终点xr,以及删除标记b。每次处理一个区间的线段时,删除线段即为将标记位置1。对s内的线段排序时,首先将被删除的线段都放到最后,然后若y值不同则按y从小到大排序,否则再按斜率k从小到大排序。

计算每段区间[x,x+1]内被覆盖的格子数时,需要注意若连续的多条线段过于接近,要避免重复计算。同时取floor或ceil时,需要对y值增或减eps,以舍去计算误差。

总体上来说虽然细节较多,仔细思考后还是比较顺利地1A了。不过也写了一整个下午……

[POJ 3130]

How I Mathematician Wonder What You Are!

判断多边形内核。

题意为N个顶点逆时针顺序描述的一个多边形,要求判断该多边形是否有“内核”。所谓“内核”,就是在该多边形内的一块区域,站在这块区域内任意一点观察多边形的内部,都可以无死角地看遍整个多边形。

解这题涉及到半平面的概念。其实就是每条线段都会将平面区域划分成两部分,一部分包含多边形内部,一部分不包含。那么,将所有线段对应的包含多边形内部那一半的平面区域求交集,就得到了多边形的内核(如果存在)或者空集(不存在内核)。

进一步考虑实现问题的话,可以将每条直线描述为ax+by+c=0,那么半平面方程即为ax+by+c>=0,其中a、b、c三个系数,根据直线的朝向以及题目给定的逆时针顺序,a是取-1或1的,进而可以确定b和c。多边形的内核区域,可以抽象为某些点,进一步分析可以发现,若存在内核,则其角一定是某两条边所在直线的交点。由于最多只有50条边,那么可以枚举n(n-1)/2个交点,依次代入n个半平面方程,看是否存在点满足对所有半平面方程都大于0即可。

最近都在练习计算几何的题目。感觉这类题有个特点是比较偏数学公式的推导,对复杂度的要求不会太高。

借这个机会好好复习下各种几何工具吧。

[POJ 3004]

Subway planning

计算几何。

题意是,在二维平面上有n个点(不为原点且不重复),和距离值d,问最少从原点引出多少点射线,可以使得n个点离某条射线的最远距离都不超过d。

这题读完之后……基本是没有任何思路的。稍微分析一下可以发现,射线肯定都是刚好离某个点距离为d的。因此写了一个搜索,对任意一点,若未被覆盖,则(1)顺时侧置射线、(2)逆时侧置射线、(3)不置射线。结果TLE。又想了一些剪枝后,还是妥妥的TLE……

然后发现discuss基本是空的……就又google了一下题解,也去下载了题目的原始数据,花了整整一天时间,总算弄明白了。大致思路如下:

首先转换到极坐标系,并将每个点对应能被覆盖的射线位置范围视作区间,那么就可以将问题转化成区间覆盖问题:由于每个区间都是必定要被覆盖的,可以将区间按起始位置排序后,贪心地选择能按顺序地覆盖最多区间的位置放置射线,这可以通过取当前按序覆盖的区间中最左的右边界值来得到。每次下一个顺序区间无法被覆盖(左边界超过当前射线位置)时,贪心地重置射线位置为该区间的右边界值。所有n个区间处理完后便是最小覆盖射线数。

但这里有一个问题就是,极坐标是一个环形结构,无法确定哪个区间最为最左区间。考虑到这里n<=500,即使枚举每个区间为起始区间,算上排序,复杂度也只是O(n^2lgn),是完全可以接受的。当然这里极坐标的计算形式以及弧度的处理还是有一些技巧的,比如atan2(y,x)函数直接根据y和x值返回取值范围在(-PI,PI]范围的弧度值,另外标程还用到了一个fmod(a,b)函数,是对浮点数算a - b*k = c,abs(c)

ps: 今天老师说可以公费买一些书(归实验室但实际是给我们看),京东也很合时宜地给了我几张优惠劵……结果便一发不可收拾了……稍微列下书单: 语言类: Ruby元编程
Python核心编程
Python Cookbook
K&R
Erlang/OTP并发编程实战
Node.js开发指南
JavaScript语言精髓与编程实践

算法类:
TAOCP卷1
TAOCP卷2
TAOCP卷3
CLRS

IT文化类:
谁说大象不能跳舞?
代码的未来
浪潮之巅
图灵的秘密:他的生平、思想及论文解读

其他:
HTTP权威指南

其中有些是看过但出了新版的,比如CLRS、浪潮之巅;有些是可以有计划地读完的,如IT文化类的其他几本;有些是参考书,如语言类和其他;有些是纯粹是买来拜的……我不说你也知道是哪些……

[POJ 1988]

Cube Stacking

并查集。

题意是,原有30,000个栈,每个栈中有一个cube,总共最多100,000个操作,每个操作可以是将一个栈叠到另一个上,或者是求某个cube下方有多少个cube。

很明显的”由cube指定的stack号来作叠置操作”暗示了要用并查集的。但以前写过的并查集仅能够实现(1)路径压缩;(2)按秩合并。也即f[i]表示的值可以是(1)栈编号(当f[i]>=0;(2)栈大小(当f[i]<0)。由此,不难推出,如果额外增设一个p[i],记录每个cube到栈顶间有多少个cube,那么就可以有: 栈大小 – 上方cube数 – 1 = 下方cube数。 进一步分析p[i]的更新方式,每次作union(a,b)时,是将a整个放在b上的,也即此时p[b]=f[a]。但如果要使p[i]值正确,压缩路径前要记录原父cube,递归处理压缩路径后,将父cube的p值累加到本cube的p值上。 跑出来只有500+ms,改成非递归可能才会快点。

[POJ 1177]

Picture

题意大概是,给出N个矩形的描述,矩形间可能有重叠,问最后图形的总周长。

这题和早上做的November Rain都被人分类成线段树,但我愣是没有想明白,这个线段树可以怎么用。也都是数组处理了一下就A了。

说说这题,首先周长可以划分为平行于x轴和平行与y轴两部分。这两部分是独立的,可以分类处理,且处理方式类似。下面以与x轴平行为例说明。

首先将所有点坐标离散化,然后用一个struct数组,记录每条边的:y坐标、起止x离散坐标、下边界标记b(是某矩形下边界则为1,否则为0)。然后将2N条边先按y从小到大,再按x从小到大排序。初始化一个全0的数组t,大小为离散化x坐标的个数,表示某段边被覆盖的次数。然后遍历struct数组,对每条边,更新其包含的各线段j的覆盖情况,若边的b==1,则t[j]++,若此时t[j]==1则表示为图形的下边界,为周长的一部分;若边的b==0,则t[j]–,若此时t[j]==0则表示为图形的上边界,也为周长的一部分。

与Y轴平行的边,处理方式类似。由此便能在O(2N*lg(2N)+2NK)的时间内计算完整个图形的周长了,这里K是每条边包含离散线段的数目。貌似K最多是O(N)的,但题目没有这么刁钻的数据,最后也就跑了16MS。

[POJ 2888]

Magic Bracelet

数论。

本来这题是在分类表里靠后的位置的,但由于最近在啃具体数学,第四章讲了“莫比乌斯反演”,就顺势把题做一下。

题意是这样的,有一个长度为n的珠串,每个珠子的颜色有m种,但其中有k对颜色是不能相邻的,问在剔除因旋转导致的重复后总共有多少种可能的珠串。

先讲这题的简化版,是POJ 2154,区别在于没有珠子间不能连接的限制。

其基本的思想仍然是Polya定理。但是这里由于n值太大,无法直接枚举出所有的置换群。于是需要考虑将具有相同数量循环节的置换群合并处理。具体的合并方式是要利用到欧拉函数phi()的性质的。总共的置换群有n个,对n的每个因子d,有n/d个循环节的置换群其每个循环节长度为d,而这样的循环群总数是phi(d)个。又因为欧拉函数满足sum_{d\n} phi(d) == n,因此计数式子就可以转化为 (sum_{d\n} phi(d) * n^(n/d)) / n。计算phi(d)的时间复杂度是O(lgd),而n的因子总数是不超过1000的(最多9个不同因子),n的n/d次方是可以在O(lg(n/d))时间内计算得到的,由此问题便能在合理时间内求解了。

另外就是计算的时候,要注意利用模运算的性质,使用int来处理(比long long快很多),同时尽量减少进行模运算的次数,否则还是会TLE的。

下面是2154的代码:

回到2888。这题额外增加了珠子间的连接限制,对应的处理方式是这样的:初始化矩阵a[m][m]元素全为1,若i和j不能相邻,则a[i][j]=a[j][i]=0,然后计算b = a^d,则长度为d的珠串其总可能数是sum{b[i][i]}。这里当i<=j时,(a^d)[i][j]表示的是,以种类i开始长度为d,结尾能够与种类j的珠子相连的珠串总数。至于为什么是这样,推一下就明白了。 于是这里计数式子就变成了(sum_{d\n} phi(d) * sum{(a^(n/d))[i][i]}) / n。 落实到具体实现时,在对n做除法时,要转化成乘以模运算下n的乘法逆元。前面的每一步处理也要控制好在int的范围内以及限制模运算的使用次数。

虽然上面写了这么多但很多都是现学现卖的OTL。不过数论还真是很有意思的东西……

[POJ 3286]

How many 0’s?

数学。

比较不擅长的题目类型,虽然一直以来都挺喜欢数学的 ;)

问的是输入unsigned int m和n,问[m, n]的所有数字打印出来后,总共包含多少个0。

题意非常明确的,其实就是要推出函数calc(d),能返回0到d所有0的个数,那么calc(n)-calc(m-1)就是结果。

对于某个具体的d,这里基本的思路是将其包含的数按范围划分,例如d=109250时,首先拆成[0, 100000],[100001, 109000],[109001, 109200]和[109201, 109250]。那么就可以分情况讨论各个范围内数字所含0的总数,最后累加起来即可。

这里采用的方式是从高位开始拆数。例如,将[0, 109250]包括的0拆成三部分:(1)[0, 100000],(2)[0, 9250],(3)以”10″为前缀导致[0, 9250]额外引入的0。那么就可以对[0, 9250]迭代地计算其中包含的0了。也即,此时算法复杂度是和d的位数线性相关的,基本上是O(1)。下面分别讨论三部分含0数目的计算方法。

(1)这里可以预处理,例如a[i]=10^i时,分别计算[1, a[i]]以及[a[i]+1, a[i]*2]范围内所含0的总数,设为b[i]和c[i]。例如a[2]=10^2=100时,b[i]为[1, 100]内0的总数,c[i]为[101, 200]内0的总数。这样处理的原因是,(1)中每次都是拆最高位的,这样当最高位为k时,即为b[i]+(k-1)*c[i]。这里b[i]和c[i]有递推关系,当然其实暴力打表也可以的。

(2)这部分是迭代的,和原本的d处理方法相同;

(3)这部分比较麻烦。首先要记录前缀中含0的个数,然后由d去除最高位后剩余的dd计算需要增加多少个0。这里分情况讨论一下即可。如果前缀有j个0,那么最前面的0包括dd*j个,然后再额外处理后面每一位的情况。

看了别人的基本思路,自己推起来也还是磕磕绊绊。表达起来就更是觉得繁琐了……