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

fanhq666的博客

Fan-Fun

 
 
 

日志

 
 

20090723做的题  

2009-07-23 20:36:53|  分类: 程序 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
NOI热身赛试题
2009.7.19
共三题, 每题满分100分, 满分300分.
邪恶的大叔水闸植树
push gates tree
输入文件push.in gates.in tree0.in - tree9.in
输出文件push.out gates.out tree0.out - tree9.out
题目类型传统传统提交答案
时间限制3s 3s -
1
1 邪恶的大叔
push (.c/.cpp/.pas)
题目描述
一个邪恶的大叔进入了这个神秘的空间, 他发现这里有很多很多的Loli在这里, 这个邪恶的大叔想把她们
全部推倒! 但是推倒Loli要耗费的体力太大了, 所以他想用尽量少的次数把她们全部推倒.
所有的Loli可以抽象成站在一个一维的坐标系内, 第i 个Loli所在的位置为Xi, 她的身高为Hi. 大叔可以推倒
任意个Loli让她们向左或者向右倒下去, 第i个Loli倒下去之后可能会连带着别的Loli一起倒下去(向左倒就是
在她左边并且满足jXi Xjj  Hi的所有Loli也会一起向左倒, 向右同样计算).
你的任务是帮助大叔计算出最少推倒多少个Loli可以让所有的Loli全部倒下.
输入格式
第一行一个整数N, 表示Loli的个数.
以下N行每行两个整数Xi; Hi,分别表示第i 1个Loli的位置和她的身高. 输入保证Xi严格递增.
输出格式
输出一行一个整数, 表示大叔最少推倒的次数.
样例输入
6
1 1
2 2
3 1
5 1
6 1
8 3
样例输出
2
样例解释
向右推倒第1个Loli可以让第2, 3个Loli一起倒下. 向左推倒第6个Loli可以让第5, 6个Loli一起倒下.
数据规模和约定
 对于30% 的数据, 满足N  10
 对于50% 的数据, 满足N  1000
 对于100% 的数据, 满足N  100000; Hi  108; Xi  231.
2
2 水闸
gates (.c/.cpp/.pas)
题目描述
由于厌倦了你的工作, 你从IT行业跳槽到了一家水产养殖公司.
你的第一项任务是把两个水槽分隔开. 尝试了操作手册的内容并仔细观察之后, 你了解了水槽的工作机制.
两个水槽由n条通道相连, 每个通道上有两个水闸. 只有两个水闸都打开时通道才开启, 其余情况下通道都
是封闭的.
这2n个水闸的状态由开关控制. 每个水闸的状态恰好由一个开关控制, 当然某个开关可能控制多个水闸或
者不控制任何水闸. 一条通道上的两个水闸也有可能由同一个开关控制.
开关一共有m个, 编号为1; 2; : : : ;m, 每个开关有两种状态: 开和关. 而水闸受开关控制的方式有两种:
 开关开时水闸打开, 开关关时水闸关闭.
 开关关时水闸打开, 开关开时水闸关闭.
输入格式
输入的第一行包含两个整数n和m.
接下来n行每行包含了一条通道的信息, 由四个整数a; S a; b; S b表示. a和b表示控制两个水闸的开关编号,
而S a和S b为0或1, 表示水闸受开关控制的方式. S i = 0表示开关i关时水闸关, 以此类推.
输出格式
如果存在一种开关的状态使得所有通道都封闭, 则输出m行, 每行一个整数0或1. 第i行为0表示编号为i的开
关应当关, 为1则表示开关应当开.
如果不存在这样的状态, 输出一行“IMPOSSIBLE”.
样例输入1
3 2
1 0 2 1
1 0 2 0
1 1 2 1
样例输出1
0
1
3
样例输入2
2 1
1 0 1 0
1 1 1 1
样例输出2
IMPOSSIBLE
数据规模和约定
 对40%的数据, n  20;m  40.
 对所有数据, n  250000;m  500000.
4
3 植树
tree
题目描述
一年一度的YL植树节到了, 每到这一天, 同学们都要在一块空地上植树. 但是由于事先没有统一的安排,
而是同学随意在自己喜欢的地方种下树苗, 这导致美观性大打折扣. 为了改变这一状况, YL City请来了著名
的Professor William来安排大家植树的位置.
首先, 为了避免很多棵树都种在一起, William将空地划分成了N  N个区域, 规定每个区域内最多只能种一
棵树. 其次, 由于地形原因, 某些区域内不能种树. 为了方便计算, William建立了直角坐标系, 这样每个区域都
能用一个数对(x; y)来表示(1  x  N; 1  y  N). 经过了数夜的研究, William发现当存在三棵树三点共线,即三
颗分别种在(x1; y1); (x2; y2); (x3; y3)的树满足(x2 x1)(y3 y1) = (x3 x1)(y2 y1)时, 美观度就会大大的降低, 因
此他规定方案中不允许出现三颗三点共线的树. 在如此苛刻的条件下, 树的数量也就被相应的限制了. 现在同
学们想要知道最多能够种多少棵树, 当然, William是很忙的, 这个任务就交给你了.
输入格式
输入的第一行是一个整数N.
接下来一行是一个整数k, 表示不能种树的区域个数. 接下来k行每行有两个整数, 表示不能植树的区域坐
标.
输出格式
第一行一个整数s, 表示树的棵数. 接下来s行, 每行两个数, 表示树的种植位置.
样例输入
2
1
1 1
样例输出
3
1 2
2 1
2 2
评分方法
每个数据单独评分.
对于每一个测试点,如果你的输出不合法,如文件格式错误, 解不合法时,该测试点得0分. 否则, 设你的输出
的树的棵数为your ans, 所有选手(包括样例程序)输出的数的棵数为best ans,弱样例程序输出的数的棵数为d.
如果your ans  best ans, 得10分;
如果your ans  d, 得1 + l9  your ansd
best ansd m分;
如果your ans < d, 得1分.


今天是第一次使用Linux....疯狂的怀念红绿蓝黄的windows图标

首先是GUIDE与Anjuta,几乎是垃圾,一个不能保存,一个不能编译运行。
只好使用g++与文本编辑器。
结果...第一题由于gpedit的字体过于垃圾,竟然拼错了一个函数名却没有发觉......
只得到了50分
这个教训告诉我:坚决使用Ctrl+F来静态盘错,对于多个类似函数/数组,坚决使用面向对象技术。

第二题,一个不同的2set问题,结果...因为数组开的不够恨竟然tle了。
第三题,提交答案,没怎么搞,得了22分......

  评论这张
 
阅读(708)| 评论(2)
推荐 转载

历史上的今天

评论

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

页脚

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