c++&oi
郑州集训Day2
巨惨,忘记考程序了,全部还原掉了!
试题
省选班训练试题(
2012.1
.
31
)
试题名称 逃出魔掌 商品大采购 黄金棋盘 手气不错
可执行文件名 Escape Shopping Game Luckylucky
输入文件名 Escape.
in
Shopping.
in
Game.
in
Luckylucky.
in
输出文件名 Escape.
out
Shopping.
out
Game.
out
Luckylucky.
out
每个测试点时限
0
.1s
0.1
~
2s
1
~
2s
0.5
~2s
测试点数目
10
10
10
10
每个测试点分值
10
10
10
10
内存限制 128MB 128MB 128MB 128MB
是否有部分分 无 无 无 无
题目类型 传统 传统 传统 传统
前言:小夜是个很漂亮又很呆的女孩子……此故事纯属虚构,如有雷同,纯属巧合。。。
逃出魔掌
【问题描述】
小夜家教很严……恩,家教很严厉。但俗话说得好“有些鸟是关不住的”。小夜家住一个很大很大的湖泊中央的小岛上,湖泊中有还有n个小岛,小岛间有桥相连。任意两个小岛之间都有至少一条路径可以到达。小夜很久没有出去玩了,她想到岸上去玩……但是去玩之前她要跟自己的爷爷奶奶叔叔伯伯阿姨婶婶大哥大姐小弟小妹打声招呼,所以她要跑遍湖中所有的岛至少一次(当然还有自己家)……orz……但是小夜有个很邪恶的爸爸,夜爸爸不准小夜出去玩。夜爸爸有足够的人手可以控制住连接岛屿的桥,在从线人那打听到小夜的情况后,夜爸爸决定在每一个时刻都增派一票人控制住某一座当前还未被他控制的桥,只要小夜路过这些桥就……
小夜在路上好几次都差点被逮到,她发现这是个问题,于是打开手机向你求助。因为被夜爸爸控制的桥会越来越多,她认为走的桥越少越好,所以她想知道当前时刻一共有多少种方案能够让选择n座桥并使得任意两个岛屿只有一条路径连通。
【输入格式】
输入文件第一行两个整数n和m,表示湖泊中除了小夜家以外的岛屿数目和夜爸爸会陆续派m票人控制桥。
接下来n
+
1行,每行n
+
1个整数,其中第i行第j个整数 Aij表示第i号岛屿和第j号岛屿之间是否直接有桥相连(0表示不连通,1表示连通)。
再接下来m行,每行两个整数a,b。表示当前时刻他已经控制住第a号岛屿和第b号岛屿直接相连的桥。(注:开始时刻夜爸爸没控制一座桥。)
【输出格式】
输出文件共有m
+
1行,每行一个整数。表示当前时刻的总方案数。
【输入样例】
5
2
0
1
1
1
1
1
1
0
1
1
1
1
1
1
0
1
1
1
1
1
1
0
1
1
1
1
1
1
0
1
4
1
1
3
【输入样例】
1296
864
540
【数据范围】
对于40
%
的数据
0
<
n
<
13
对于100
%
的数据
0
<
n
<
26
,
0
<
m
<
31
输出数据保证在extended范围内。
商品大采购
【问题描述】
终于逃出了夜爸爸的魔掌,小夜来到了一个巨大无比的超市。超市里琳琅满目的商品勾起了小夜的购买欲。。。
~
囧
~
。。。。 于是小夜推来n辆大型购物车••开始往里面塞东西!@#¥……塞了一车又一车……因为太呆了,小夜喜欢重复地买一些东西,而且每辆购物车里都会有n件物品。比如她在推第一辆车的时候会买熊宝宝、小saber、机器人……在推第2辆车的时候她还是会买熊宝宝、小saber、机器人,而且买这些东西的顺序一样,只是数目不同罢了……结帐的时候,售货员告诉她每辆购物车里的商品总价值x元,累加起来后小夜发现这是个天文数字。。。。她开始怀疑售货员有没有坑她。因为每辆车里商品太多,小夜不能直接看到商品的单价,她只知道第i辆购物车里第ai件商品的数目是多少。但她根本算不出那么多物品的单价,于是她想到了你……
任务:小夜给了你一张表,上面写着每辆车里各个商品的数目以及商品总价,请你帮小夜算出每件商品的单价是多少。
【输入格式】
输入文件中第一行有一个数字n代购物车数
接下来有n行,每行n
+
1个整数。前n个整数aij 代表第i辆辆购物车里第j件商品的数目,第n
+
1个整数xi 代表该辆购物车的总价值。
【输出格式】
输出文件一共有n行,每行一个整数,代表第i件物品vi的单价。
【输入样例】
2
1
1
3
1
2
5
【输出样例】
1
2
【数据范围】
对于20
%
的数据:
0
<
n
<=
10
对于100
%
的数据:
0
<
n
<=
500
0
<
vi
<
32767
0
<
xi
<
32767
0
<
aij
<
101
对于10
%
的数据限1s,对于另外20
%
的数据时限2s
黄金棋盘
【题目描述】
我们的小夜同学在超市刷了几百张卡以后发现身上仅存一张“X业银行”的储蓄卡。大小姐顿时发现自己即将过没有钱的日子……怎么办呢? 还好天无绝人之路,有个巫师来到了她身边,他自称身上有个盘古时期留下的宝物——黄金棋盘。这是个很神奇的东西,正面是个n
*
n的棋盘G,每个格子上都有一定数目的黄金,而且黄金可以再生
^
_
^
。巫师手上还有一些棋子,当一颗棋子放置在G(i,j)号位置时,棋盘上第i行和第j列的所有黄金都会被棋子吸走, 值得庆幸的是,每颗棋子在放下之后只会吸取一次黄金(不然由于黄金棋盘的再生性,棋子会不停地吸黄金……),并且放好后就不能移动了(但不影响这个位置的黄金再生)。 于是巫师打算跟小夜玩个游戏,游戏规则如下:
1
、巫师先在n
*
n的棋盘内放置m颗棋子。吸取的黄金数记为C。
2
、当棋子被放置在点G(i,j)上后,棋盘的第i行和第j列都不能放置棋子。
3
、在巫师布置完棋子后,小夜可以尽量多的在棋盘上放棋子,但要遵循规则2。
4
、小夜所有棋子吸取的黄金数记为V,当V
>
C时,小夜获胜,否则巫师获胜。
5
、游戏后败家支付赢家
|
C
-
V
|
数量黄金等价的money。
注意: 黄金与money之间比例为1:e
小夜听了后动心了,决定赌一把。为了能够必胜,小夜决定再次找到你,赢了的话事后五五分~。
任务: 在小夜告诉你棋盘布局以后,请你计算小夜是否能获胜。
【输入格式】
输入文件第一行为一个整数n,表示棋盘大小。
接下来是个n
*
n的矩阵,表示每个格子上的黄金数目gold(i , j)。
第n
+
1行是一个整数m,表示巫师放置的棋子数。
接下来m行每行两个整数a,b,表示巫师放置的棋子坐标。
最后一行为一个整数e,代表黄金与money之间的汇率
【输出格式】
如果能获胜,输出一个整数,即小夜将赢得多少money,
否则输出“Night can not win
!
”。
【输入样例】
3
1
2
1
2
1
3
1
3
1
1
2
2
1
【输出样例】
5
【数据范围】
对于30
%
的数据时限为2s
对于所有数据:
3
<=
n
<=
300
0
<=
m
<=
n
1
<=
e
<=
10000
0
<=
gold(i , j)
<=
32767
手气不错
【题目描述】
果然•••••••@#¥@#……
%
果然!!! 果然小夜被骗了。 现在我们可怜的小夜身上仅仅只有little money。 但此时她突然觉得上帝让她槑了这么久怎么说这次也会保佑下她,于是她决定去参加摇摇乐大抽奖活动……
摇摇乐大抽奖活动是一种类似于彩票的东西,人们每次可以花一些钱买一张摇摇卷。每张摇摇卷上面都有一个编码x。系统会不定期的抽奖,每次抽奖系统都会随机生成一个编码Xj,在之前的所有摇摇卷上选取一张编码小于Xj且与Xj相差最小的一张Xi作为中奖卷,获得的奖金
j
V
=
∑ Xk
k
=
i
为了保证游戏的公平,每次抽出的中奖券将被禁止参加以后的抽奖,并且以后奖金计算时不将此卷累加入奖金中。
小夜没什么钱了,但剩下的钱足够她参加一次摇摇乐活动。请你计算出在活动结束时,小夜可以获得多少奖金。
【输入格式】
输入文件第一行为一个整数n,表示游戏回合数
接下来n行每行两个整数a, x。
当a为0时,表示这回合是抽奖环节, x为系统产生的编码。
当a为1时,表示这回合是小夜买摇摇卷;当a为2时,表示这回合是路人甲乙丙丁XXX购买摇摇卷; x为摇摇卷上的编码。
【输出格式】
输出文件一个数字v,表示小夜获得的奖金数额。
【输入样例】
8
1
3
1
4
1
7
1
1
1
6
0
8
1
9
0
5
【输出样例】
47
【数据范围】
0
<
n
<=
5
*
10
^
5
0
<
x
<=
10
^
8
输入数据保证不出现重复编码
对于10
%
的数据时限2s
好在一边做一边测了。
第一题10
第二题AC
第三题才开始做
第四题还没看
考的是湖南的省选模拟题,难度较高。
分析一下,第一题是动态地求图的生成树的个数。要用矩阵法。我写的还是超时。【我写的矩阵比较垃圾】
第二题是高斯消元。我写的直译版竟然AC。记得AHOI07时,直译版还是过不了的。【要不然是数据弱了,要不然是我的程序实现能力提升了】
第三题是KM算法
第四题考数据结构(平衡树?线段树?)
总体看一下,四小时四题。
省选时可能你四题都会做。(给我100小时我可以写到至少310或400)
但是时间上还是很紧的。
第一题可能是最难的。要不然不会直接放弃。否则可能花1h+,才得10,不划算了【正如我,3h用掉1h+就直接完蛋了】。
第二题20min瞬间AC
第三题看穿就必须在40min内瞬间AC
第四题没有仔细看,但最后和第一题要权衡。估计至少要在拿到100才能进省队吧。
AH乱七八糟的题目和数据除外~
posted on 2012-01-31 22:06
zyn.cpp
阅读(146)
评论(0)
编辑
收藏
引用
只有注册用户
登录
后才能发表评论。
【推荐】100%开源!大型工业跨平台软件C++源码提供,建模,组态!
网站导航:
博客园
IT新闻
BlogJava
知识库
博问
管理
<
2012年1月
>
日
一
二
三
四
五
六
25
26
27
28
29
30
31
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
1
2
3
4
导航
C++博客
首页
新随笔
联系
聚合
管理
统计
随笔 - 57
文章 - 13
评论 - 11
引用 - 0
常用链接
我的随笔
我的评论
我参与的随笔
留言簿
给我留言
查看公开留言
查看私人留言
随笔档案
(57)
2012年6月 (2)
2012年5月 (4)
2012年4月 (18)
2012年3月 (7)
2012年2月 (14)
2012年1月 (3)
2011年12月 (8)
2011年11月 (1)
文章档案
(13)
2012年2月 (1)
2011年12月 (7)
2011年11月 (1)
2011年9月 (3)
2011年8月 (1)
搜索
最新评论
1. re: 培训作业-第三周(STL&USACO+4)
评论内容较长,点击标题查看
--佛教网
2. re: 培训作业-第三周(STL&USACO+4)
评论内容较长,点击标题查看
--happem
3. re: NOIP2011解题报告
sum[i]表示前i个点的单位数?这。。,sum[i]表示i点前下车的乘客数吧?
--锐
4. re: NOIP2011解题报告
顶一下。。
--锐
5. re: 培训作业-第三周(STL&USACO+4)
@zyn.cpp
用vector暴力平衡树啊。。。
--姚京韬
阅读排行榜
1. NOIP2011普及组的第三题:瑞士轮(2622)
2. NOI LINUX 安装记(1970)
3. 随便说说状态压缩(1528)
4. 迎接初中同学——整理OI知识点(building)(803)
5. POJ 1733 (551)
评论排行榜
1. 培训作业-第三周(STL&USACO+4)(5)
2. NOIP2011普及组的第三题:瑞士轮(2)
3. POJ 1733 (1)
4. 给count-base sort正身(0)
5. 奇怪的乘法运算(cm)(0)
Powered by:
C++博客
Copyright © zyn.cpp