资讯首页 热点资讯初中高中竞赛自招

文库 > 热点资讯 > 正文

2019年海淀区青少年程序设计挑战活动复赛初中组试题

3553 0 0 2019-04-28 16:29:46

2019年海淀区青少年程序设计挑战活动复赛 初中组C++语言试题


竞赛时间:2019 年 4 月 27 日 13:30~16:30 


注意事项: 

1. 答题统一在windows系统下使用DEVC++5.11版本编程环境。 

2. 在计算机D盘根目录下创建一个以BJHDC和自己考号为文件名的文件夹。

如:D:\ BJHDC0001。 

2. 各题最后写好的源文件,按照题目规定的文件名存入上述文件夹中。 

3. 完成作答后,提交自己创建的整个文件夹,该文件夹仅仅包含各题的源

文件,不能包含子文件夹,或其它任何文件。  

4. 共有4道题目,每题100分。 

切记:答案严格按照题目要求命名。有疑问及时举手询问监考老师。 

 

试题 


试题1:杯子 (glass) 

源代码:glass.cpp 

输入文件:glass.in 

输出文件:glass.out 

时间限制:1s 

空间限制:256MB 

【题目描述】 

小明买了N个容积可以是无穷大的杯子,刚开始的时候每个杯子里有1升水,

接着小明发现杯子实在太多了,于是他决定保留不超过K个杯子。每次他选择两

个当前含水量相等的杯子,把一个杯子的水全部倒进另一个里,然后把空瓶丢弃。

(不能丢弃有水的杯子)  

显然在有些情况下小明无法达到他的目标,比如N=3,K=1。此时小明会重

新买一些新的杯子(新杯子容积无限,开始时有1升水),以达到目标。  

现在小明想知道,最少需要买多少个新杯子才能达到目标呢?  

【输入说明】  

一行两个正整数,N,K(1≤N≤1000000000,K≤1000)。 

【输出说明】  

一个非负整数,表示最少需要买多少新杯子。 

【样例输入1】 

3 1 

【样例输出1】 

【样例输入2】 

13 2 

【样例输出2】 

【样例输入3】  

1000000 5 

【样例输出3】  

15808 

【数据范围】  

对于50%的数据,N≤10000000;  

对于100%的数据如题目。 

 

 

试题2:玩具(toy) 

源代码:toy.cpp 

输入文件:toy.in 

输出文件:toy.out 

时间限制:1s 

空间限制:256MB 

【题目描述】 

商店正在出售小C最喜欢的系列玩具,在接下来的n周中,每周会出售其中

的一款,同一款玩具不会重复出现。 

由于是小C最喜欢的系列,他希望尽可能多地购买这些玩具,但是同一款玩

具小C只会购买一个。同时,小C的预算只有m元,因此他无法将每一款都纳入

囊中。此外,小C不能连续两周都购买玩具,否则他会陷入愧疚。现在小C想知

道,他最多可以买多少款不同的玩具呢? 

【输入说明】 

输入文件共2行; 

第一行两个正整数n和m,中间用一个空格隔开; 

第二行共n个正整数,第i个正整数表示第i周出售的玩具的价格。 

【输出说明】 

输出文件只有一行,包含一个整数,表示小C最多能买多少款不同的玩具。

 

【样例输入】  

3 8 

4 4 5 

【样例输出】  

【数据范围】 

对于30%的数据,n≤10; 

对于60%的数据,n≤100,m≤1000; 

对于100%的数据,n≤1000,m≤1000000,单个玩具的价格≤1000。 

 

 

试题3:恐怖的奴隶主(bob) 

源代码:bob.cpp 

输入文件:bob.in 

输出文件:bob.out 

时间限制:1s 

空间限制:512MB 

【题目描述】 

小L热衷于undercards. 

在undercards中,有四个格子。每个格子要么是空的,要么住着一只BigBob。

 

每个BigBob有一个不超过k的血量;血量减到0视为死亡。那个格子随即空

出。 

当一只BigBob受到伤害后,假如它没有死亡且剩余血量为t,它会从左数第

一个空格处召唤一只血量为a[t]的BigBob;若没有空格,则不会召唤。 

法术R定义为:从左往右,对每个BigBob造成一点伤害;假如有BigBob死

亡,重复上述效果。 

