Category Archives: 培训通知

2016年第41届ACM-ICPC亚洲区域赛(沈阳站)现场赛名额

Published by:

序号 学校名称 网络赛 WF 其他 总数
1 安徽大学 1 1
2 北华大学 1 1
3 北京大学 1 1 2 4
4 北京航空航天大学 1 1 2
5 北京化工大学 1 1
6 北京交通大学 1 1 2
7 北京科技大学 1 1
8 北京理工大学(含软件学院1个) 1 1 1 3
9 北京林业大学 1 1
10 北京师范大学 1 1 2
11 北京信息科技大学 1 1
12 北京邮电大学 1 1 2
13 常州大学 1 1
14 成都信息工程大学 1 1
15 大连东软信息学院 1 1
16 大连海事大学 1 1
17 大连理工大学 1 2 3
18 电子科技大学 1 1 1 3
19 电子科技大学中山学院 1 1
20 东北林业大学 1 2 3
21 东北农业大学 2 2
22 东北师范大学 1 1 1 3
23 福建工程学院 1 1
24 福建农林大学 1 1
25 福建师范大学 1 1
26 福州大学 1 1 2
27 复旦大学 1 1 2
28 广东工业大学 1 1 2
29 广州大学 1 1
30 国防科技大学 1 1 2
31 哈尔滨工程大学 1 1 2
32 哈尔滨工业大学 1 2 3
33 哈尔滨工业大学(威海) 1 1
34 哈尔滨理工大学 2 2
35 哈尔滨商业大学 1 1
36 杭州电子科技大学 1 1 1 3
37 杭州师范大学 1 1
38 河海大学 1 1
39 河南工业大学 1 1
40 河南理工大学 1 1
41 黑龙江大学 1 1
42 湖南大学 1 1 2
43 湖南工学院 1 1
44 湖南工业大学 1 1 2
45 湖南科技大学 1 1
46 华东交通大学 1 1
47 华东理工大学 1 1
48 华东师范大学 1 1
49 华南理工大学 1 1 2
50 华南农业大学 1 1 2
51 华中科技大学 1 1 2
52 华中农业大学 1 1
53 华中师范大学 1 1 2
54 吉林大学 1 1 1 3
55 吉首大学 1 1
56 济南大学 1 1
57 解放军理工大学 1 1
58 解放军信息工程大学 1 1
59 金策工业综合大学(DPRK) 1 1
60 辽宁大学 1 1
61 南华大学 1 1
62 南京大学 1 1
63 南京航空航天大学 1 1 2
64 南京理工大学 1 1 2
65 南京邮电大学 1 1
66 南开大学 1 1
67 南阳理工学院 1 1
68 宁波大学 1 1 2
69 青岛大学 1 1
70 厦门大学 1 1
71 山东大学 1 1 2
72 山东工商学院 1 1
73 山东科技大学 1 1
74 山东理工大学 1 1
75 山东师范大学 1 1 2
76 上海大学 1 1 2
77 上海交通大学 1 1 2
78 深圳大学 1 1 2
79 沈阳师范大学 1 1
80 首都师范大学 1 1
81 四川大学 1 1
82 苏州大学 1 1
83 天津大学 1 1 2
84 同济大学 1 1 2
85 武汉大学 1 1
86 武汉科技大学 1 1
87 武汉理工大学 1 1
88 西安电子科技大学 1 1
89 西安交通大学 1 1 2
90 西安邮电大学 1 1
91 西北大学 1 1
92 西北工业大学 1 2 3
93 西北农林科技大学 1 1
94 西南交通大学 1 1
95 西南科技大学 1 1
96 西南民族大学 1 1
97 湘潭大学 1 1
98 长安大学 1 1
99 长春理工大学 1 1
100 长沙理工大学 1 1
101 浙江财经大学 1 1
102 浙江大学 1 1 1 3
103 浙江大学城市学院 1 1 2
104 浙江大学宁波理工学院 1 1
105 浙江工业大学 1 1 1 3
106 浙江工业大学之江学院 1 1
107 浙江农林大学 1 1
108 浙江师范大学 1 1 2
109 中国地质大学(北京) 1 1
110 中国地质大学(武汉) 1 1
111 中国科学技术大学 1 1 2
112 中国科学院大学 1 1 2
113 中国人民大学 1 1 2
114 中国石油大学(华东) 1 1 2
115 中南大学 1 1
116 中山大学 1 1 1 3
117 重庆大学 1 1 2
118 重庆邮电大学 1 1

