Welcome to dongming's space

快乐女生

刘惜君

早上在飞鱼秀上听到Michael Jackson去世的消息。

震惊，沮丧，失落。

我不是Michael Jackson的粉丝，但是仍难摆脱他的离去带来的伤感。

虽然带着种种的负面新闻，但对大多数70后和80后来说，他仍然是那个时代的标志。

伴随着自己的成长，儿时的巨星开始离去！！！

 

愿安息。。。

转眼间已经是两年的光阴，研究生的开题同时已经在眼前了。

时间这东西还真是快，特别是在你回头看过去的时候，就愈发显得快了。

前不久和blrc的朋友们小聚，一起开心的日子似乎就在眼前，其实已经一年有余了。好在大家一切都好。还是有些想老马老张的。恩

前几天波说要回北京工作，心里很是高兴，可是由于种种原因未能实现，伤感之余只能遥祝老友快乐平安。

家里的小丫头保了研，去公司实习了，据说表现还不错，恩，应该不错了，她很聪明。

小铭还在为工作辛苦奔波，哥们，别紧张，你是小铭，没问题的。

小四的房子着实不错，我喜欢。过几天我还得找你辅导一下ubuntu（再此一并感谢shuai的免费刻盘服务）.

似乎自从脸上长了小包，好久没有喝酒了，周末大博生日+党硕庸晓聚会，喝了不少，也算过过瘾。

后来总结，洋酒始终不及中国酒好，无论味道，感觉，还有价格。

回主题，开题喽，不是很忙，但是在努力的让自己忙起来。

那句话怎么说来着？厚积勃发！哈哈！

据说哥哥后天要考G了。

你还别笑，哥哥就真就考G了。

等成绩出来了你也别笑，哥哥还就真就考这么多了。

哇哈哈。

 

工作的工作，结婚的结婚，买房的买房，玩车的玩车。

 

咱最近落后了点！！！

恩，接下来得一年会更落后！！！ 

今天土了一把，参加了一次百度之星程序设计大赛，希望鄙视百度的同志们不要鄙视我^_^

比赛指定用C 或者 C++ 编写程序。由于对C++不是很熟。所以选择了那久违的C.突然间让我找回了大二时C语言上机考试的感觉。不过百度出的题远远不及我们晏海华老师出的题有难度，算法部分其实很容易，大部分时间都花费在了IO上面（不要笑话我，同志们，我估计现在没有几个人能记住怎么写一个简单的输入输出了。哈哈哈）

嘿嘿，具体我的成绩怎么样呢，说了也不怕丢人，只要以后的老板不看到这篇blog就好，比我当年本科上机考试还差——那个时候是60分，这次在打个折。打几折就不要说了。

朋友说有几家大牛公司要的人都是算法牛的（不要误解，不是说百度），看来要学习喽。

 

 

试题如下，一共四题，这里是后三个，有兴趣的写着玩玩吧，估计让晏海华作能够得满分：

 

你尝试过在百度上使用site inurl语法查询吗? 如果还没有的话可以试一下:)
如输入 site:www.baidu.com inurl:news
则会搜出所有在www.baidu.com站点上的包含"news"子串的url。

现在我们有一个inurl查询列表和一个url列表，你能找出所有至少被查询过一次的url吗？

输入格式
输入第一行是一个整数n，表示一共有n个查询。以下n行每行一个查询。查询的site部分和inurl部分中间恰好用一个空格分割，且每行不包含其他空格。下一行是一个整数m，表示url列表中一共有m个url。以下m行每行一个url。

输出格式
每个url输出一行。如果至少符合一条查询，输出1，否则输出0。

输入样例 例
3
site:www.baidu.com inurl:/more
site:zhidao.baidu.com inurl:/browse/
site:www.sina.com.cn inurl:www20041223am
7
http://www.baidu.com/more/
http://www.baidu.com/guding/more.html
http://www.baidu.com/events/20060105/photomore.html
http://hi.baidu.com/browse/
http://hi.baidu.com/baidu/
http://www.sina.com.cn/head/www20021123am.shtml
http://www.sina.com.cn/head/www20041223am.shtml

输出样例 例
1
1
0
0
0
0
1

评分规则

程序将运行在一台Linux机器上（内存使用不作严格限制），在每一测试用例上运行不能超过2秒，否则该用例不得分；

要求程序能按照输入样例的格式读取标准输入数据，按照输出样例的格式将运行结果输出到标准输出上。如果不能正确读入数据和输出数据，该题将不得分；

该题共有6个测试数据集，数据1,2,3,4,5,6的大小分别约为4K, 750K, 1.5M, 6.5M, 12M, 18M。所有查询和url均合法，url均以http://开头。url和查询中可能包含中文。输入文件的每行不超过256个字节；

该题目30分。

 

百度网页采集器(Baiduspider)每天从互联网收录数亿网页，互联网的网页质量参差不齐。百度的工程师们每天都在改进方法来判断一个网页质量的好坏，使质量差的网页出现在检索结果中较后的位置。现在实习生小胖想到一个很简单的方法来判断一个网页内容的好坏，方法如下：
1. 利用数据挖掘技术在互联网语料库中挖掘出一批有特点的词汇，分为好词和坏词两种，好词标上正的权重，坏词标上负的权重；
2. 通过好词和坏词词典对每个网页计算网页总权重：从第一个字开始匹配，找到一个好词则加上相应的权重，找到一个坏词则减去相应的权重，下一次匹配将从找到的词末尾的下一个位置开始。
3. 坏词采用正向最短匹配：从当前匹配位置开始的若干连续汉字，如果形成多个坏词，则只计算最短的那个坏词的权重，下一次匹配将从这个最短坏词末尾的下一个位置开始。
4. 好词采取正向最长匹配：从当前匹配位置开始的若干连续汉字，如果形成多个“有效”好词，则只计算最长“有效”好词的权重，下一次匹配从这个最长“有效”好词末尾的下一个位置开始。
5. “无效”好词的定义：好词的一部分本身是一个坏词；或者好词的一部分与后续相邻的若干字组成一个坏词。

