长安大学ACM协会

长安大学第二届ACM程序设计竞赛校赛简要题解 写在前面1.出现了密码条打错，网络故障，全程开外网，现场缺乏管理，配置不好用等等问题，沿袭了一直以来校赛出状况的传统，真心感谢各位能够谅解。2.特别感谢西邮袁子涵和张浩然，帮我们解决了$PC^2$的种种问题，并帮忙渡过了正赛开场时最艰难的时候。 A.Count Circles简单统计一下即可，一些写法需要特判$0$的情况。 B.Boys and Girls注意到同性之间的交换位置没有意义，故初始序列和最终序列相比，同性之间的相对位置是不发生变化的。即是说如果初始序列是$B{1}…B{2}…B{3}……B{n}$，省略号处表示有若干个$G$，那么最终序列是$B{1}GB{2}GB{3}G…B{n}G$或者$GB{1}GB{2}GB{3}…GB{n}$,那么最少交换次数就是每个$B$从初始位置移动到最终位置需要的步数之和，分别计算$BGBG…$和$GBGB…$的答案取小者即可。 C.Roses枚举一个圆，对没有被此圆覆盖的点求最小圆覆盖，复杂度为$O（n^4）$。 D.Arrays离线询问，将点按$A$，询问按$x$排序后，问题 ...

讲课之前 我们不妨先考虑下傻瓜式合并，加入我们开一个数组表示某一个集合，那么在集合合并的时候，需要把每一个元素移动至对应集合，合并复杂度O(n),查找复杂度O(n)。我们能优化合并么？当然可以，用链表或者STL的list。 由于不支持随机存取，那么查找的复杂度还是O(n)。怎么优化查找，那就用并查集了 概述 并查集顾名思义就是有“合并集合”和“查找集合”两种操作的关于数据结构的一种算法。 操作初始化：12345678void init() { for(int i=0; i<N; i++) { par[i] = i; rank[i] = 1; }} 查找：12345int find(int x){ return par[x] = find(par[x]);} 合并：1234567891011121314void unite(int x,int y){ x = find(x); y = find(y); i ...

前言首先感谢各位dalao前来参赛，感谢各位领队帮忙判题发球。 比赛之前我们做了不少准备，为的是能做好命题和评测以及招待外宾的工作，不知道各位是否还觉得满意呢。 很高兴这次比赛没有出什么大问题，尽管有熟悉的ESA，熟悉的烂鼠标，以及热身最后崩了一小下。同时赛后我们发现打印的题面并不是最新版本的，但是数据并没有问题，这可能导致一些选手白白花时间多考虑了一些细节上的问题，深表歉意。 我们强行续了一把OJ，尽管它还不是很稳定，目前只放了这次迎新杯的题目，欢迎选手补题，没来现场的也可以在OJ上小玩一下。 题面链接：戳这里看热身赛题面题面链接：戳这里看正式赛题面比赛链接：点击进入,需要先注册终榜链接：戳这里膜大佬 最后，希望各大院校今后都能加强交流与友好往来，祝陕西省的ACM越来越好。 热身赛难度分布热身赛主要让选手熟悉环境与PC^2的使用方法，一共设置了四道题目。其中第一道为测试提交的题，另外三道大概是随便暴力题或比较近期的一些原题简化。由于是热身赛所以难度上也没有去把控，导致有萌新绝望卡题，也有dalao光速AK。 A.欢迎来到彩虹岛 签到题意：输出“Welcome ...

不知不觉已经开学近三个月了，C++你学会了多少呢？或许你学过其他编程语言（这简直不能更好了），想不想和同学同场竞技，敢不敢和西安市最优秀的大一萌新一较高下？是时候约一场比赛了！ 赛事长安大学第三届ACM程序设计竞赛 竞赛规则使用一台电脑编写代码（C++、Java等）解决给出的问题。以解出的题目数量为排名标准，题目数量相同的以比赛用时为排名标准（用时越短排名越靠前）。每到题目第一个解出的同学会得到一只一血气球哦～之后解出该题的同学会得到和此题相对应的颜色的气球。 题目范围题目数量为10~12道。题目类型包含但不限于以下内容：签到题，暴力，贪心，简单的数学推导题目，递推和二分，考思维的题，考验代码能力的模拟题。 日程表2016年12月4日在长安大学渭水校区举办. 时间 事项 地点 9:30-10:00 热身赛进场，比赛环境介绍 明远二区 10:00-11:00 热身赛 明远二区 12:00-16:00 正式赛 明远二区 19:00-20:30 颁奖及讲题 WX3304 参赛对象 长安大学大一同学均可参加 长安大学大二非集训队同学 ...

竞赛规则 ACM-ICPC是团队形式的比赛，每队由至多3名队员组成。队员必须是来自本校研一及以下的学生，同时需要注意每位选手最多可以参加2次全球总决赛和5次区域赛，每个赛季最多参加2次区域赛。 比赛期间，每队使用1台电脑，需要在5个小时内使用C、C++或Java中的一种，编写程序解决7到13个问题，题目均为英文题面。近年来，随着选手水平的提高，区域赛题目数量有增多的趋势。 题目规格以一道例题来讲解常规的ACM赛题组成部分： A + B Problem 题目标题Time Limit: 2000/1000 MS (Java/Others) 运行时间限制Memory Limit: 65536/32768 K (Java/Others) 内存空间限制Problem Description 问题描述Calculate A + B.Input 输入格式Each line will contain two integers A and B. Process to end of file.Output 输出格式For each case, output A + B in one line.Sa ...

由于审核未通过，此页内容删除

A协纳新啦！啦！！啦！！！长安大学ACM-ICPC协会纳新啦！期待你的加入！！！ 新一届的纳新工作又开始啦，我们还准备了有趣的题目和小礼品哦！不管你是哪个学院，不管你是哪个专业喜欢算法，喜欢挑战的萌新们还等什么，赶快加入我们吧！！ FAQ$Q:$ 什么是 $ACM \; ICPC$ 吖？$A:$ 这是国际大学生程序设计竞赛的简称啦~也就是说，如果你水平足够的话是可以参加每年一次的世界总决赛的(orz…)。 $Q:$ 那A协是干嘛的吖？$A:$ 我们是一群喜欢算法的萌新。啊，不对，泥萌才是萌新！我们只是算法爱好者~那泥萌喜欢算法嘛&_&喜欢就加入我们吧！ $Q:$ 什么是C语言？什么是算法？什么是程序设计？$A:$ 你需要看这个嘛，还有这个。或许看一道题目你能更清晰的了解ACM-ICPC，点这里。 $Q:$ 比赛形式是什么样的吖？$A:$ 正式比赛中，是最多三个人一支队伍，共同使用一台电脑，解决约十道题目。可以携带任何纸质资料，题目为英文描述。在提交某道题目的答案后几分钟内即可出现是否通过此题目的结果。 关于培训在上学期，我们会有C语言培训课。所以，不必担心你 ...

长安大学ACM-ICPC集训队每年两次纳新，分别在每学期开学时。秋季学期主要针对大二的同学，春季学期主要针对大一的同学。除了条件一外，还需要分别满足条件二、三才可能会被接纳。 加入条件一 人品要好，不弄虚作假，尊重老师和队友，和其他队员能融洽相处 愿意无条件服从集训队的训练安排、组队安排、参赛安排以及其他统一的安排 有毅力，愿意花时间进行相关的训练，而不是患得患失 加入条件二（对大一） 在各类OJ做题超过 130 题的大一同学，妹纸的题量略少一点也无妨 在cf至少有五次比赛记录，且至少连续三场 rating 大于1450 在新生赛中成绩优异者、日常训练完成度高者 加入条件三（对大二） 参考条件二 提供你的博客地址、OJ 昵称等 请自行对比集训队15级队员 其他或许你还不满足上面的条件，但是十分喜欢算法，愿意花更多的时间，我们也会酌情考虑的。 加入方式请联系clw同学（QQ:1141166429)，之后我们安排考核，通过后即可加入集训队！以上，至2017年7月份失效！ 后话请不要止步于此！！！