东北大学ACM-ICPC团队2016暑期培训安排

Published by:

(有未尽事宜均会在此处更新通知)

现役队员
7.25-8.21
内容:多校联合赛
http://acm.hdu.edu.cn/contests/contest_list.php
地点:综合楼201
队内练习赛

大一新组队队员
7.23-8.15(Lesson01)
地点:不限
内容:
PartA(必做)
自行学习邓俊辉老师数据结构课程
点击下面链接,自行注册,并完成课程的题目。
完成暑期数据结构(上)数据结构(下)
http://www.xuetangx.com/courses/search?query=%E9%82%93%E4%BF%8A%E8%BE%89
PartB(可选)
自行学习清华邓俊辉老师的计算几何课程
8.15-9.3(Lesson02)
地点:综合楼201
训练内容:
专题讲解
专题训练
新人练习赛(预计三场,作为遴选参加东北四省赛的选拔标准)
校内练习赛难度一场,校赛难度一场,省赛难度一场

东北大学ACM创新实验班(大学生程序设计竞赛团队)选修课名单(浑南校区)

Published by:

通过选拔,以下为东北大学ACM创新实验班(大学生程序设计竞赛团队)选修课名单(浑南校区)。浑南校区与南湖校区分开培养,课程安排会另外通知,请大家安心等待。


班级 姓名 性别 学号
陈浪平 20144830
软信1401 丁宁 20144832
工业工程1501 李冠亚 20150845
软工1501 王锡䶮 20152151
软英1502 郭楚尘 20154693
软工1501 刘旭东 20154816
软工1506 陆慧 20154822
软工1501 张磊 20154824
软英1501 郭清妍 20154825
软英1502 王震远 20154830
软英1502 王文意 20154834
软工1504 牛达明 20154835
软英1502 于笑晨 20154843
软工1502 江锡聪 20154848
软工1503 雷镇丞 20154851
软工1501 蒙宸宇 20154853
软工1501 胡科雷 20154858
软工1506 陈瑜峰 20154863
软工1507 徐毅X 20154864
软工1508 李宗兴 20154869
软工1503 丁宇诚 20154870
软工1502 张加安 20154874
软工1505 任明旭 20154881
软工1502 周伟祥 20154889
软工1505 杨毅博 20154890
软日1501 杭咨存 20154895
软英1501 南亦博 20154896
软工1503 姬辰肇 20154903
软英1502 胡正煦 20154906
软英1502 陈子康 20154914
软英1502 吴浩翔 20154917
软工1502 张旭东 20154919
软工1501 汪航 20154937
软工1501 张兆林 20154938
软工1501 范吕生 20154941
软工1501 孙臣臣 20154944
软工1502 任锐 20154947
软工1503 袁浩 20154948
软工1502 崔志远 20154955
软工1503 张岩森 20154957
软英1502 李瀚芃 20154961
软工1505 李佳宇 20154981
软英1501 张超贺 20154982
软工1501 姚明 20154986
软工1502 王俊皓 20154993
软国1501 王安琪 20154995
软工1502 孟旭晨 20154997
软工1501 刘彦君 20155000
软工1506 郭治锦 20155002
软工1502 彭乙凡 20155012
软日1501 赵昶 20155014
软工1508 展亮 20155033
软英1501 彭炳男 20155037
软工1503 赵阳 20155042
软工1503 吕世伟 20155043
软工1506 蔺昭 20155044
软工1504 张鑫 20155058
软国1502 曹勐 20155061
软英1502 吕浩宇 20155070
软工1507 徐卓辉 20155076
软工1508 刘俊斐 20155077
软工1505 杨谦 20155080
软英1502 周洁 20155086
软工1508 高佩文 20155096
软工1507 周彦兆 20155113
软工1501 曾子卓 20155115
软工1501 田家豪 20155117
软工1506 刘金毅 20155122
数媒1502 刘博文 20155258
软信 李子菁 20155281
软信1501 董婕慧 20155282
软信1502 顾兆 20155283
软信1502 杜晓凡 20155292
软信1502 赵林枫 20155298
软信1501 王茂锟 20155306
软信1501 张源境 20155314
中荷1501 王晟 20155393
李晨余

附件:浑南校区名单

东北大学ACM创新实验班(大学生程序设计竞赛团队)选修课名单(南湖校区)

Published by:

