mightyvoice的博客

    回想这半年，从7月1号回家开始全心准备GRE, 中途上了新东方，然后9.3的GRE, 接着10.22的托福，结果托福成绩出来本想放弃申请，最后因为每一项都基本能过线然后决定申请，这个时候已经11中下旬了，中途做了linux编程课的作业，考了试，参加了个比赛。从考完GRE开始就开始选校啊，构思PS和推荐信这些。申请开始后，网上各种填表，各种发帖问问题，各种纠结，跑了几次档案馆，跑老师那里签推荐信也是好多次，晚上熬夜写PS，PH，还有推荐信，改了进一个月的文书，白天复习期末加各

   忙了20天的申请，这段时间感觉压力很大，中途又抢了明年3.4重庆的托福，现在期末考试再加申请还有准备托福让我一天感觉总是忙不过来。从前段时间的压力大变成了现在每天像打鸡血一样，每天能很早起床去图书馆占雅间，每当又完成了某个申请的步骤，我都会觉得找到了A题的那种感觉，所以最近把一切都看开了，大不了也就是是10封rej信，没走我继续读我的研，学分也修了……

    开学考G前我对自己的定位和目标就是：只要我这学期能把考GT, 修学分，申请，这三件事做完了，不管结果如何我都达到了自己的目标。即使结果很挫，但是从这三件事里面都能学到以后工作了完全没多少机会学到的东西。从准备G到现在我中途至少有50次向放弃，因为经常我会觉得，留在成都，又有GF，以后工作会有房子也会有滋润的小日子也会有。。。每次郁闷

今年下午去把复赛的软件现场通过了测试，然后信息论也复习得差不多了，开始真正打酱油了！

    本科期间有出国的想法，但是同寝室一兄弟要去美国读硕士据说2年50w，于是我就绝望了，然后再也没去了解过出国的东西，大四了才知道居然美国可以本科直博而且有全奖！隔壁寝室兼鼓手朋友得了rutgers的offer我才知道原来电子科大学生也是可以拿全奖的，当年看了一本相信很多人都看过的书《哈佛女孩刘亦婷》就以为拿offer必然是神人和名校出生，进了这个误区自然就没继续去了解出国的东西，范了严重的战略性错误！

    从小看了很多牛人的故事，多少在美国读的博，那是便对美国的学术氛围很向往，因为以前不知道有工科这东西，反正

    晕啊！快一年没写博客了，这一年妈的又是各种酱油啊，结果最关键的酱油还没打好，明年继续酱油……

   很久没发现新歌了，最近突然发现了一些新的歌，至少是以前没听过的歌，稍微总结下，各种风格：朋克，独立，金属，流行，各种口味啊。

1. OK三明治 - 去海边。 在《我爱摇滚乐》上发现的成都新乐队，流行朋克，英伦，电子风的，很欢乐很清新啊！电子配乐的旋律很赞！歌词多青春的，女主唱声音还可以吧，总之很青春，旋律很赞！

2 . OK三明治 - 青。依旧很舒服的旋律，很青春的歌词，难得让我看下歌词……

3.  Loser - The First Time - 《Just Like You》。 0

最近觉得很颓废，虽然态度上还多认真的，但是感觉精神上异常颓废， 我现在很怀念那段时间的充实，那种每天都能完成一点任务的感觉太好了， 更怀恋那种被逼上绝路完全断了后路一条路走到黑的感觉。发现近一个月来我没找到任何前进的迹象，客观上没有堕落， 精神上已经堕落了……

题意：求第i个满足这个性质的数：这个数能表示成某个数的各位的乘积，例如6满足这个性质，因为6 = 1*2*3, 所以是123各位的和。最后答案不超过10^18。

     易知这个问题等价与：求第i个这样的数x, x = (2^a) * (3^b) * (5^c) * (7^d). (a,b,c,d >= 0). 关键是最后这个答案比较大，复杂度不好把握啊， 题里也没说要有多大的一个表。最晚移动通信课无聊想到一个简单的方法貌似不会超时。

     算法：用一个ans数组存满足性质的数， 初始只有一个1， 设2个指针tail和head，head指向当前最后一个数，tail指向当前要进行扩展的数，每次扩展分别对当前的数乘以2, 3, 5, 7，用一个set保存已经得到的数， 如果乘积还没得到就加入到ans和set中。如果乘积大于10^18就抛弃。 关键是最后这个循环怎么停止呢， 因为不知道小于10^18的数一共有多少个。这个时候就能发挥tail和head的作用了， 易知扩展停止的条件就是tail > head。 于是代码就出来了，最后500ms，如果用hash的话应该快些。

    看了Amber大神的论文，醍醐灌顶啊，虽然还有点地方没彻底弄明白， 里面推荐了这题。

    最小点权覆盖，即找出图的一个子点集V1，对于图的每一条边e(u, v), u属于V1或者v属于V1，且V1中各个点的权值之和最小。 如果不看论文我是打死想不到和最小割扯上关系，虽然都是求最小。 那天晚上整理了一下2者转化的思路。

    首先建网络流图： 增加源点和汇点，对于原图边e(u,v). 令c[u][v] = oo, c[s][u] = W(u), c[v][t] = W(v).。设权重都大于0. 这样，显然边e(u,v)不可能在最小割C[S,T]中，否则就不是最小割了。 所以对于每一条路径s--u--v--t, 根据割的定义， 那么3条边s--u, u--v, v--t至少有一条边在割边集里。因为u--v不在割边集里，那么s--u或者v--t在割边集里，于是对于原图每一条边u--v, 都有u或者v在割集中。 所以根据建图的赋值最小割边集每一条边的容量对应一个点的点权。综上：最小割里的点能覆盖原图每一条边，且最小割的容量对应这些点的点权，于是最小割容量就对应最小点权覆盖。