Category Archives: 培训通知

2015年NEUACM二月月赛题解

Published by:

最终的board:http://acm.neu.edu.cn/hustoj/contestrank.php?cid=1049

首先恭喜高思坦同学拿到了winner,其他同学要好好努力了呀~

感觉这次题目的类型还是挺全的,有各路大神来参与,出题人表示蛮开心的= =,虽然中间C题的数据有点波折,但感谢mathlover同学帮忙验证了题目数据。

标称挂在http://www.cnblogs.com/acvc/category/661566.html,以后这个就作为NEU月赛挂代码的地方吧。

 

A.简单的模拟题,分别判断同一行,同一列,对角线和反对角线四种情况就可以了。

 

B.题意:给出2n个value,要求分成两组每组n个,要求分成的这两组满足差值最小。

solution :

可能有很多人搞过一个uva上的题目那个题目没要求均分,所以直接一个裸背包就好了,但是这题要求均分,同样的可以使用背包,但是要多增加一个状态表示到目前为止分给第一组的个数,所以有 :

dp[i][j][k]=max(dp[i][j][k],max(dp[i-1][j-1][k-v[i]]+v[i],dp[i-1][j][k]));

表示都目前为止枚举到第i个value,给第一组分了j个,所用的体积为k的最优状态。

考虑内存所以要用到滚动数组,需要注意枚举的顺序。枚举的时候注意优化否则会tle.

 

C.基础的几何题,在纸上画几下就能发现规律。

(训练指南后面有n个圆的,这题简化了,只有一个圆)

在两点间连线,如果不被圆阻挡,那么走直线就行了。如果被圆阻挡了,就两个点做对圆的切线,则距离等于切线长加上中间一段圆弧的距离。

需要注意的是两点都在圆内的情况,这时也是走直线。

PS:这题好波折,中间发现标称有问题,然后改了一下,后来发现有两组数据没法手算删掉了,后来经人提醒用几何画板验证是对的就又加上了= =

 

D.改编的汉诺塔= =考了递归和矩阵快速幂。

设A[n]为从n个圆盘移动到相邻柱子的最小次数,B[n]为n个圆盘移动到下下个柱子的最小次数。则可以找到递推式A[n]=2*B[n-1]+1,B[n]=A[n-1]+2*B[n-1]+1.

由于n最大可以到10^9,所以需要用矩阵快速幂,构造矩阵

图片2

这样就行了=。=

 

E.基本的图论问题。解法是利用欧拉回路的知识+并查集。

如果只有一个连通分量,那么答案就是奇数度的点的个数/2,因为每两个奇数点连线就可以了。而且一个连通分量里奇数度的点一定只有偶数个。

如果有多个连通分量,就答案分成两个部分,在每个连通分量里,如果奇数度的点的个数超过2个,那么这部分添加边数是(奇数度的点的个数-2)/2,然后将所有连通分量练成一个圈(剩余两个奇数度的点的连这两个奇数点,如果没剩奇数点就随便连两个点就行了)

其实在纸上画画就发现结论了。。

Trick的地方就是如果一个连通分量内只有一个点,那么就不需要经过,因为我们要经过的是边。

 

F.

题意:给出n个数字,要求分成两组,其中一组要求每个数互素,求两组差值的最小值。

solution :

由于n小于100 既然要求互素当然就要考虑素因子,100内的素因子的数量小于27个,数据量还是很大。但是小于50的素因子只有15个,因为大于50的因子不会重复出现所以不用考虑,对于15这么小的数据量显然要用状态压缩。

dp[i+1][state|v[i+1]]=max(dp[i][state]+1,dp[i+1][state|v[i+1]]) 表示当前选到第i+1个数字,素因子选择的状态为state|v[i+1] ,转移显而易见,就是从上一次状态转移过来。最后枚举dp[n][state] 得到最大值。

有了最大值之后判断差值的最小值就很容易了。

(这题数据比较水了,没想到有真么多做法。直接暴力都能骗过我的数据)

 

G.本来想出质因子分解的,然后比赛时发现出水了。。直接暴力枚举就行了= =

为了加快速度注意利用性质,比如随着数字的增大连续的数字的个数是非递增的之类的。

 

H.这题最后还是没人过哩,好忧桑= =,标称的做法是离线+树状数组(求全局最大值)

首先对于每个数,预处理出其和其它数&的所有可能的结果(比如5,其可能结果是1,4,5)