通过选拔,以下为东北大学ACM创新实验班(大学生程序设计竞赛团队)选修课名单(南湖校区)。请同学们与10月15日(本周四)18:30到计算中心二楼机房上课。欢迎名单以外的同学到教室旁听。

本名单并不会直接影响日后的集训队队员选拔,认真刷题、努力学习才是关键!

 

数学1401 方梦凯 20141081
数学与应用数学 黄垠博 20141083
数学1401 王天然 20141091
数学1401 王天然 20141091
应用数学1401 邹宏利 20141100
数学1401 何祺玥 20141102
信计1401 姜宝伟 20141114
信计1401 李俊翔 20141116
信计1401 李林 20141117
信计1401 王飞 20141124
信计1401 王培阳 20141125
信计1401 王元帅 20141126
信计1401 温伟磊 20141127
信计1401 俆硕 20141128
信计1402 吕柏蓉 20141165
应用物理1403 张王霖翰 20141250
应物1403 赵子楠 20141259
工程力学1401 李仁杰 20141305
计算机1403 张露 20141379
计算机1404 诸子轩 20141929
材料成型1406 吴传峰 20142683
电科1402 叶文强 20142861
机械1412 路文杰 20143410
计算机1403 王泽洋 20143656
计算机1403 周芳同 20143673
自动化1405 张昊岩 20144012
电子信息 张子明 20144378
电子信息工程1402 吴珩 20144534
信计1501 王存翔 20151435
信计1501 林鹤翔 20151436
信计1501 孔渝峰 20151443
应数1501 田玉丹妮 20151472
应用数学1501 韩奇东 20151487
安全工程1502 刘梦晶 20151608
测绘1502 赵明明 20151948
机械1505 仇维俊 20153315
自动化1507 蒲帅 20154049
计算机1506 刘静 20154303
计算机1508 刘卓成 20154305
计算机1504 吴越 20154306
计算机1506 莫晓强 20154307
计算机1502 汤星奇 20154308
计算机1506 张无奇 20154313
计算机1507 孔欣雨 20154315
计算机1502 章翰元 20154325
计算机1503 葛欣杰 20154326
计算机1509 潘敏佳 20154329
计算机1505 朱凯铭 20154331
计算机1506 萧则和 20154334
计算机1502 麦恒瑞 20154335
计算机1502 余宝仑 20154337
计算机1508 王新东 20154338
计算机1508 王新东 20154338
计算机1507 张伟康 20154340
计算机1506 韩天柱 20154341
1506 吴俊威 20154342
计算机1508 唐牧天 20154344
计算机1508 王云杰 20154348
计算机1502 杨磊 20154351
计算机1506 王政 20154352
计算机1502 张宗祥 20154353
计算机1509 徐滔 20154356
计算机1502 潘长春 20154359
计算机1507 李开均 20154360
计算机1506 吴佳益 20154361
计算机1502 王东 20154367
计算机1506 闫润格 20154369
计算机1508 张宇航 20154378
计算机1506 张伟颖 20154379
计算机1507 曹润柘 20154382
计算机1509 李书缘 20154383
计算机1503 段金言 20154386
计算机1505 魏家鹏 20154387
计算机1506 李中 20154388
计算机1504 陈欣 20154391
计算机1503 霍玺闻 20154393
计算机1505 田东辉 20154394
计算机1503 贾海峰 20154398
计算机1503 张宇杰 20154406
计算机1508 倪琳 20154412
计算机1505 王兴钰 20154425
计算机1508 马莺僡 20154429
计算机1506 肖宇飞 20154431
计算机1503 孙浩 20154435
计算机1505 张昊 20154440
计算机1503 崔家华 20154442
计算机1509 金璐瑶 20154443
计算机1507 庞凯 20154445
计算机1507 庞凯 20154445
计算机1508 韩雨晴 20154447
计算机1503 刘昕 20154448
计算机1503 范苑飞 20154453
计1509 卫雪 20154456
计算机1504 肖雨晴 20154458
计算机1509 刘校宁 20154467
1505 任泽槟 20154470
计算机1506 王曼竹 20154472
计算机1502 王湛元 20154473
计算机1505 王日升 20154482
计算机1505 王日升 20154482
计算机1503 李旭 20154490
计算机1502 周子群 20154491
计算机1509 刘瑞奇 20154496
计算机1507 梁晨 20154497
计算机1507 张林峰 20154500
计算机1504 宋凯 20154506
计算机1505 安儒智 20154507
计算机1503 刘宝源 20154510
计算机1507 赵帅 20154512
计算机1503 刘子健 20154513
计算机1503 鲍瑞祺 20154571
计算机1503 谢良彬 20154518
计算机1506 黄世财 20154521
计算机1506 龚怿焜 20154522
计算机1503 湛进 20154523
计算机1509 髙金毅 20154525
计算机1507 赵恩泽 20154533
计算机1504 解凌帆 20154535
计算机1509 李天志 20154536
计算机1504 郭苗苗 20154538
计算机1504 覃文翰 20154548
计算机1504 孙艺洋 20154556
计算机1506 于梓元 20154561
计算机1507 石丽君 20154568
电子信息1501 黄楚均 20154631

