博客首页
注册
建议与交流
排行榜
加入友情链接
推荐
投诉
搜索：
帮助
我的小屋-----I love it
我的小天地，我的心灵之地
ppzhang.cublog.cn
管理博客
发表文章
留言
收藏夹
博客圈
音乐
· mp3
}
· 我喜欢的flash
· MTV
相册
· 我收藏的机器人
· 我的相片
· MyFriend
· 精美壁纸
文章
· Algorithm
· C sharp 学习
· Data Structure
}
· C sharp 学习
· 软件测试
· English
· 我写的诗
· 我爱文学（现代）
· 我爱文学（古典）
· 我的个人生活
}
· 我的小项目
· Java实践小项目
· Linux学习
}
· 资料收藏
· 我的程序
首页
关于作者
姓名：ppzhang 职业：学生 年龄：20 位置： 个性介绍： 相互学习，相互交流，希望成为好朋友！
||
<<
>>
||
我的分类
文章列表 - 资料收藏
百度之星2008程序设计大赛 初赛第一场试题
<DIV>1. 广告排名区间（10分）</DIV> <DIV>问题背景<BR>shifen广告消费预估系统可以估计出一段时间内一个特定的广告在检索结果中排在各个位置的几率。比如系统对某广告的输出如下：<BR>p1 = 0.03, p2 = 0.08, p3 = 0.04 ……<BR>这说明该广告展现在第1位的概率是 3%，展现在第2位的概率是 8%，展现在第3位的概率是 4%……<BR>问题是：如何给出一个排名估计区间[i, j]，使得广告出现在该区间中的概率大于或等于一个预设值p，同时这个区间所包含的元素尽可能的少。也可用数学语言来描述：给定数p和数列 p1, p2, … , pn，求 i和 j (1 <= i <= j <= n)，在满足pi + pi+1 + … + pj >= p的前提下让j-i 最小。<BR>一般来说，pi只需保留6位小数就足够了。这样，若令ai=106pi，a=106p，则a和所有的ai均为[0,106]之间的整数。这样就避免了对实数的处理。<BR>输入格式<BR>第一行包含一个整数n (1 <= n <= 100,000)。<BR>以下n行每行包含一个[0,106]内的整数，依次为a1，a2，…，an。这n个整数之和保证不超过106。<BR>最后一行包含一个[0,106]内的整数a。保证所有ai之和不小于a。<BR>输出格式<BR>输出仅一行，包含一个整数，即j – i的最小值。<BR>样例输入<BR>7<BR>5<BR>8<BR>4<BR>7<BR>10<BR>5<BR>2<BR>18<BR>样例输出<BR>2<BR>样例解释<BR>a2=8, a3=4, a4=7之和为19，满足条件。而任何两个相邻数之和均小于18。</DIV> <DIV>2. LZW网页判重（20分）</DIV> <DIV>问题背景<BR>有一种简单的网页判重的方法，通过求两个网页内容的最长公共子序列(LCS)长度来判定两个网页的相似程度。如：<BR>（网页A）老师：请用“果然”造句。<BR>（网页B）学生：先吃水果，然后喝汽水……<BR>它们的最长公共子序列为“果然”，长度为2。注意这里的“子序列”并不要求连续。<BR>类似的，下面两个网页：<BR>（网页A）老师：请用“果然”造句。<BR>（网页B）学生：先吃水果，然后喝汽水，果然拉肚子……<BR>最长公共子序列还是“果然”，长度为2。但不难看出，由于“果然”两个字在网页B中也曾连续出现，第二组网页比第一组更加“相似”。为了区分开这两种情况的区分度，我们改用一种称为LZW的理论。为了严格的叙述相似度的计算方法，我们首先定义“文本单元”。<BR>假定网页用一个不包含空白字符（空格、回车换行、水平制表符）的字符串来表示。它只包含纯文本，没有标签。在计算相似度之前，你应该首先对该字符串进行处理，划分成一个个“文本单元”。每个文本单位可以是一个中文字、英文单词（由一个或多个连续的半角英文字母和数字组成，正规表达式为[a-zA-Z0-9]+）、或者一个标点符号。<BR>根据上述定义，同一个标点符号的全角和半角应该被作为不同的文本单元，尽管他们看起来可能很相近；每个单独全角英文和全角数字都应该被看成一个单独的文本单元，而连续的半角英文字母和数字应被看成一个整体。总之，全角的字符可以与中文字同等对待。<BR>这样，网页被看成文本单元序列。例如，网页“内容？１２345６??web2.00#”切分出的文本单元序列为（为了显示方便，用下划线分隔各文本单元）：<BR>内_容_？_１_２_345_６_?_?_web2_._00_#<BR>而网页“why内容相似??1234567890,web#00”的切分结果为：<BR>why_内_容_相_似_?_?_1234567890_,_web_#_00<BR>黑体部分给出了两个网页的一个公共子序列。注意“内容”、“??”分别在两个网页中都是连续出现的文本单元。为了奖励这种情况，LZW规定一段由连续k个文本单元组成的字符串权值为k2。在刚才的例子中，“内容”、“??”的权值均为4。但“00”是一个数字串，应当被看成一个单独的文本单元。所以权值仅为1。<BR>根据上述规则，公共子序列“内容 ?? 00”的权值为22+22+1=9。在所有可能的子序列中，这个权值是最大的。<BR>给定两个网页，求他们的LZW相似度，即所有可能的公共子序列中的最大权值。<BR>注意<BR>1) 输入的网页内容以GBK编码(参见FAQ)<BR>2) 除了大小写英文字母和数字之外的其他半角字符均视为标点符号。<BR>输入格式<BR>包含两行，分别是网页A和B对应的字符串（不包含空白字符）。每行至少包含5个字节，最多包含200个字节。<BR>输出格式<BR>输出仅一行，包含一个整数，为两个网页的LZW相似度。<BR>样例输入<BR>内容？123456??web2.00#<BR>why内容相似??1234567890,web#00<BR>样例输出<BR>9<BR>样例解释<BR>尽管两个网页里看上去都有“123456”但一方面第一个网页中混杂的全角和半角字符，而另一方面，即使全部改成半角字符，由于数字串“123456”和“1234567890”将分别看成一个单独的文本单元，因此无法部分匹配。</DIV> <DIV>3. 钉子与木板（30分）</DIV> <DIV>问题背景<BR>墙上有n个钉子，编号为1, 2, …, n。其中钉子i的横坐标为i，纵坐标初始为xi。可以进行两种操作：<BR>0 k v：竖直移动钉子k，坐标变为(k, v)。<BR>1 s t v：若在高度为v处放一块横坐标范围是[s,t]的水平木板，它将下落到什么高度？换句话说，求出钉子s, s+1, s+2, …, t的纵坐标中，不超过v的最大值。如果这些钉子的高度全部大于v，则木板将落到地上，高度为0。<BR>注意，在T操作时，水平木板只是用来测试的“临时木板”，将在测试后立即被拿走，不会影响到后续测试工作。<BR>输入格式<BR>第一行包含两个整数n, m，即钉子的个数和操作的个数（1<=n,m<=105）。以下n行一个不超过109的非负整数，即xi。<BR>输出格式<BR>按照输入的顺序，对于每个T操作输出一个整数，即该测试水平木板的最后高度。<BR>样例输入<BR>5 4<BR>1<BR>3<BR>5<BR>7<BR>9<BR>1 2 4 6<BR>0 3 10<BR>1 3 5 7<BR>1 3 5 5<BR>样例输出<BR>5<BR>7<BR>0</DIV> <DIV>4. 圆面覆盖(40分)</DIV> <DIV>问题背景<BR>在平面上有一个长为L，宽为W的长方形，左下角坐标为(0,0)，右上角坐标为(L,W)。给定一些圆，第i个圆的圆心坐标为(xi,yi)，半径为Ri。<BR>你的任务是求最小的正实数k，使得把每个圆的半径变为原来的k倍后（即：第i个圆半径变为kRi，圆心位置不变），长方形将被这些圆完全覆盖。换句话说，长方形内部或边界上的任意点均至少在一个圆的内部或边界上。<BR>输入格式<BR>输入第一行包含三个整数n, L, W（1<=n<=50，1<=L,W<=1000），即圆的个数、长方形的长和宽。<BR>以下n行，每行三个不超过1000的正整数xi, yi和Ri。<BR>输出格式<BR>仅一行，包含一个实数k，保留小数点后三位。<BR>样例输入<BR>1 2 2<BR>1 1 1<BR>样例输出<BR>1.414<BR> </DIV> <DIV> </DIV>
查看全文
发表于:2008-06-17 ┆
阅读(131)
┆
评论(0)
JAVA界面编程
<DIV> <TABLE style="BORDER-COLLAPSE: collapse" borderColor=#dddddd cellSpacing=0 cellPadding=0 width=360 align=center border=1> <TBODY> <TR height=60> <TD align=middle width=60><IMG alt="" src="http://control.cublog.cn/fileicon/pdf.gif" border=0></TD> <TD> <TABLE style="BORDER-COLLAPSE: collapse" cellSpacing=0 cellPadding=0 width="100%" border=0> <TBODY> <TR height=20> <TD align=middle width=40>文件:</TD> <TD>java界面.pdf</TD></TR> <TR height=20> <TD align=middle width=40>大小:</TD> <TD>472KB</TD></TR> <TR height=20> <TD align=middle width=40>下载:</TD> <TD><A href="http://blogimg.chinaunix.net/blog/upfile2/080617113427.pdf">下载</A></TD></TR></TBODY></TABLE></TD></TR></TBODY></TABLE> <TABLE style="BORDER-COLLAPSE: collapse" borderColor=#dddddd cellSpacing=0 cellPadding=0 width=360 align=center border=1> <TBODY> <TR height=60> <TD align=middle width=60><IMG alt="" src="http://control.cublog.cn/fileicon/pdf.gif" border=0></TD> <TD> <TABLE style="BORDER-COLLAPSE: collapse" cellSpacing=0 cellPadding=0 width="100%" border=0> <TBODY> <TR height=20> <TD align=middle width=40>文件:</TD> <TD>JavaSwing2-14.pdf</TD></TR> <TR height=20> <TD align=middle width=40>大小:</TD> <TD>808KB</TD></TR> <TR height=20> <TD align=middle width=40>下载:</TD> <TD><A href="http://blogimg.chinaunix.net/blog/upfile2/080617113351.pdf">下载</A></TD></TR></TBODY></TABLE></TD></TR></TBODY></TABLE></DIV>
查看全文
发表于:2008-06-17 ┆
阅读(184)
┆
评论(0)
ADO连接各种数据库
<DIV>1.ACCESS 2000 <BR> <BR> _ConnectionPtr m_pConn; <BR> CString m_sConn="Provider=Microsoft.Jet.OLEDB.4.0.1;Data Source=d:\\db1.mdb"; <BR> m_pConn.CreateInstance("ADODB.Connection"); <BR> try <BR> { <BR> HRESULT hr=m_pConn->Open((_bstr_t)m_sConn,"","",adConnectUnspecified); <BR> if (FAILED(hr)) <BR> { <BR> AfxMessageBox("不能连接数据库 source!"); <BR> return FALSE; <BR> } <BR> } <BR> catch(_com_error e) <BR> { <BR> AfxMessageBox("不能连接数据库 error!"); <BR> return FALSE; <BR> } <BR> <BR> 2.SQL Server 2000 <BR> <BR> _ConnectionPtr m_pConn; <BR> CString m_sConn="Provider=SQLOLEDB.1;Data Source=192.168.3.9;Initial <BR> Catalog=sode"; //sode是数据库服务器192.168.3.9上的一个数据库 <BR> m_pConn.CreateInstance("ADODB.Connection"); <BR> try <BR> { <BR> HRESULT hr=m_pConn->Open((_bstr_t)m_sConn,"sa","mapper",adConnectUnspecified); <BR> if (FAILED(hr)) <BR> { <BR> AfxMessageBox("不能连接数据库 source!"); <BR> return FALSE; <BR> } <BR> } <BR> catch(_com_error e) <BR> { <BR> AfxMessageBox("不能连接数据库 error!"); <BR> return FALSE; <BR> } <BR> <BR> 3.Oracle 9i <BR> <BR> _ConnectionPtr m_pConn; <BR> CString m_sConn="Provider=MSDAORA.1;Data Source=sode_192.168.3.9"; //使用 <BR> ms连接库，sode为SID，192.168.3.9为机器ip <BR> m_pConn.CreateInstance("ADODB.Connection"); <BR> try <BR> { <BR> HRESULT hr=m_pConn->Open((_bstr_t)m_sConn,"sodeUser","sodePw",adConnectUnspecified); <BR> if (FAILED(hr)) <BR> { <BR> AfxMessageBox("不能连接数据库 source!"); <BR> return FALSE; <BR> } <BR> } <BR> catch(_com_error e) <BR> { <BR> AfxMessageBox("不能打开数据库 error!"); <BR> return FALSE; <BR> } <BR> 、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、<BR> m_pConnection->ConnectionString=_bstr_t(L"Provider=SQLOLEDB;Server=TZG;Database=tzgtest;Trusted_Connection=yes;uid=;pwd=;"); <BR> // hr=m_pConnection->Open(_bstr_t(L""), <BR> _bstr_t(L""),_bstr_t(L""),adModeUnknown);<BR>、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、<BR></DIV>
查看全文
发表于:2008-06-17 ┆
阅读(103)
┆
评论(0)
JAVA+ACCESS编程体会
<DIV>下午花了点时间，体会了下java&access的编程。实际上，是公司需要整合两个异质系统的数据。数据库一个采用ms的sql server，另一个是access。其实对于数据表的操作，免不了总是程序里面一个重要的步骤。之前，公司一直用sql server，数据库的访问操作都是用javabean进行封装好的，而且，大部分的公司实际上也都是这么做的。</DIV> <DIV>被过滤广告 就编程来讲，对于sql server，微软提供了专门的jdbc驱动程序，也就是大家平常用的那三个jar文件。但access的编程可没那么豪华，现在可用的编程方法，只是提供一个jdbc-odbc桥接器进行连接，效率就不用说了哦。<BR> <BR> 大概过程也略略罗嗦一下：<BR> 1，创建制定数据库的URL:同时配置access数据源<BR> 如： String url = "jdbc:odbc:Oblog";<BR> 2，加载驱动程序<BR> Class.forName("sun.jdbc.odbc.JdbcOdbcDriver");<BR> 3，创建连接<BR> Connection conn = DriverManager.getConnection(url, "user", "pwd");<BR> 4，创建sql语句对象<BR> Statement stmt = conn.createStatement();<BR> 5，执行sql语句<BR> stmt.execute(strSql.toString());</DIV> <DIV> 干脆贴个例子： </DIV> <DIV> </DIV> <DIV><BR> //Select.java</DIV> <DIV> import java.sql.*;</DIV> <DIV> class Select{<BR> public static void main(){<BR> try{<BR> String url = "jdbc:odbc:wombat";<BR> Connection conn = DriverManager.getConnection(url,"user","pwd");<BR> Statement stmt = conn.createStatement();<BR> ResultSet rs = stmt.executeQuery("SELECT * FROM Table1");<BR> System.out.println("Got ResultSet Now");<BR> rs.beforeFirst();<BR> while(rs.next()){<BR> System.out.println(rs.getString(1));<BR> }<BR> stmt.close();<BR> conn.close();<BR> }<BR> catch(Exception ex){<BR> ex.printStackTrace();<BR> }<BR> }<BR> } <BR></DIV>
查看全文
发表于:2008-06-17 ┆
阅读(110)
┆
评论(0)