聪明的小L发现,在某些情况下,当他发动法术R时,游戏会陷入循环。 

他想求出这样的初始情形有多少种。 

【输入输出说明】 

输入一个正整数k; 

随后一行k-1个正整数,表示a[1]~a[k-1]; 

输出一个整数,表示答案。 

【样例输入】 

【样例输入】 

31 

【样例解释】 

Bigbob最多有2血,满血bigbob受伤会召出新的。 

循环的初始状态有: 

(2,1,0,0),(1,2,0,0),(2,0,1,0),(2,1,1,0),(0,2,1,0),(1,2,1,0),(2,2,1,0) ,(1,0,2,0),(

0,1,2,0),(1,1,2,0),(2,1,2,0),(2,1,0,1),(0,2,0,1),(1,2,0,1),(0,2,1,1),(1,2,1,1),(0,0,2,

1),(1,0,2,1),(0,1,2,1),(1,1,2,1),(2,1,2,1),(0,2,2,1),(1,2,2,1),(2,1,0,2) ,(1,2,0,2),(2,

0,1,2),(2,1,1,2),(0,2,1,2),(1,2,1,2),(2,2,1,2),(2,1,2,2) 

共31种。 

【数据范围】 

对于30%的数据,k≤5; 

对于70%的数据,k≤10, a[i]=k; 

对于100%的数据,k≤15, 1≤a[i]≤k。 

 

 

试题4:组合树(tree) 

输入文件:tree.in 

输出文件:tree.out 

时间限制:4s 

空间限制:512MB 

【题目描述】 

Bob想要和Carrol玩游戏。但Carrol觉得玩游戏太无聊,就和Tuesday去写

歌了。于是现在Bob来找你玩游戏。 

这个游戏是这样的:给定一棵n个节点的树, 1号点为根节点,设v的父亲

是f(v) 。其中每个节点有一个颜色,要么是黑色,要么是白色。不妨记第i个节

点的初始颜色是ci。ci =0或1,表示黑色或白色。 

在游戏开始时,Bob为每个节点选择一个目标颜色di,要求你经过若干次操

作,将每个节点变成其目标颜色。你的操作是这样的: 

●选定一个点u,将u,f(u),f(f(u)),…,fk-1 (u)这k个节点的颜色翻转(将白色节

点变为黑色节点,将黑色节点变为白色节点)。其中k是游戏开始前确定的一个

正整数。 

只有u,f(u),f(f(u)),…,fk-1 (u)这k个节点均存在,你才能执行这样的操作。当

然,你可以执行任意多次操作。 

现在Bob要和你玩T次这样的游戏,每次你都想要知道你是否有可能完成要

求,即通过若干次操作,将所有节点变成其目标颜色。 

【输入说明】 

●第一行仅一个数T≤10,表示这样的游戏的次数; 

●接下来共有T组数据。对于每一组数据: 

○第一行是两个正整数n,k,n表示树的大小,k的含义请参见题目描述。

数据满足n,k≤2×105 

○接下来n-1行每行两个数u,v,表示树上有一条边(u,v) 。注意:输入

并不保证边的方向。 

○接下来一行n个数c1 , c2,…,cn,表示初始颜色。 

○接下来一行n个数d1 , d2,…,dn,表示目标颜色。 

【输出说明】 

输出包含T行,第i行对应第i次游戏的答案; 

对于第i次游戏,如果你有可能完成任务,输出Yes,否则输出No 。 

【样例输入】 

2 3 2 1 2 2 3 

0 0 0 1 0 1 3 2 1 2 2 3 0 0 0 1 1 1 【样例输出】 

Yes 

No 

【样例解释】 

●在第一个例子中,第一次选择2号点操作,1,2号点被翻转;第二次选择3

号点操作,2,3号点被翻转。即达成目标状态。 

●可以证明,无法将初始状态经过操作变为目标状态。 

【数据范围】 

对于全部测试点:T≤10, k≤n≤2×105,保证数据给出的是一棵树。 

对于前 10% 的数据,n≤5; 

对于前 30% 的数据,n≤20; 

对于前 50% 的数据,n≤2000; 

对于前 70% 的数据,n≤50000; 

对于全部数据,n≤2×105 


我要评论 0条评论

0/300

自律公约

网友评论

来第一个评论吧