现在小胖已经做好了第1步的工作，有一个好词和坏词的列表（词典），但是由于没有对中文文本处理的程序经验，他想请未来的百度之星们帮他完成这个程序。

输入格式
输入第一行为一个字符串（网页正文）。从第二行开始为词典，格式为“词 空格 词的权重”。权重为一个带符号32位整数。如果权重为正，则为好词，反之则为坏词；不存在重复的词，不存在权重为0的词。
作为“网页”的字符串中同时包含中文和ASCII字符，每个汉字占2个字节。并非“网页”中的所有字都在词典中。

输出格式
输出仅一行，为网页总权重（答案保证不超过带符号32位整数的范围）。

样例输入 例
小胖之喷火龙骑士!!
小胖 6
喷火 -1
喷火龙 -1
火龙 -1
龙 4
龙骑 3
龙骑士 2
骑士 -2
士 3

样例输出 例
7

样例解释
从“网页”中找到的好词为“小胖”和“龙”，坏词为“喷火”和“骑士”。特别要说明一下“龙”被识别为好词的原因——“喷火”和“喷火龙”均为坏词，按正向最短匹配得到“喷火”，接着往下匹配到好词“龙”、“龙骑”和“龙骑士”，但是由于“骑士”是坏词，所以“龙骑”、“龙骑士”无效而“龙”是最长的有效好词。注意题目描述中的匹配规则，好词的“有效”和“无效”只考虑该好词的一部分与后续字是否能够组成坏词，而不考虑和前面的字是否能够组成坏词——样例中的“龙”虽然可以与前面的字组成坏词“喷火龙”和“火龙”，但由于这两个词都是未能匹配成功的坏词，因此对好词“龙”的词性没有影响，可以累积“龙”的权重。

注意事项
输入数据的中文采用GBK编码。
GBK：是又一个汉字编码标准，全称《汉字内码扩展规范》。采用双字节表示，总体编码范围为 8140-FEFE，首字节在 81-FE 之间，尾字节在 40-FE 之间，排除xx7F。总计 23940 个码位，共收入 21886 个汉字和图形符号，其中汉字（包括部首和构件）21003 个，图形符号 883 个。

评分规则

程序将运行在一台Linux机器上（内存使用不作严格限制），在每一测试用例上运行不能超过1秒，否则该用例不得分；

要求程序能按照输入样例的格式读取标准输入数据，按照输出样例的格式将运行结果输出到标准输出上。如果不能正确读入数据和输出数据，该题将不得分；

该题共有10个测试数据集，前7组数据的大小不超过1K字节，数据8和数据9不超过600K字节，数据10的网页正文不超过1M字节。所有数据的词典不超过50,000项，且词典中的词保证由1到5个汉字组成。词典不包含重复的单词；

该题目20分。

 

为了在紧张的上班时间让员工们轻松些，百度休息室里放置着按摩椅、CD、高尔夫套装和Wii游戏机等休闲用品。其中最受欢迎的当然是游戏机。

Wii游戏机有两个手柄，每个手柄使用两节电池（这两个电池可以是不同的品牌），其中至少一块电池没电时该手柄没电。

工程师们在玩游戏时，总是用最简单的方式更换电池：有手柄没电时把所有没电的电池拿走，一一换上新电池即可（有电的电池总是继续使用）。当有手柄没电且没有新电池可用时才停止玩Wii。

告诉你每个品牌电池的使用时间以及该品牌电池的个数，请计算工程师们玩游戏时间的最小值和最大值。

输入格式
输入第一行为一个正整数n，表示电池的种数。接下来n行，每行两个整数L和F，表示使用时间为L的电池有F个（电池不必成对出现，即F可以是奇数）。

输出格式
输出仅一行，包含两个整数，分别表示工程师们的最短游戏时间和最长游戏时间（短的时间在前）。两个整数之间以空格隔开。

输入样例 例
3
3 2
5 2
8 2

输出样例 例
5 8

样例解释
有三对电池，使用时间分别为3小时、5小时和8小时。
方案1：一开始给手柄1使用一对3小时的电池，给手柄2使用一对5小时的电池，则3小时后手柄1没电，换上一对8小时的。再过2小时后，手柄2没电。此时已经没有电池可用了。总时间为5小时。
方案2：一开始给手柄1使用一对8小时的电池，给手柄2使用一对5小时的电池，则5小时后手柄2没电，换上一对3小时的。再过3小时后，手柄1和手柄2同时没电。此时已经没有电池可用了。总时间为8小时。

评分规则

程序将运行在一台Linux机器上（内存使用不作严格限制），在每一测试用例上运行不能超过2秒，否则该用例不得分；

要求程序能按照输入样例的格式读取标准输入数据，按照输出样例的格式将运行结果输出到标准输出上。如果不能正确读入数据和输出数据，该题将不得分；

该题共有15个测试数据集，均满足n<=10, L<=200, F的总和不超过30；

该题目30分。