附件:南湖校区ACM选修课名单

东北大学ACM创新实验班(大学生程序设计竞赛团队) 招新通知(浑南校区)

Published by:

各位同学:

首先感谢你关注东北大学大学生ACM创新实验班(大学生程序设计竞赛团队)招新活动。

想感受计算机程序设计带来的乐趣吗?

想进入东北大学ACM创新实验班与编程牛人交流学习吗?

想入围参加ACM-ICPC国际大学生程序设计竞赛吗?

请参加东北大学ACM创新实验班招新宣讲会。创新创业学院负责ACM竞赛教师和创新实验班的班导师将为你介绍实验班情况和招新流程。望届时参加。

一、宣讲时间:2015年10月10日(周六)13:00-13:30

二、宣讲地点:东北大学浑南校区信息A109教室

三、招新条件:以大一、大二年级学生为主,喜爱编程,对计算机程序设计有浓厚兴趣的同学均可报名。

四、选拔:报名参加的同学需选拔方可进入ACM创新实验班。“新人选拔”计划在10月11日(周日)进行,具体选拔安排将在宣讲会现场发布。

五、学校为ACM创新实验班提供了良好的学习和交流平台,并制定了适合大学生进行程序设计和参加程序设计竞赛的学习方案。浑南校区实验班位于东北大学学生创新创业基地(浑南校区生活服务中心三楼,正在建设中)。通过选拔可进入实验班学习。

 

 

东北大学创新创业学院

ACM创新实验班

2015年10月8日

东北大学ACM创新实验班(大学生程序设计竞赛团队) 招新宣讲通知(南湖校区)

Published by:

各位同学:

欢迎你关注东北大学大学生ACM创新实验班(大学生程序设计竞赛团队)招新活动。

想感受计算机程序设计带来的乐趣吗?

想进入东北大学ACM创新实验班与编程牛人交流学习吗?

想入围参加ACM-ICPC国际大学生程序设计竞赛吗?

来参加东北大学ACM创新实验班招新宣讲会吧!届时东北大学创新创业学院ACM竞赛负责教师和创新实验班的班导师将为你介绍实验班情况和招新流程。

一、宣讲时间:2015年10月9日(周五)12:40-13:30

二、宣讲地点:东北大学科学馆201报告厅(南湖校区)(浑南校区稍后发布)

三、招新条件:以大一、大二年级学生为主,喜爱编程,对计算机程序设计有浓厚兴趣的同学均可报名。

四、选拔:报名参加的同学需选拔方可进入ACM创新实验班。“新人选拔”计划在10月11日(周日)进行,具体选拔安排将在宣讲会现场发布。

五、学校为ACM创新实验班提供了良好的学习和交流平台,并制定了适合大学生进行程序设计和参加程序设计竞赛的学习方案。实验班位于东北大学南湖校区科学馆(学生创新创业基地)401教室和浑南校区学生创新创业基地。通过选拔可进入实验班学习。

 

 

东北大学创新创业学院

ACM创新实验班

2015年10月7日

2015年NEUACM第三次月赛题解

Published by:

榜单:http://acm.neu.edu.cn/hustoj/contestrank.php?cid=1051

标称:http://www.cnblogs.com/acvc/category/677830.html

A

炒股有个macd技术指标,通过快线与慢线的关系,来判断下一日是买入还是卖出.

快线是指最近K天股票收盘价之和/K , 慢线是M天股票收盘价之和/M 。 (M > K)

当快线自下而上穿过慢线,则输出买入标志,当快线自上而下穿过慢线,输出卖出标志。

然后如果数据天数<=M ,则输出silent

这题很简单吧。普及下macd知识

这样我们只需要每次纪录前一天的快线,慢线值,然后再算出今日的 快线、慢线值, 这两个判断是否形成交叉就可以了。方法太多了。
B