再开一个last数组,记录每个数(0到1024)在离线扫描的时候上一次出现的位置。然后离线扫描,没遇到一个新的元素,就在其上一次出现过的位置将其所有可能&的结果加入到树状数组中,然后对于一组查询(r等于当前处理到的元素),求出其l处向右的最大值。原理就是出现过至少两次的最大的数就是所求的&的最大值。

说得比较含糊,具体看代码吧~

 

下学期马上就要开学了,很快就是省赛和四省赛了呀,同学们可要加把劲呀。从这次比赛看出,很多同学寒假的训练还是不够勤奋。新生从月赛中看到什么还不会的算法数据结构神马的就要多去学,老队员建议多打比赛(CF,TC,各个OJ月赛神马的)保持状态。

接下三月份还有月赛,希望每个同学努力训练,争取下一次多多AC^_^.

 

 

NEUACM 2015年一月月赛 题解

Published by:

第一次月赛为了照顾下新生,所以题目比较水,没怎么考算法。。所以后果是有10+个人ak了= =b..

A

题目意思就是给你A,B,C 三种方式理财,然后每个月会给你一个年利率,然后每个月的本金+利润可以在下一个月接着理财, 但你也可以不选择任何方式理财。

double a[3][100];

double money;

int n;

int main(){

scanf(“%d”,&n);

while(n–){

for(int i = 0;i < 3;i++){

for(int j = 0;j < 12;j++){

scanf(“%lf”,&a[i][j]);

}

}

scanf(“%lf”,&money);

double begin = 1.0;

for(int i = 0;i < 12;i++){

double v = 0;

for(int j = 0;j < 3;j++){

if(a[j][i] > v)

v = a[j][i];

}

v /= 100.0;

begin = begin * (1 + v);

}

money = money * (begin – 1.0);

printf(“%.3lf\n”,money);

}

return 0;

}

然后这样就很水很水了。。  只用从1月开始一直到12月,找出最大的利润,如果这时候利润是< 0的,那就不理财,  然后结果就是输出最终的利润。 签到题。。题意略坑。

B

题意: 给出n 个数字,求出存在多少个组连续的t个数字,满足这t个数字每个数字的值都小于c.

Solution :

注意下是保证单个数字的值小于c即可,只需要从前向后模拟下,扫描到val>c 时将扫描长度清零即可。

C 水题

把k=10^n代进去k*(k+1)/2就看出来了

D

这题很水的。 看起来吓人。 因为每次操作,只会操作1-10的倍数

所以每次操作的时候只用一个 sum 数组来存储加的数是多少就可以了。。

然后就输出区间 (1 , r) – (1 , l-1) 的和就OK了。

输出的时候,只用判断1到 l中,有多少个数是 1的倍数,2的倍数,3的倍数,。。。10的倍数。。然后累加就好了。。是不是特别简单… 专为不懂数据结构者设计。

int CASE;

int n;

char s[10];

int a,b;

long long sum[20];

long long QUERY(int l){

if(l == 0)return 0;

long long ans = 0;

for(int i = 1;i <= 10;i++){

ans += sum[i] * (l / i);

}

return ans;

}

long long Answer(int l,int r){

return QUERY(r) – QUERY(l-1);

}

int main(){

scanf(“%d”,&CASE);

while(CASE–){

scanf(“%d”,&n);

for(int i = 0;i < 20;i++) sum[i] = 0;

int q;

scanf(“%d”,&q);

while(q–){

scanf(“%s %d %d”,s,&a,&b);

if(s[0] == ‘P’){

sum[a] += b;

}else{

printf(“%lld\n”,Answer(a,b));

}

}

}

return 0;

}

数据比较水,只卡掉了运行超时

2333333

E

题意: 给出n个数的随机排列,求最少交换多少步能变成递增序列。

Solution : 考虑每个置换,假设存在一个置换的循环节为n , 要想把每个置换内的数字交换到自己的位置至少需要n-1 次,因此只需要分解出这个序列每个置换的循环节求和即可。

比如 :

1 2 3 4 5 6 7

2 3 4 1 6 5 7

分解完之后就是 (1,2,3,4) (5,6) (7) 那么最后的总是就是 3+1+0 =4。

此题存在很多的变形,比如说每次交换的代价是两个数的和(两个数的最大值),求变成递增序列最少代价。但是这些都是通过求置换得出来的。

