- 浏览: 1654237 次
- 性别:
- 来自: 北京
文章分类
- 全部博客 (405)
- C/C++ (16)
- Linux (60)
- Algorithm (41)
- ACM (8)
- Ruby (39)
- Ruby on Rails (6)
- FP (2)
- Java SE (39)
- Java EE (6)
- Spring (11)
- Hibernate (1)
- Struts (1)
- Ajax (5)
- php (2)
- Data/Web Mining (20)
- Search Engine (19)
- NLP (2)
- Machine Learning (23)
- R (0)
- Database (10)
- Data Structure (6)
- Design Pattern (16)
- Hadoop (2)
- Browser (0)
- Firefox plugin/XPCOM (8)
- Eclise development (5)
- Architecture (1)
- Server (1)
- Cache (6)
- Code Generation (3)
- Open Source Tool (5)
- Develope Tools (5)
- 读书笔记 (7)
- 备忘 (4)
- 情感 (4)
- Others (20)
- python (0)
最新评论
-
532870393:
请问下,这本书是基于Hadoop1还是Hadoop2?
Hadoop in Action简单笔记(一) -
dongbiying:
不懂呀。。
十大常用数据结构 -
bing_it:
...
使用Spring MVC HandlerExceptionResolver处理异常 -
一别梦心:
按照上面的执行,文件确实是更新了,但是还是找不到kernel, ...
virtualbox 4.08安装虚机Ubuntu11.04增强功能失败解决方法 -
dsjt:
楼主spring 什么版本,我的3.1 ,xml中配置 < ...
使用Spring MVC HandlerExceptionResolver处理异常
由于不符合参赛条件,未能参加百度之星,看了题目还挺有意思,把题目放着有空做做。
2009年5月30日19:00-22:30(由于第二题出错,比赛时间延长半小时),2008百度之星大赛在线资格赛(初赛)展开。百度爱好者(Baiduer.com.cn)在第一时间给大家带了初赛题目。第一场初赛共四题,分别是火柴游戏(250分)、电子商务平台商品推荐问题 (300分)、争车位(300分)和葫芦娃 (350分),总计1200分。 1. 火柴游戏(250分) 题目描述 在百度,同事们之间喜欢交流游戏。其中,火柴游戏是一个比较经典的例子。游戏的规则很简单:恰好移动一根火柴,使等式成立。如下面的等式可以变成3+6=9(还有其他解):移动哪一根火柴能使等式成立? 下面是所有火柴数字的样子 请你写一个程序,找出所有的规范解。所谓规范是指: * 只能改变数字,不能改变符号; * 数字和符号的组成方式必须严格的和图示的一样(减号由一根火柴组成); * 新等式必须形如a+b=c或a-b=c,其中a、b、c都是不含前导0的非负整数。 当然,最重要的是:新的等式必须在数学上成立。 输入格式 输入仅一行,为一个格式为a+b=c或a-b=c的表达式,其中a、b、c均为不含前导0的非负整数。表达式长度不超过100,且不含空白字符。因此,加号/减号紧跟在a的后面、 b紧跟在加号/减号的后面、等号紧跟在b的后面、c紧跟在等号的后面。 输出格式 输出所有规范解,按字典序输出(请注意:输出顺序不对将不得分)。无解时,仅输出一行-1。 样例输入1 9+5=9 样例输出1 3+5=8 3+6=9 样例输入2 1+1=2 样例输出2 -1 测试数据 共10个测试点,基本参数如下表: 裁判问答: Q:第一题的表达式长度不是只有5吗? A:可以多位整数 Q:把某根移出来再移到原来的位置上算不算移动? A:不算 2. 电子商务平台商品推荐问题 (300分) 题目描述 百度网络交易平台(“百度有啊”)是建立在百度旗下独有的搜索技术、强大社区资源基础上的中文互联网领域最具规模的网上个人C2C交易平台。伴随着“百度有啊”的成长,“有啊”的顾客也蜂拥而至;面对如此大量的用户,如何把平台上数以千万计的商品按一定的规则推荐给他们以促成交易,是“百度有啊”面临的重要问题。 在本题中,假设有M个用户和N种产品,每个用户的浏览历史可以用一个N维特征向量 X描述:Xi=1当且仅当该用户曾经浏览过商品i。如果用户A和用户B曾浏览过(部分)相同的商品,我们说用户A和用户B相似;如果用户A和用户B相似,或者用户A和一个“与用户B相似”的用户相似,则需要把用户A和用户B划分到同一个用户群。该用户群中所有用户的特征向量的“按位或” 便是整个用户群的特征向量——它表示至少被其中一个用户浏览过的商品集合。 每当一个新用户到来时,可以计算出它和所有用户群之间的相似度。假定他的特征向量为A,用户群的特征向量为B,则: 其中计算特征向量模长时使用的是二范数,即所有维度数值的平方和的算术平方根。 接下来,我们应找出该用户最接近的用户群,并从该用户群购买过的商品中选三个商品进行推荐。一般来说,一个商品被购买的次数越多,就越应该被优先推荐(若购买次数相同,优先推荐id值小的商品),但为了避免马太效应,我们需要做一个特殊处理:不推荐最畅销的商品(如果有多个商品的购买次数都是最多的,则它们都不应该被推荐, 为简单计, 如果所有商品的购买次数都一样的话就都不推荐了)。另外,推荐给用户的商品不能是他已经购买过的商品。 如果从最接近的用户群中无法推荐出三个商品,应从次接近的用户群购买的商品中以相同的规则补充,以此类推,直到选出三个推荐商品,或者无法选出更多商品。 测试数据保证任何一个用户不会跟两个不同用户群的相似度相同,因此商品推荐的结果总是惟一的。 注意:如果用户浏览记录跟某用户群的相似度为0,则在任何情况下都不从该用户群购买的商品中推荐。 输入格式 第1行:M、N,分别是平台用户数和商品总数。0 < M,N <= 100 000 第2行:K,表示接下来有K行记录。0 < K <= 100 000 第3~K+2行,每一行是一次用户的浏览-购买记录,记录格式为: uid i1,i2, …,ip b1,b2,…,bq 其中uid是不超过M-1的非负整数,代表用户id。i为本次浏览的商品id集合(无重复元素,元素顺序无意义),而b为该用户在此次浏览后购买的商品集合(无重复元素,元素顺序无意义)。i中的每个元素均为不超过N-1的整数,b是i的子集。q <= p <= 50。注意:同一个用户ID可以对应多条记录 第K+3行:Q,表示接下来有Q次查询。0 < Q <= 125 第K+4~K+Q+3行:每一行是一次用户的浏览记录,格式为 uid i1,i2, …,ip 含义类似于浏览-购买记录。注意:用户群划分方式完全取决于第3行开始的K条记录。这里的查询不会导致用户群划分方式的变化(在实际的系统中,用户群数据也是定期更新,而非实时修改)。 输出格式 对每个查询输出一行,为推荐的最多三个商品的id(为不超过N-1的非负整数),按推荐度降序排列。如果没有任何可推荐的商品,输出NONE;如果有商品可推荐,但不足三个,应全部输出。 样例输入 9 12 8 0 0,1,2 1 1 3,4,5 3,4 2 1,5 1 3 6,7 6,7 4 8,9 8 5 8,10 8,10 0 11 11 8 6 6 3 6 0,1,2 1 0,1,2,6 3 8,9 样例输出 3 4 11 11 7 10 PS:原样例有错,于22:45分修正样例 样例解释 首先对购买历史进行预处理形成用户群,然后对每个用户群购买的商品按购买次数进行排序,结果如下: 接下来处理查询。 输入:0,1,2 输出:3,4,11 此浏览记录与用户群0最接近。根据规则推荐3,4,11 (1是最畅销商品,不推荐;对于被购买数量相同的商品3和4,优先推荐id值小的商品) 输入:0,1,2,6 输出:7,11 此浏览记录与用户群1最接近,根据规则推荐7(6是最畅销商品,不推荐);由于不足三个商品,从次接近的用户群0中推荐,推荐11 (1是最畅销商品,3、4是购买过的商品);仍然不足三个商品,但是已无更多商品可以推荐。 输入:8,9 输出:10 此浏览记录与用户群2最接近,根据规则推荐10;不足三个商品,但是已无更多商品可推荐。 测试数据 共20个测试点,基本参数如下表: 3. 争车位(300分) 题目描述 争车位是目前SNS网站上比较热门的游戏之一。假如小明有N个好友和M辆车。每个好友都有K个车位。这些车位可能停放了小明的车,也可能停放了其它人的车,还能没有停任何车辆(空车位)。在当前状态中,小明的M辆车全停放在他的好友的车位上。 任务一:考虑如下的移车规则: 1. 必须按一定顺序依次移动自己的车,而不能移动别人的车。 2. 每辆车只可以移动一次。 3. 车只能从原来的位置移到空车位处,不能移动到一个已停放了车的车位(无论这辆车是谁的)。移动后,原来的位置就成了空车位。 4. 只能跨好友移车。也就是说,一辆车不能从某好友的车位移到这个好友的另一车位。 请帮助小明把他的所有M辆车都移动一遍。 任务二:考虑如下的移车规则: 1. 每个车位都对应一个金额。当小明把一辆车最终停在某个车位时,将会得到该车位对应的金额。 2. 不一定需要把所有车都移一遍,但只有移动前后处于不同车位的车才能得到对应的金额。 3. 可以把自己的车开到附近的空地上(那里足以停下他所有的车)作为临时中转。因此车不必依次移动,每辆车也可以多次移动。但请注意:所有移动结束之后,每个车位最多只能停一辆车。 4. 和任务一相同的是:仍不许动其他人的车,且每辆车在移动之前和所有移动结束后所在的车位仍必须属于不同好友。特别地,不许最终把一辆车停到用于中转的那个空地上。 请帮助小明获得最大的总金额。 输入格式 第1行包含一个整数T,即任务编号(T=1或2)。 第2行包含两个整数N、K,分别表示小明的好友数和每个好友的车位数。以下N行每行有一个包含K个字符的字符串,描述每个好友当前车位的状态。其中‘#’ 表示该车位停放的是小明的车;‘*’ 表示该车位停放的是其它人的车; ‘.’ 表示该车位是空车位。 如果T=1,输入到此结束;否则接下来的N行每行包含K个不超过100的整数,分别表示每个车位对应的金额。 输入据至少有一辆小明的车。 输出格式 如果T=1,输出任意可行的移车方案。假如有M个步骤,则第一行输出M,紧接着M行表示M步的具体内容。格式为:(x1,y1)->(x2,y2),表示把第x1个好友第y1个车位上的车移到第x2个好友的第y2个车位。如果无解,输出-1。 输入T=2,输出一个数字,表示最多的金额总数。 样例输入1 1 3 4 ##*. .#** **** 样例输出1 3 (0,0)->(1,0) (1,1)->(0,3) (0,1)->(1,1) 样例输入2 1 3 4 ##*# .#** **** 样例输出2 -1 样例输入3 2 2 2 #* #* 2 1 1 2 样例输出3 3 测试数据 共20个测试点,基本参数如下表: 题目描述 蝎子精和蛇精为祸人间,葫芦七兄弟准备与之决一死战。不幸的是,七弟不慎被两只妖精抓住,困在了蛇蝎山的囚笼里,其余六兄弟必须尽快去营救。二娃使用千里眼,查看到七弟被囚的位置,但蛇蝎山地势复杂,机关遍布,如何才能又快又安全的把七弟救出来呢?于是,六兄弟请您来帮忙了。 在二娃的帮助下,大家先绘制了一张蛇蝎山的地图,并把能安全停留的地方以点标记。你很快就发现,这些安全点组成了一个六邻接图——每个点都与左上、左、左下、右下、右、右上六个点等距。于是,你以其中两条坐标轴:“左——右”和“左上——右下”,给各点设置坐标(见图1)。只要把囚笼的六个邻接点都占了,然后六兄弟一起施法,就能把七弟营救出来。 图1. 六邻接图及坐标 虽然已经有了地图,但怎样走才能最快的把七弟救出来呢?葫芦兄弟告诉你,他们有两种移动方式: 1、跑步。可在一单位时间移动一单位距离,即从一个点移动到某个邻接点(见图2)。 图2. 跑步移动示意图 2、翻跟头。可在一单位时间沿着一个坐标轴方向移动多个单位距离,但其飞过的每个点上都必须有葫芦兄弟站在那里施法。例如,在点 (0,0)和点(1,1)都有葫芦娃,那么位于点(2,2)的葫芦娃便可在兄弟的帮助下,沿着“左下——右上”坐标轴直接翻跟头到点(-1,-1)(见图 3)。 图3. 翻跟斗移动示意图 另外,为了不引起妖精的注意,每一单位时间最多只有一个葫芦娃能移动,且每个点上只能站一个葫芦娃。由于葫芦兄弟心灵相通,被囚的七弟也能为兄弟施法。 六个葫芦娃的出发位置为(0,0),(1,0),(2,0),(1,1),(2,1),(2,2)。如果按照最快的方案,六兄弟需要多长时间才能救出七弟呢? 输入格式 输入仅包含一行,包含两个整数X, Y,表示囚禁七弟的位置。只要把此点的六个邻接点都占了,就能把七弟救出来。 (X,Y)不会和上述六个出发点重合。0 <= X, Y < 7 输出格式 输出一行,包含一个整数,即营救的最短时间。 样例输入1 3 1 样例输出1 4 样例输入2 3 4 样例输出2 8 样例输入3 0 5 样例输出3 14 测试数据 共30组数据,输出结果近似在[0,16]内均匀分布。 注意事项 •请不要把离线计算的结果保存在源代码中(例如,直接把答案保存在ans[X][Y]中,读取输入后直接输出),否则本题得0分. •请不要特判/猜测/随机打印结果,否则本题得0分。 •今年新增比赛规则: 公布所有选手的源代码。关于运行时限: 每题均有两个时限T1/T2。如果程序输出正确,且程序运行时间为T,则T<=T1时,该测试点得分为100%, T>=T2时,该测试点得分为0%。T1<T<T2时,该测试点得分为(T2-T)/(T2-T1) * 100%。 T1根据参考程序的运行速度和题目难度设定,T2通常取T1的4倍到8倍之间。 具体的T1,T2不公布。百度之星2009程序设计大赛 初赛第一场试题
测试点编号
表达式的长度
1-2
1-10
3-4
10-25
5-6
26-50
7-10
51-100
用户群ID
用户ID
浏览过的商品ID集合
购买的商品ID
0
0,1,2
0,1,2,3,4,5,11
1(2次),3,4,11
1
3,8
6,7
6(2次),7
2
4,5
8,9,10
8(2次),10
测试点编号
M
N
K
Q
1
<=100
<=100
<=100
<=100
2
<=100
<=100
<=100
<=100
3
<=100
<=100
<=100
<=100
4
<=100
<=100
<=100
<=100
5
<=100
<=100
<=100
<=100
6
<=1000
<=1000
<=1000
<=100
7
<=1000
<=1000
<=1000
<=100
8
<=1000
<=1000
<=1000
<=100
9
<=1000
<=1000
<=1000
<=100
10
<=1000
<=1000
<=1000
<=100
11
10000
10000
10000
100
12
20000
20000
20000
100
13
30000
30000
30000
100
14
40000
40000
40000
100
15
50000
50000
50000
100
16
60000
60000
60000
100
17
70000
70000
70000
100
18
80000
80000
80000
100
19
90000
90000
90000
100
20
100000
100000
100000
100
测试点编号
T
N
K
1
1
3
6
2
1
10
10
3
1
10
10
4
1
3
4
5
1
100
100
6
1
10
100
7
1
10
100
8
1
10000
100
9
1
100000
100
10
1
100000
100
11
2
2
4
12
2
10
4
13
2
5
5
14
2
3
4
15
2
20
4
16
2
50
10
17
2
50
10
18
2
10
10
19
2
50
10
20
2
50
10
评论
没搞过这些编程大赛,搞不定这些题目。
发表评论
-
二分查找之变型题目
2010-10-24 12:40 2159二分查找算法在各个公司的笔试面试题大量出现,通常不是简单一眼就 ... -
一道笔试题(创新工厂)解法
2010-10-21 17:44 1855一个帖子http://www.iteye.com/topic/ ... -
[zz]大数据量,海量数据 处理方法总结
2010-08-27 22:24 2273大数据量的问题是很多面试笔试中经常出现的问题,比如baidu ... -
Trie and suffix array
2010-04-13 20:54 1927字典数Trie和后缀数组suffix array是处理字符串操 ... -
金币问题
2009-11-09 08:41 2018今年某公司的笔试题: 一个矩阵地图,每一个元素值代表金币数, ... -
楼梯问题
2009-11-09 08:19 1578hl给我的几道某公司的算法题: 1、 有个 100 级的 ... -
一道考察模拟乘法的题目
2009-11-07 22:37 1423今天hl和我讨论一道题目: 写道 整形数组如a={1,4, ... -
链表归并
2009-11-07 21:40 1038以前gx同学问的某某公司的笔试题,写一下练练(纯手写,没编译过 ... -
找出出现次数超过一半的数字
2009-11-07 21:23 1891hl同学问我一道这个题,想了一种方法,感觉还是不错的,只扫描一 ... -
有道难题以超低分晋级
2009-06-10 11:36 1568有道难题比赛居然晋级了,可以领到一个t-shirt。 -
逆序数/逆序数对
2009-06-09 23:17 3785逆序数是个常遇到的问题,主要有两种解法: O(n^2)的方法: ... -
有道难题topcoder
2009-05-31 23:55 2463今天做了有道topcoder的题目,也是第一次在topcode ... -
一个对字符串很好的Hash函数ELFHHash
2009-05-03 21:41 2283#include<stdio.h> #defin ... -
最大流Ford-Fulkerson算法
2009-04-22 17:33 9696算法导论对最大流算法有很详细的介绍,今天实现了最大流Ford- ... -
大数/高精度加减乘除取模[收藏]
2009-04-16 19:38 5070#include <iostream> #i ... -
带重复数字的全排列
2009-04-16 18:58 3897上次gx同学问我一道又重复数字的全排列的问题,我当时用set保 ... -
差分约束系统
2009-04-15 16:00 3749(本文假设读者已经有以下知识:最短路径的基本性质、Bellma ... -
二分图匹配
2009-04-15 15:40 3731二分图最大匹配的匈牙利算法 二分图是这样一个图,它的顶点可以分 ... -
线段树
2009-03-24 10:58 1688把问题简化一下: 在自然数,且所有的数不大于30000的 ... -
树状数组
2009-03-24 10:39 2347树状数组是一种非常优雅的数据结构. 当要频繁的对数 ...
相关推荐
"百度之星编程大赛历年试题" 是一个集合了百度公司主办的年度编程竞赛——百度之星的历年来试题资源的压缩包。这个压缩包很可能是程序员、计算机科学学生或对算法和编程挑战感兴趣的个人的一个宝贵学习资料。百度之...
根据给定的信息,我们可以分析出这是关于Astar2007百度之星程序设计大赛网络资格赛(初赛)的相关题目及解析。以下是对各题目所涉及的知识点进行详细阐述: ### 第一题:时间线问题 #### 题目描述: 本题要求处理...
"历年百度之星程序设计大赛试题题目" 本 resources 是关于历年百度之星程序设计大赛试题题目的汇总,涵盖了四个不同的编程题目,每个题目都有其特定的需求和评分标准。本文将详细解释每个题目的描述、输入数据、...
2006年的百度之星程序设计大赛复赛中,第四题便是基于这个游戏机制设定的算法挑战。本题要求参赛者编写程序解决Zuma游戏中的消除策略,以达到最高的得分效率。 在Zuma游戏中,玩家控制一个可移动的彩球,目标是通过...
- **选择排序、插入排序等**: 虽然本题未涉及这些排序算法,但在实际编程中也是常见的排序方法之一。 ### 4. 性能分析与优化 #### 4.1 时间复杂度 - **输入读取**: O(n),其中 n 是输入数据的数量。 - **计算 max1 ...
百度之星09复赛题目 8个小时4道题 百度之星程序设计大赛由百度公司发起创办于2005年,旨在为广大程序设计爱好者搭建一个比试身手、切磋交流的平台。09年百度之星程序设计大赛是连续举办的第五届。大赛每年邀请喜欢...
【百度之星试题A+答案】知识点: 这道试题主要涉及的是算法优化问题,具体是关于图标的排列优化,目标是最大化所有图标的“分离度”之和。问题的关键在于如何有效地将不同开发者开发的应用图标进行穿插排列,使得...
【百度之星历年赛题汇总】是一份集合了历年百度之星程序设计大赛的试题资源,适合参赛者准备和学习。这份资料包含多个不同难度和主题的编程题目,旨在考察选手的算法设计、数据处理和问题解决能力。 第一题《连续正...
### 百度之星十年试题集知识点总结 #### 百度之星程序设计大赛概览 - **背景介绍**:“百度之星”是由百度公司主办的一项面向全国大学生的程序设计竞赛,自2005年起至今已成功举办多届。该比赛旨在通过算法挑战激发...
### 百度之星Astar2011程序设计大赛初赛试题分析 #### 第一题:图标排列 在本题中,目标是最优化百度应用平台上的应用图标展示,以提高用户体验。具体而言,任务是计算当来自不同开发者的应用图标以最佳方式穿插...
8. **并发与调度**:在第二个问题中,涉及多支维修队伍的调度问题,这需要一种有效的并发控制策略,确保每小时只执行一条指令,避免冲突和无效操作。 9. **状态机设计**:每个维修队伍可以看作一个状态机,根据给定...
【第四届百度之星决赛题目数据标程】是针对编程竞赛的一项重要资源,主要针对的是ACM(国际大学生程序设计竞赛)和OI(信息学奥林匹克)领域的参赛者。这些比赛旨在提升大学生在算法设计、编程能力以及问题解决上的...
### 百度之星2011(初赛)算法设计题解析 #### 图标排列问题解析 ##### 问题背景及目标 ...通过上述分析,我们可以深入理解百度之星2011初赛中的三道题目,并掌握解决这些问题的关键思路和方法。
这个文件很可能是2008年百度之星第二场初赛的题目集或者解题思路,包含了一定的编程挑战。参赛者或学习者可以通过分析这些题目,了解比赛的题型和难度,以及当时的热门技术方向。例如,这些题目可能涉及排序算法、...