注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

fanhq666的博客

Fan-Fun

 
 
 

日志

 
 

BJOI2011Day1(10%)题目与成绩  

2011-02-12 19:40:05|  分类: 程序 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

2011年北京冬令营

第一试

竞赛时间:2011年2月12日上午8:00-13:00

题目名称

双端队列

最小三角形

神秘好人

目录

deque

triangle

bdcxq

可执行文件名

deque

triangle

bdcxq

输入文件名

deque.in

triangle.in

bdcxq.in

输出文件名

deque.out

triangle.out

bdcxq.out

每个测试点时限

1

10 

测试点数目

10

10

10

每个测试点分值

10

10

10

是否有部分分

题目类型

传统

传统

传统

提交源程序须加后缀

对于Pascal语言

deque.pas

triangle.pas

bdcxq.pas

对于C    语言

deque.c

triangle.c

bdcxq.c

对于C++  语言

deque.cpp

triangle.cpp

bdcxq.cpp

注意:最终测试时,所有编译命令均不打开任何优化开关

双端队列

【问题描述】

Sherry现在碰到了一个棘手的问题,有N个整数需要排序。

Sherry手头能用的工具就是若干个双端队列。

她需要依次处理这N个数,对于每个数,Sherry能做以下两件事:

1. 新建一个双端队列,并将当前数作为这个队列中的唯一的数;

2. 将当前数放入已有的队列的头之前或者尾之后。

对所有的数处理完成之后,Sherry将这些队列排序后就可以得到一个非降的序列。

【输入文件】

输入文件deque.in的第一行包含一个整数N,表示整数的个数。接下来的N每行包含一个整数Di,其中Di表示所需处理的整数

【输出文件】

输出文件为deque.out

其中只包含一行,为Sherry最少需要的双端队列数。

【输入样例】

6

3

6

0

9

6

3

【输出样例】

2

数据规模和约定

30%的数据中N5000

100%的数据中N200000

最小三角形

【问题描述】

Xaviera现在遇到了一个有趣的问题。

平面上有N个点,Xaviera想找出周长最小的三角形。

由于点非常多,分布也非常乱,所以Xaviera想请你来解决这个问题。

为了减小问题的难度,这里的三角形也包括共线的三点。

【输入文件】

输入文件triangle.in

第一行包含一个整数N表示点的个数。

接下来N行每行有两个整数,表示这个点的坐标。

【输出文件】

输出文件为triangle.out

输出只有一行,包含一个6位小数,为周长最短的三角形的周长(四舍五入)。

【输入样例】

4

1 1

2 3

3 3

3 4

【输出样例】

3.414214

数据规模和约定

30%的数据中N500

100%的数据中N200000

神秘好人

【问题描述】

有一个神秘好人跟Bdcxq玩一个游戏,如果Bdcxq成功完成了这个游戏,那么他将会得到一件礼物。

这个游戏是这样的:

有一个梯子形的图如下,每条边都有一个权值。

+-+-+-+-+-+ 

 |  |   |  |   |  |

+-+-+-+-+-+
神秘好人一开始会告诉Bdcxq每条边的权值。

然后神秘好人会做这样的事情:

1. 神秘好人会修改某条边的权值;

2. 神秘老人会问你从一个点走到另一个点所需经过边权和最小的权值和。

如果Bdcxq一直能答对问题,那么他就完成了游戏,也能得到礼物。

现在他请你编一个程序来帮他完成游戏。

【输入文件

输入文件名为bdcxq.in

输入文件的第一行包含一个整数N,表示梯子总共含有2N个点,第一行从左至右分别标号为13,……,2N-1第二行从左至右分别标号为24,……,2N

接下来有三行。

第一行有N-1个整数,依次表示上层相邻两点间的初始权值。

第二行有N个整数,依次表示两层之间的边的初始权值。

第三行有N-1个整数,依次表示下层相邻两点间的初始权值。

接下来一行包含一个整数M,表示神秘好人在游戏开始后的操作。

接下来M行:

每行第一个整数若是0,表示这是一个修改操作,接下来会有3个整数AiBiCiAi012分别代表这条边属于上层边,中间边和下层边,Bi表示这条边是这一层从左向右数的第Bi条边,Ci表示要修改成的边权。

每行第一个整数若是1,表示这是一个询问操作,接下来会有2个整数AiBi,询问AiBi的经过边的最小权值和。

【输出文件

输出文件名为bdcxq.out

对于每次询问操作你需要输出一行包含一个整数,为最小的边权值和。

【输入样例】

4

1 2 7

1 3 4 8

4 5 6

5

1 1 2

1 2 6

1 1 8

1 3 1

1 1 8

【输出样例】

1

8

13

10

【数据规模】

30%的数据满足NM 1000

100%的数据满足NM 100000



成绩呈典型的几何分布:


范浩强(我):300分==============================

SunBinTao:   140分==============

黄纪元:      110分===========

LiQiYang★:  90分 =========

王戈锐★:    70分 =======

HeXin:       60分 ======

30分的有:LuXiaoQiang、张放★★、WangZhiMo、ZhangeZiWei、SunTong、LuoJi、HuangRenPei

                   ===

                   ===

                   ===

                   ===

                   ===

                   ===

                   ===

20分的有:TanQingYang。

                   ==

10分的有:ZhuYueQi、何行舟★★、YangJiaQi、ChenRuiLin

                   =

                   =

                   =

剩下大约30人全部是0分。



























加一个五角星的是今年冒出来的新星。

加两个五角星的是……你知道的


说一下算法:

第一题:把原序列排序,之后贪心(能插入到队列中就插入,否则新建)或者dp(求最少局部极值点)。

第二题:分治,见算法导论最近点对。

第三题:经典线段树,见某年某题(6*N维护最短路的问题)。


  评论这张
 
阅读(1669)| 评论(5)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017