const int MAX = 1e7+10;
int a[MAX],c[MAX];
bool vis[MAX];
int main() {
freopen(“in.txt”,”r”,stdin);
freopen(“out.txt”,”w”,stdout);
int n,res,cnt;
while(scanf(“%d”,&n)==1) {
for(int i=1;i<=n;i++) {
scanf(“%d”,&a[i]);
}
memset(vis,false,sizeof(vis));
res=0;
for(int i=1;i<=n;i++) {
if(!vis[i]) {
cnt=1;
int pos=a[i];
vis[i]=true;
while(!vis[pos]) {
vis[pos]=true;
pos=a[pos];
cnt++;
}
res+=cnt-1;
}
}
printf(“%d\n”,res);
}
return 0;
}

F

题意: n颗子弹扫射,前k颗以1cm 的速度弹道上扬 ,后(n-k) 发子弹保持在最高点,问最多能达到多少个靶子 。

Solution :

考虑的到靶子的最大高度,可以直接采用枚举的方法。 可以先枚举第一发子弹的位置pos,那么第k发子弹的位置就是在 pos+k-1 处, 只要求出pos ,pos+1,…..pos+k-1 这一段连续的序列中有多少个位置是靶子就好。可以利用前缀和预处理下,然后最后 (n-k)发由于是保持在同一个高度,可以直接算出当前的高度有多少个靶子。

注意 : 不能直接去枚举靶子的位置,还有就是要把数组开大一点。

int main() {
// freopen(“in.txt”,”r”,stdin);
// freopen(“out.txt”,”w”,stdout);
int n,k,m;
while(scanf(“%d %d %d”,&n,&m,&k)==3) {
memset(sum,0,sizeof(sum));
memset(vis,0,sizeof(vis));
int Max=0;
for(int i=1;i<=n;++i) {
scanf(“%d”,&H[i]);
Max=max(Max,H[i]);
if(!vis[H[i]]) {
add(H[i],1);
}
vis[H[i]]++;
}
int res=0,tot;
for(int i=1;i<=Max;i++) {
tot=0;
int R=i+k-1,L=i;
tot+=Query(R)-Query(L-1);
if(vis[R]>m-k) {
tot+=m-k;
}
else {
tot+=max(vis[R]-1,0);
}
res=max(res,tot);
}
printf(“%d\n”,res);
}
return 0;
}

G 数学题

打个表就看成规律了,然后数比较大要用高精度。

如果用递推形式的话弄高精度比较麻烦,所以可以将结果化简一下再用。

如果n和m不同奇偶,那么答案是0,否则答案是2^((n-1)*(m-1))

(用数学归纳法可以证)

H

一个水题,几何题, 就是需要处理下凹边型的情况跟 1个点的情况。

int n;

struct point{

double x,y;

}P[1010],C;

double dis(const point &a,const point &b){

return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));

}

double D_dis(const point &a,const point &b){

return ((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));

}

double getArea(const point &x, const point &y, const point & z){

double a = dis(x,y);

double b = dis(y,z);

double c = dis(z,x);

double p = (a+b+c)/2;

return sqrt(p*(p-a)*(p-b)*(p-c)) * 2;

}

double GET(point p,point q){

double mm ,h;

mm = min( dis(C,q), dis(C ,p));

h = getArea(p,q,C) / dis(p,q);

if(D_dis(p,C) > (D_dis(p,q) + D_dis(q,C)) || D_dis(C,q) > (D_dis(p,C) + D_dis(p,q)) ){

return mm;

}else{

return min(mm,h);

}

}

int main(){

int CASE;

scanf(“%d”,&CASE);

while(CASE–){

scanf(“%d”,&n);

for(int i = 0;i < n;i++){

scanf(“%lf %lf”,&P[i].x,&P[i].y);

}

P[n] = P[0];

scanf(“%lf %lf”,&C.x,&C.y);

if(n == 1){

printf(“%.3lf\n”,dis(C,P[0]));

continue;

}

double ret = 0x3f3f3f3f;

for(int i = 0;i < n;i++){

double tmp = GET(P[i],P[i+1]);

ret = ret < tmp ? ret : tmp;

}

printf(“%.3lf\n”,ret);

}

return 0;

}

I 数学期望

做法很多,我的做法是n只蚂蚁中每两只蚂蚁碰面的机会是1/4,而这样的蚂蚁对数是C(n,2)

所以答案就是C(n,2)/4.

J 签到题

去后一半数就达到最大值,它们之间的最小公约数为1,所以满足要求,所以答案是n-[n/2]

 出题人

2015-1-31

寒假师徒分配

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竞赛集训队的奖品。