加载中…
个人资料
徐于铃
徐于铃
  • 博客等级:
  • 博客积分:0
  • 博客访问:43,408
  • 关注人气:31
  • 获赠金笔:0支
  • 赠出金笔:0支
  • 荣誉徽章:
相关博文
推荐博文
谁看过这篇博文
加载中…
正文 字体大小:

复盘|2019年海淀区程序设计挑战活动小学组试题解析

(2019-05-18 15:48:15)

2019年海淀区程序设计挑战赛 复赛上机试题小学组


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

概要:

据说这次比赛 约700人参加初赛,约298人进入复赛(上机操作),本次考试不难,主要考语法和小思路,org.

试题一:约数

题目大意:给定一个正整数n,求n除了自身以外最大约数。

思路:

30分:注意到n≤100,可以用100个if判断一下,手算出来所有结果(呵呵呵

60分:i从1到n-1枚举,如果n mod i ==0 ,答案和i取max       时间复杂度O(n)

100分:

注意到如果i是n的约数,那么n/i也是n的约数。如果i从小到大枚举,n/i必然是从大到小的。我们就可以使i从1到根号n枚举,如果n mod i==0,ans=max{i,n/i,ans}  (这里n/i不为n)。

复杂度O(sqrt(n))

注意:for(int i=1;i<=sqrt(n);i++)这样写复杂度有问题(上课讲过)

应该

int t=sqrt(n);

for(int i=1;i<=t;i++)



试题二:阶乘

没有部分分

首先看单阶乘

结论:一个数 n 的阶乘末尾有多少个 0,取决于从 1 到 n 的各个数的因子中 2 和 5 的个数,,而 2 的个数是远远多余 5 的个数的。 因此取决于5的个数。现在问题的关键是如何求解因子5的个数。

思路一:记录每个数的因子5的个数然后相加,但是这样很可能会超时。

思路二:用 n 不断除以 5, 直到结果为 0, 然后把中间得到的结果累加。

理由:不断除以 5, 是因为每间隔 5 个数有一个数可以被 5 整除, 然后在这些可被 5 整除的数中, 每间隔 5 个数又有一个可以被 25 整除, 故要再除一次, ... 直到结果为 0, 表示没有能继续被 5 整除的数了。


其实慧明的在线题库也有类似的题:oj.huimingedu.com


双阶乘:

如果n为奇数,则答案为0(没有2的因子)

如果n为偶数,和之前做法类似。


试题三:序列

思路:

50分:按照题目模拟,翻转序列b即暴力翻转。

100分:

用双端队列模拟,首先定义正方向为从前向后,将ai加到序列b的尾部即在双端队列尾部加入ai,将序列翻转即把正方向改变成从后向前,再将ai加到序列b的尾部即在双端队列的队头加入ai,以此类推。

双端队列可以手写数组或者用stl的deque实现(老师上课讲过)


也可以用链表模拟,c++的list有swap功能,自己手写链表也可以(上课讲过)


试题四:糖果

思路:

50分做法:

从小到大枚举l,再从前向后枚举区间,暴力check一下区间内有没有相同分类的糖果。时间复杂度O(n^2*26)

关于时间复杂度为什么不是O(n^3):我们注意到糖果种类数最多为26,求的是任意l个糖果不会有相同的分类,所以l最大为26。

70分做法:

从小到大枚举l,再从前向后枚举区间,可以对每种糖果的数量做一个前缀和,再用前缀和减一下来判断区间内有没有相同分类的糖果。

时间复杂度O(n*26*26)

可以做到O(n*26)

100分做法:

我们可以统计这样一个东西:对于每个位置pos,记录第i种糖果上次出现的位置为f[i][pos],答案就是min{ans,pos-f[i][pos]+1}。

问题转化为如何计算f[i][pos],如果当前u位置的糖果为i,则f[i][pos]=i,否则f[i][pos]=f[i-1][pos]

时间复杂度O(n)


试题五:迷宫

BFS裸题,走迷宫问题,我和孙老师都讲过类似的题


试题六:盒子

思路:

20分做法:

搜索或枚举(可能会被写得好的贪心水过去)


50分或100分做法:

求lis(最长上升子序列)。

(优化到O(nlogn)就可以拿满分了

近乎原题:noip1999导弹拦截的第二问



Dilworth定理:对于一个偏序集,最少链划分等于最长反链长度。

Dilworth定理的对偶定理:对于一个偏序集,其最少反链划分数等于其最长链的长度。

也就是说把一个数列划分成最少的最长不升子序列的数目就等于这个数列的最长上升子序列的长度。


下面来说说这个定理是怎么来的:

偏序集的定义:偏序是在集合X上的二元关系≤(这只是个抽象符号,不是“小于或等于”,它满足自反性、反对称性和传递性)。即对于X中的任意元素a,b和c,有:

(1)自反性:a≤a;

(2)反对称性:如果a≤b且b≤a,则有a=b;

(3)传递性:如果a≤b且b≤c,则a≤c 。

带有偏序关系的集合称为偏序集。


令(X,≤)是一个偏序集,对于集合中的两个元素a、b,如果有a≤b或者b≤a,则称a和b是可比的,否则a和b不可比。

一个反链A是X的一个子集,它的任意两个元素都不能进行比较。

一个链C是X的一个子集,它的任意两个元素都可比。


【定理】

在X中,对于元素a,如果任意元素b,都有a≤b,则称a为极小元。

定理1:令(X,≤)是一个有限偏序集,并令r是其最大链的大小。则X可以被划分成r个但不能再少的反链。

其对偶定理称为Dilworth定理

令(X,≤)是一个有限偏序集,并令m是反链的最大的大小。则X可以被划分成m个但不能再少的链。

虽然这两个定理内容相似,但第一个定理证明要简单一些。此处就只证明定理1。


证明:设p为最少反链个数

(1)先证明X不能划分成小于r个反链。由于r是最大链C的大小,C中任两个元素都可比,因此C中任两个元素都不能属于同一反链。所以p>=r。

(2)设X1=X,A1是X1中的极小元的集合。从X1中删除A1得到X2。注意到对于X2中任意元素a2,必存在X1中的元素a1,使得a1<=a2。令A2是X2中极小元的集合,从X2中删除A2得到X3……,最终会有一个Xk非空而Xk+1为空。于是A1,A2,…,Ak就是X的反链的划分,同时存在链a1<=a2<=…<=ak,其中ai在Ai内。由于r是最长链大小,因此r>=k。由于X被划分成了k个反链,因此r>=k>=p。

(3)因此r=p,定理1得证。

【解决】

要求最少的覆盖,按照Dilworth定理

最少链划分 = 最长反链长度


求lis可以用树状数组或二分优化到O(nlogn)


以上解析来自北京慧明教育科技发展有限公司 ,转载请联系下方电话


慧明科技信息学咨询报名请填写

https://www.wjx.top/jq/36765962.aspx


恭喜慧明科技学员在NOIP2018复赛中表现突出!(附北京地区获奖名单)

信息学课程大纲(2019)


学信息编程 到慧明科技

010-57110625

010-57112553

地址:北三环西路48号科技会展中心3号楼2C

官网:www.huimingedu.com      


0

阅读 评论 收藏 转载 喜欢 打印举报/Report
  • 评论加载中,请稍候...
发评论

    发评论

    以上网友发言只代表其个人观点,不代表新浪网的观点或立场。

      

    新浪BLOG意见反馈留言板 电话:4000520066 提示音后按1键(按当地市话标准计费) 欢迎批评指正

    新浪简介 | About Sina | 广告服务 | 联系我们 | 招聘信息 | 网站律师 | SINA English | 会员注册 | 产品答疑

    新浪公司 版权所有