寒假师徒分配

Published by:

师徒分配情况如下:

许磊: 电信 杨浩 计算机 茅佳峰
伍建霖:物联网 陈逸桐 自动化 叶松
林淮佳:自动化 余谦 中荷 徐王子浩 计算机 杨程皓
曹高飞:数字 张文池 中荷 杨亮
孟骋: 软件 张欣雨 软信 钱晓宇
朱玉琦:计算机 张裕浩 计算机 房礼靖
陶子恒:软日 李钊 软信 骆宁
王涵: 软件 罗益超 软信 吴朋
谢海滨:计算机 程国宇 计算机 岑榕
刘恒宇:计算机 孟李 计算机 李思特
陆凯: 软件 许鹏林 电信 李佳奇
范希航:软英 王珺昊 计算机 程立智

各位加油!希望假期有所收获!

2014 NEUACM 新星赛题解

Published by:

 

 

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

2014东北大学ACM程序设计新星赛通知

Published by:

一. 竞赛介绍

ACM国际大学生程序设计竞赛(英文全称:ACM International Collegiate ProgrammingContest(ACM-ICPC或ICPC)是由美国计算机协会(ACM)主办的,一项旨在展示大学生创新能力、团队精神和在压力下编写程序、分析和解决问题能力的年度竞赛。经过近30多年的发展,ACM国际大学生程序设计竞赛已经发展成为最具影响力的大学生计算机竞赛。

我校自从参与该赛事以来,成绩逐年提升,我校队员多次参加ACM-ICPC亚洲区域赛,取得佳绩,这些队员在ACM竞赛的学习过程中,程序设计能力取得了极大的提高,个人职业发展也取得了良好的开端,大部分队员已经就职于Baidu、阿里巴巴等著名企业。

东北大学ACM程序设计新星赛旨在激发我校大学生程序设计学习的兴趣,加强学风建设,增进我校学生在计算机程序设计、数据结构、算法设计等学科的学习,比赛每年举办一次,吸引全校数百名程序爱好者参加,为广大程序设计爱好者搭建了一个学习、交流、竞技的平台。

 

二.  组织单位

主办:东北大学学生创新中心

承办:东北大学校ACM竞赛集训队

 

三. 比赛规则

1.本次比赛以个人的形式参赛;

2.竞赛中6题左右,试题描述为英文,比赛时间为2个半小时;

3.竞赛可以使用的语言:C++、C、Java;

4.重点考察选手的算法和程序设计能力,不考察任何Windows编程知识;

5.选手可携带任何非电子类资料,包括书籍和打印出来的程序等;

6.评委负责将结果(正确或出错的类型)通过网络尽快返回给选手,除此之外不提供任何额外帮助;

返回结果:

1.Accepted. —通过!(AC)

2.Wrong Anwser. —答案错。(WA)

3.RunTime Error. —程序运行出错,意外终止等。(RTE)

4.Time Limit Exceeded. —超时。程序没在规定时间内出答案。(TLE)

5.Presentation Error. —格式错。程序没按规定的格式输出答案。(PE)

6.Memory Limit Exceeded. —超内存。程序没在规定空间内出答案。(MLE)

7.Compile Error. —编译错。程序编译不过。(CE)

 

四.竞赛安排

即日起至12日25日 中午12点:参赛选手自行在报名网站上注册比赛账号(参见注册与参赛方式);

2014年12月25日 18:30-21:00 在东北大学计算中心微机6室进行比赛在东北大学online judge(acm.neu.edu.cn/hustoj)上进行;

 

四.注册与参赛方式

参赛选手需登录219.216.96.47进行注册报名,填写个人真实信息。比赛将现场分发账号,使用其他账号的选手将不计入排名,选手需凭此账号密码参加现场比赛

本次比赛由参加过亚洲区域赛东北大学2014年ACM集训队队员作为命题组,将不参与比赛。非东大2014ACM集训队的东大在校学生均可报名参赛,并且届时会有其他学校的同学友情参与同场竞技。

 

五.奖励方案

大赛设冠、亚、季军、一等奖(包含冠亚季军),二等奖,三等奖,并授予校级荣誉。所有获奖选手将颁发东北大学学生创新中心的证书及东北大学校ACM竞赛集训队的奖品。