A: Sister Wang

题意:给出一个字符串,要求把其中的数字挑出来并且按升序排序后输出。

解法:直接做就行了,一开始大家都没有看到排序就输出了,出题人才特地把排序的标红了,读题很重要哩~

图片1

PS:里面有C++ stl的用法,希望大家早日学会stl。。性价比高高地~

 

B: Christmas math gift

题意:给a*x^2+b*x+c=0中的a,b,c,求输出这个方程是多解,单解,还是无解

解法:如果a!=0,直接按b*b-4*a*c判断就可以了。如果a=0,那么再看b,如果b!=0,那么一个解,如果b=0再看c,如果c!=0,没有解,c=0,无穷多解。

Trick:因为a,b,c<=10^9,所以b*b-4*a*c可能会爆int,得用long long。

图片2

PS:好像老师上课让大家做过类似的题,大家应该有过思考才对。

 

C: Fushuai see movie

题意:给出一个环,在里面找出最长的连续的单调上升的子序列

解法:把序列复制一遍放在后面,这样环就变成了链,然后就变成了在一个链里找最长的连续上升序列,递推就可以了,f[i]代表以i为结尾的最长连续上升序列的长度。

图片3

PS:由于n<=10^5,所以暴力的做法,肯定不能过~

正解的时间复杂度是O(N)

 

D: Jiajia buys apple

题意:给出n个苹果和m次称量的结果,每次每边称k个苹果,总是左边比右边重,然后magic苹果要么比evil苹果重要么比evil苹果轻,然后问你能找出唯一的那个magic苹果(知道是重还是轻),那么就输出是哪个和重还是轻,否则(判断不了哪个)就输出“Jiajia is sad”

首先先抱歉一下,题意有歧义没说明白,因为原来的那套题队长说不适合新生做,然后就拿掉两道,然后我就再补上这题,由于比较匆忙,所以脑子不清醒再加上小伙伴们忘记帮我验这题所以导致这题成为这次比赛的一个瑕疵。。

思路:其实就是枚举每个苹果是不是magic,是重还是轻,然后如果结果唯一就输出,否则就无解

很抱歉,脑子当时不清醒,然后程序写的思路和出题的思路已经完全不一样了,比赛的时候发现了这个问题,然后我就去过了E和F,希望把榜带好,坑了那么多做D的同学实在很抱歉,赛后想改数据重新发现已经很麻烦,这次就只能这样了,下次我一定会注意,不会再让这种事情发生。。

 

 

 

E: Bored Qishen

题意:在1到n里的n个数里面,挑出若干数组成一个集合,要求这个集合里每两个数的乘积都不是完全平方数,问这样的集合的大小最大是多少。

解法:两种做法,标称的解法是把那些质因数分解后含的质数都是一次的数挑出来。。然后比赛的时候,发现过的同学的另一种做法,是把平方数和平方数的倍数都去掉,然后剩下的统计进去。。具体为什么这样的是对的大家仔细想想就知道了~

标程的做法,用到了筛素数表:

图片4

另一种做法,比标称简单了很多

图片5

 

 

F: Hengheng eat noodles

题意:给出n个面条,随机将2*n个端点两两连接在一起,问期望得到几个面条圈。

解法:利用期望的线性性质,令d[i]为前i跟面条能组成的线圈的期望数,假设d[i-1]已经求出来呢,那么对于第i根面条,对于其一端来说,另一端和前i-1根面条一共有2*(i-1)+1=2*i-1种选择。。那么有两种可能,要么和另一端相连组成一个圈,这是的概率是1/(2*i-1),新组成了一个圈;另一种是和前面的面条的端点相连,这时没有形成新的圈,概率是(2*i-2)/(2*i-1),所以标称如下:

图片6

然后化简后可以得到d[n]=sigma(1/(2*i-1))(1<=i<=n),然后有的同学很聪明,打表就找出规律了,然后就过了~

 

G: Annoying 01 string

题意:给你一个01串(长度小于等于10^5),求长度在l和r之间(包括l,r且l>0)且其中1所占的比例大于等于%p(p<=100)的子串

的个数

思路:好伤心呀。。比赛的时候没有人开这题。。用前缀和表示前i个字符里1的个数,那么那个条件可以表示为(s[j]-s[i-1])/(j-i+1)>=p,然后可以化成

100*s[i]-p*i>=100*s[j]-p*j,然后发现方程两边都只是和i,j相关的的了,然后就可以按照新得出的100*s[i]-p*i对数组重新排序(这个值大的在前面),这样只要前面的后面的随便组就行。.注意到其实还有一个长度的要求,这样就转化成了经典树状数组统计的模型,时间复杂度是O(N*logN)

图片7

其中,add()和sum()函数是树状数组的功能

 

 

后记:

第一次出比赛还是蛮用心的(可惜出了D的纰漏,so sorry),看到除了有问题的D和最后一题G,其它题大家都有人过(虽然过F的是大二的。。),还是蛮开心的,大家玩得开心还是最重要嘛~

然后希望学弟学妹们好好努力,看到和外校的差距,寒假多多刷题,下学期的省赛就看了你们的发挥了呀~

最后,参加了比赛,然后还没有加群的同学记得加这个群(校内群):31164134,大家记得互相转告一下。

 

 

 

NEU-佳佳

2014-12-25


发表评论

电子邮件地址不会被公开。 必填项已用*标注