“玲珑杯”郑州轻工业学院第九届ACM程序设计大赛圆满结束

“玲珑杯”郑州轻工业学院第九届ACM程序设计大赛圆满结束

     ACM/ICPC国际大学生程序设计竞赛由美国计算机学会主办，是目前国际大学生计算机相关领域公认规模最大、水平最高的赛事之一，对参赛学生的学术水平和实践能力要求很高。为提高学生对ACM/ICPC国际大学生程序设计竞赛的认识，培养学生对程序设计的兴趣，同时为即将举办的河南省第九届ACM程序设计大赛进行热身，郑州轻工业学院计算机与通信工程学院（电子信息工程学院）于2017年4月16日在科学校区举办“玲珑杯”郑州轻工业学院第九届ACM程序设计大赛暨河南高校邀请赛。该赛事收到省内各高校的高度关注，本次大赛吸引了郑州大学、河南大学、河南理工大学、河南工业大学等十几所院校师生参赛代表共计180余支队伍、500多名学生前来切磋交流。大赛得到了郑州珑凌科技有限公司的独家冠名赞助。

     上午九点，郑州轻工业学院第九届“玲珑杯”ACM程序设计大赛暨河南省高校邀请赛正式开始。比赛为10题5小时赛制，其中，大赛终榜里的前10名有5个队伍由高中生大佬承包。其中冠军队获得了3000元奖金。一等奖奖金800元，二等奖奖金500元，三等奖奖金300元。另外，比赛其他表现突出的队伍也分别获得了：最佳新人奖，最佳女队将，最快解题奖等奖励。

     “玲珑杯”为郑州珑凌科技有限公司旗下“玲珑学院”在线教育项目的子项目，经常赞助河南省内高校比赛。除线下和高校的对接，还专门开发设有线上OJ平台“玲珑OJ”，每周六举行“玲珑杯”线上邀请赛，邀请全国各大高校ACmer进行切磋交流，欢迎对算法感兴趣的同学。

玲珑学院官网：http://www.ifrog.cc/

玲珑OJ网址：http://www.ifrog.cc/acm

以下是本次大赛题解 

 ---------------------------------------------------------------------------------------------------------------------------------------------------------------------

“玲珑杯”郑州轻工业学院第九届ACM程序设计大赛题解 

Problem A:

     tmk 射气球 比较简单的题，直接求空间中一个点到直线的距离而已，这道题说了直线和水平的平面平行，我们可以先求投影到直线的距离，然后再算当前点到直线的距离。

 

Problem B:

base64 解密

将 d2hhdCBpcyB0aGUgcmVtYWluZGVyIHdoZW4gdGhlIG51bWJlciBpcyBkaXZpZGVkIGJ5IDIwMTc/

按 base64 解密可以得到 what is the remainder when the number is divided by 2017?所以答案就是 输出 x%2017。 

具体解密规则:由于后面没有’=’，所以直接把每个字符按表转化为 6 位二进制，把每 8 位 分成一组，按 ASCII 码转换为对应字符就可以了。 

 

Problem C:DOBRI  

按题目算出前缀和，对于 i>2，判断 sum[i]是否等于 sum[i-1]+sum[i-2]+sum[i-3]，进行计数， 就可以了。

 

Problem D: hipercijevi

对于每个管道，新建一个点，向管道连接的所有点连一条边，之后进行一次 bfs，将得到的 结果除 2 就可以了。

 

Problem E: Can Win

转化为网络流模型: 

其中 MAX 为第 k 队的最高得分，即 mark[k]+cnrt[k]。
对于每一个 a[i][j]，按左半部分建边;
对于每一个点 i，向汇点建立一条 MAX-mark[i]的边。
从 s 向 t 跑最大流，如果从 s 连向 i，j 的边都满流，则第 k 个队可以获得胜利。 

 

Problem F: Tmk 吃汤饭 模拟，如果有人等待，则一秒一秒模拟，否则，直接跳到下一时刻即可。

 

Problem G: 密室逃脱
可以发现 a^b 与 a 的大小只与 b 的二进制表示中最高位的 1 所在的那一位有关，如果 a 在

这一位是 0，a^b>a，否则 a^b<a，那么就我们只要考虑每一位中有多少个数在这一位是 1 和多少 个数的最高位 1 是这一位，将它们相乘后累加即可，时间复杂度为 O(n*m+m) 

 

Problem H: 维克兹的进制转换

对于一个数，我们先考虑其最后一位为 0、1、2 中的哪一个。 如果 n&1，那么最后一位只能是 1，所以 f[n] = f[n/2]。 否则，那么最后一位可以是 0 或则 2，所以 f[n]=f[n/2]+f[n/2-1]。 特殊地，f[0] = 1，f[1] = 1，f[2] = 2。 

 

Problem I: 这里是天堂!

先考虑当前情况可行与否

如果当 a>n 或 b>m 时是绝对不可行的，概率为 0

当 a+b<n+m 时，k 一定等于 a+b，否则概率为 0

当 a+b==n+m 时，k>=a+b，否则概率为 0 接下来就是求一个概率，考虑到猫猫来的顺序对答案没有影响，所以可以直接使用古典概型，也即求可行的方案数除以总方案数。

可行的方案数为从 n 里选 a 个的方案乘上从 m 里选 b 个的方案数，总方案为从 n+m 里选 a+b个的方案数。也即 C(n,a)*C(m,b)/C(n+m,a+b)。

由于数据很小，所以可以直接用组合数的递推公式 C(n,m)=C(n-1,m-1)+C(n-1,m)求出答案，然后分别作为分子分母花间一下就可以了。

Problem J: ht 的生日 party 【分析】

先举一些例子，当有 10 个人，数 3 个人就出队 我们只要找到小一点的每个数和当前数对应关系是什么就可以了 

例如上图，假设你下一轮 7 个人最后是第 5 个人存活的，那么 10 个人最后是第 4 个同学存 活的，你如果下一轮 7 个人最后是第 1 个人存活的，那么 10 个人最后是第 10 个同学存活的。

现在就是要找 C 数组和 A 数组的对应关系 从C数组先推到B数组，再从B数组推到A数组

设 A 数组的个数为 n，那么 B 数组和 C 数组就有 n-n/m 个数(/为整除)

    A[i]=B[i]+(B[i]-1)/(m-1)

    C[i]=B[(n-n/m)+1-i]

这样就很容易得到这 C 和 A 的关系,设 f[n]表示 n 个人玩游戏，幸存者为第 f[n]个人,所以得到递推式 

复杂度就是 O(n)的