答案是6*n-3,由于n超过长整型,所以得用高精度(c,c++手写高精度或者用JAVA大数类)

C

首先题意你要搞懂,就是N个建筑物,高度是可能会变的,范围在[1,Hi], 然后你要给一个至少多长的绳索,使其无论高度怎么变化,都能让人走过去。

看下数据 1<=n,w,H<=100

这就是最基础的动态规划了。。挺水的。。
f[H1][H2], f纪录最优的答案 , H1是前一个建筑物的高度, H2是当前建筑物的高度

有下面的递推关系:

ans[i][j] = max(ans[i][j],ans[i-1][z] + sqrt(w*w + (z-j)*(z-j))); (1<=z<=H[前] ,1<=j<=H[后])

D

题意为求A和B在L和R区间中的最大公约数。

N个询问、L到R区间,暴力肯定超时。

想一下最大公约数的定义,

比如A=420=2*2*3*5*7

B=540=2*2*3*3*3*5

则最大公约数=2*2*3*5=60,其余的公约数也肯定是2,2,3,5的组合

所以我们只要求出A,B的最大公约数,gcd(A,B)的所有公约数然后二分即可

用STL里的upper_bound(常用的还有lower_bound)一行代码即可解决二分

E

分组背包,限制是每组至少取一个
由于有分组,所以不能像01背包那样写成一维dp的形式,所以f[i][j]表示前i组总共j重量下的最大价值。
由于有每组至少取一个的限制,所以转移时注意先对当前组做转移状态,再对前一组做状态转移

//当前物品非当前组的第一件
if (f[i][w-c]>-1) {
f[i][w]=max(f[i][w],f[i][w-c]+v);
}
//当前物品为当前组的第一件
if (f[i-1][w-c]>-1) {
f[i][w]=max(f[i][w],f[i-1][w-c]+v);
}

需要注意就是上面两个if的顺序不能反,因为物品的重量有可能是0…

F

题意:给出n条线段,然后每次询问给一条线段,问这条线段包含前面给出的n条线段的多少条。

首先需要升下维度,吧一维的线段[x1,x2] 看成二维空间中的点,然后画图发现如果一条线段包含另一条线段一定就是满足某种关系。可以见下图。

图片1

方法一:可以直接利用二维前缀和预处理,由于x,y才1000完全可以直接前缀和求出前缀。

方法二:对于方法1如果题目加上修改操作就不能实行,所以可以采用二维的树状数组去求解。

G

显然Kid画的是一个无向欧拉图,其满足两个条件:
1.每个点的度数是偶数
2.图是连通的

对于邻接矩阵A,其平方B=A^2中,B[i][j]表示从点i到点j的路径条数。
首先我们看B[i][i],有两个部分组成:
1.每个点都有自环,所以可以通过这个自环走两次回到自身
2.走到另一个点再走回来(同一条边),这部分等于该点除自环外的度数
由定义可知,如果原图是无向欧拉图,那么第二部分的结果是个偶数,加上第一部分,所以B[i][i]一定是奇数。所以
不满足这个条件的就输出No
然后对于B[i][j],如果大于0,那么就存在这么一种可能:沿i的自环走一次,再走一次到j,即原图中i和j一定有边相连,
所以利用这个条件可以构造出原图。再用并查集判断一下这样构造出来的原图是不是连通的。

H

题意就不叙述了。。

(下面的图画错了,应该是逆时针转)

这题情况蛮多,最基本的思路也是二分。

因为如果qishen能在t时间内抓到萝莉,那他肯定也能在大于t的时间内抓到萝莉

现在需要二分时间t,

首先我们肯定得计算t时间后luoli的位置。

情况A,如果qishen与luoli在t时间的位置A的直线相连不经过灰圆,那么肯定是直接跑过去。

图片2

情况B:

直线连接穿过灰圆

则现在需要求出qishen与圆的切线的切点,luoli与圆切线的切点,考虑蓝色弧长+两段切线的长,看qishen能否在t时间走过这段距离。

图片3

涉及:二分、判断点在某时刻在圆上的位置、直线是否与圆相交、求点与圆的切线、求弧长等。较恶心 >_<

I

一道挺好的数据结构题,据出题人说有4种做法。。
这里给其中的一种做法,就是先预处理出序列中每个数在序列中出现的位置(用10^5个vector存,但总大小不会超过10^5)
然后每次查询时二分左右区间L,R的位置,然后就能得出结果了。

 

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:

师徒分配情况如下:

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

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