省赛顺利闭幕，榜单和题目在这里，简要发一下题解吧。 前四题出题人只给了简要题解╮(╯_╰)╭ 有同学要的A题的标程： A A.Rui and her cylinders可以使用各种办法来做这道题，包括模拟退火，三分等。需要注意到两个在圆柱侧面的点的最短路可能经过底面。 B.Rui and her functions主要x的单调性，可以问题进行整体的分治。 C.Rui and her sequences注意到操作1是没有意义的，因为操作1结束后，局部来说需要用最多次数的操作2才能实现目标，这一定是比只考虑操作2要更劣的。 修改题面之后删除条件1 D.Rui and her triangles对于任意一对点a,b，假设它们的木棍长度是x,y(x>y)，如果第三边的长度在(x-y,x+y)内就可以组成三角形。于是用cnt[i][j]表示子树i中有多少对木棍满足“与长度为j的木棍可以组成三角形”。那么对所有的点对a,b，设a和b的lca是c，给cnt[c][]的(x-y,x+y)一段加1。然后按各个子树对cnt求和。那么一个子树i中的三角形总数就等于sigma cnt[i][ ...

1. 新学期的算法课程本学期的算法课程将于下周（第二周）重新起航，欢迎所有喜欢算法的同学前来听课。时间仍然为每周五晚7:00，没有特殊通知的情况下，地点均在修远3304教室 具体内容以及相关学习资料和挂题情况，请见：算法课安排 2. 省赛报名 外校学生均由外校教练办理报名手续，故本报名通知针对本校学生 2016年第四届陕西省ACM-ICPC程序设计竞赛将于5月22日在本校举行， 详情请关注 省赛官网 长安大学的同学们~第四届陕西省ACM/ICPC程序设计竞赛 将于今年5月22日在长安大学渭水校区举行，期间将会有来自陕西省各个大学的ACMER队伍(预计100个队伍)前来参赛比赛将会有金牌、银牌、铜牌，并且会有学分，你想拿学分么，你想体验大学竞赛激情四射的角逐么，你想跟他人比拼智力能力努力程度么？！快来组队(三人一队)报名吧！ 对于本校的学生：（只需填写报名表，不收取报名费）报名信息发送至chdacmdaydayup@163.com (报名单详见群文件”报名单”) 3. 更多帮助有任何问题，请加入长安大学ACM协会官方群「88837395」进行询问。