2015 苏州大学程序设计校赛题解 #2

作者: shad0w_walker(admin) 分类: 算法 发布时间: 2015-12-02 18:30 ė 6 没有评论

2015苏州大学程序设计竞赛暨苏州大学ACM-ICPC校选赛(第二场)于2015年12月14日落下帷幕

每题Accepted及Submitted如下:
2015suda#2-problem

最终前15名Ranklist如下:
2015suda#2-ranklist

写在最前面:我想对每个大一新生说,你们处在最好的时代,这是一个在苏大搞ACM最好的时代,你们注定是创造历史的一届。还记得一年前我还和你们一样的时候,苏大在ACM的赛场上最好的成绩只有铜牌,有时还惨不忍睹,但是这一年包括之前的几年来,学院对竞赛的重视程度在提高,我们在ACM竞赛中的综合排名飞速的上升,我可以感觉到,未来的一两年里我们还有很大的上升空间,ACM实验室的一切都在越来越好,我们有更多的东西能留给你们和你们之后的人,一切都要看学号是15开头的你们了。别在最该奋斗是时候,选择了安逸。

这次题目面向大一新生,类型主要在于模拟、数学、贪心等,需要一定读题能力以及思维量,没有任何复杂的算法,在我看来是挺不错的。标程的题均代码行数为16.5行,远小于C语言考试程序题。从Ranklist上来看,本场的题目难度基本达到预期,除了我的1008没有人尝试以外,其他题目都有同学AC。然而1008并不是防AK题,只要耐心算就能算出来,比赛时有两个同学已经推出公式但忘记开根号,很可惜。
总之,学弟学妹们都表现的很不错!

这些题目是我们队三人出的,前四题奚政,中间三题凯凯王,最后三题是我
附上队友博客地址http://www.cnblogs.com/cenariusxzhttp://www.ivy-end.com/


 

以下是题解——

1001  草爷要的榜 (模拟、排序)

by 奚政

这个题主要是为了向新生专门介绍一下关于ACM赛制的罚时规则。
只不过为了题目难易程度,设定的是所有队伍过题数一样,就不需要优先对题数进行排序了。本来准备按照罚时大小依次输出队伍编号的,担心新生不会用结构体双关键字排序并且想不到两个数组一起排序,所以干脆改成只要计算罚时并排序输出就行。这题也并没有卡n方的复杂复,可以说基本是读懂规则会读入就能AC啦。
大概需要注意的只有以“xx:yy”的格式读入时间,并且了解给出的提交次数包括1次AC,所以错误提交的次数是读入的次数减1。
于是这题就是对每支队伍读入所有时间转为分钟数,再依次读入所有提交次数,分别减1再乘20分钟,计算总和之后对每个队伍的罚时排个序就行了。
反正数据给的很足,基本过数据的都能过这题。要是没注意到提交次数包括AC,发现样例少了那么多分钟也就发现了吧。

点击此处展开代码

 

1002 草爷要的雷(模拟)

by 奚政

这个题其实还是非常水的,主要是题目限制比较多,所以关键是读懂整个规则和扫雷图的布局。
因为图中只有一个数字点开的,所以遍历一遍图找出那个数字的坐标,然后对它的8个方向的格子累计一下有多少‘*’,然后数字除以‘*’个数约分一下就行。因为不会存在概率0,也不会存在概率大于1,还说明用1/1表示1,所以放心地约分就行。
主要需要读懂题意,所以我一开始出的时候担心题意太绕。然后随意模拟一下,就是要注意数字可能出现在边界,那么扫它周围8个方向的时候需要先判断坐标有没有出界。然后就是统计并约分,约分首选用gcd昂,而且gcd在另一题里面给出了,只不过不会用gcd其实也不要紧,因为一共就1+2+3+…+8种共36种约分的情况,动手列一下就行了。

点击此处展开代码

 

1003 草爷要的福利题(water)

by 奚政

这题真心福利题了,大家一起签到昂。
只要看懂题意,然后随便敲就行。
先读完题目个数和两个系数,之后读入每题的两个参数分别与系数相乘并求和,然后比较求出最大值就行了。

点击此处展开代码

 

1004 草爷要的数(数学、容斥)

by 奚政

这个题其实也不难,主要是有卡点。
首先题目是简单容斥,思路比较好想。
对于刚高中毕业的新生来说,如果求两个数在一段区间内的倍数的个数,那么肯定能想到是两数各自的倍数个数的和减去两数最小公倍数的倍数个数。
比如4、6就是
4的倍数的个数+6的倍数的个数-12的倍数的个数;
那么三个数其实就是分别的倍数个数-两两最小公倍数的倍数个数+三数最小公倍数的倍数个数。
比如4、6、10就是
4的倍数的个数+6的倍数的个数+10的倍数的个数-12的倍数的个数-20的倍数的个数-30的倍数的个数+60的倍数的个数;
具体画一下韦恩图就知道了。
然后统计在区间[a,b]内的个数就用[1,b]内个数减去[1,a-1]内的个数就行了。
比如4在[a,b]间的倍数个数就是 b/4-(a-1)/4,做简单除法就ok。
给出的一些良心数据+给出gcd(最大公约数)的函数也容易引导大家去想lcm(最小公倍数=两数乘积除以两数的gcd)。
而三个数的lcm则为其中两个数的lcm与另外一个数再求lcm。
而这题的坑点在于虽然所有求出的gcd都保证小于1e18,但是两数的乘积却是可能大于long long的
即:a*b/gcd(a,b)时结果小于1e18,但是a*b时可能大于long long范围;
因此需要考察一下解题的素养了,我们可以先用其中一个数除以两数gcd再乘以另一个数
即:a/gcd(a,b)*b;
这样只要能够保证结果是小于1e18的,那么过程中必定也不会大于1e18。

点击此处展开代码

 

1005 Ivy::Timer(water、题意杀)

by Ivy_End

这道题目主要考察对题意的理解以及对于二进制的掌握。
首先我们考虑题目中给出的机器周期,也就是说一条指令需要1/1,000,000s的时间,那么1s能够执行1,000,000次运算,也就是说1ms可以执行1,000条指令。如果我们需要定时1ms,也就是需要是的处理器工作1,000条指令。
其次,我们知道定时器的工作方式是当存在溢出时,自动停止,定时结束。也就是说我们程序的执行时间取决于我们对于定时器初始的赋值以及定时器溢出时的值。
我们知道,16位二进制数的最大值为65535,也就是说到达65536的时候就会溢出。所以如果我们需要定时1ms,那么就需要将定时器的值改为65536-X*1000。
接下来,我们知道对于16位的二进制数X,它的高8位数据为X%256,低8位数据为x/256。
那么,我们只需要输出这两个数据就好了。

点击此处展开代码

 

1006 Ivy::Capacitance(贪心)

by Ivy_End

Ivy_End:
首先,我们知道电容串联越串越小,电容并联越并越大;这可以由电阻并联越并越小,电阻串联越串越大,以及电容串并联与电阻串并联的关系导出。
根据上述关系,我们可以这样处理电容C,假设C=A/B,那么对于C的整数部分[A/B],我们只需要选择使用[A/B]个电容并联就可以得到。那么剩下来的小数部分怎么办呢。
这时候,我们用到了一条结论,如果最少使用K个电容构成A/B法拉的电容,那么也最少需要K个电容才能构成B/A法拉的电容。
因此,对于A/B的小数部分,我们只需要对它取倒数即可,直到最后不存在小数部分。

shad0w_walker:
电容值为A/B的电容并联上n个电容值为1的电容,得到的总电容为(A+nB)/B(分子上加n个分母)
电容值为A/B的电容串联上n个电容值为1的电容,得到的总电容为A/(B+nA)(分母上加n个分子)
所以这道题只要这样处理——
如果A>B,则使A’=A%B,那么A/B就是由A’/B并联上n=[A/B]个电阻得到
如果A<B,则使B’=B%A,那么A/B就是由A/B’串联上n=[B/A]个电阻得到
不断进行上述操作直到A/B=1即可

点击此处展开代码

 

1007 Ivy::Multiply(water)

by Ivy_End

这是一道水题,只需要用到最基本的乘法运算和取模运算。需要注意的是运算过程中需要使用long long数据类型。

点击此处展开代码

 

1008 低能数学题(计算几何)

by shad0w_walker

这是一道中规中矩的高中解析几何题,需要一定计算量,耐心地做下去应该不是很难吧(逃

首先,由题知\(F(1,0)\),设\(A(x_{1},y_{1})\),\(B(x_{2},y_{2})\)
假设\(l_{AB}\)的斜率为\(k\),可以得到 \(l_{AB}:y=k(x-1)\) ,代入椭圆\(C\)方程中得\((1+2k^{2})x^{2}-4k^{2}x+2k^{2}-2=0\),那么\(x_{1}+x_{2}=\frac{4k^{2}}{1+2k^{2}}\) , \(x_{1}x_{2}=\frac{2k^{2}-2}{1+2k^{2}}\)
则\(x_{C}=\frac{x_{1}+x_{2}}{2}=\frac{2k^{2}}{1+2k^{2}}\),于是
\[PC=\sqrt{1+ (\frac{1}{k})^{2}}\left | x_{C}-x_{P} \right |=\frac{2\sqrt{1+k^{2}}(1+3k^{2})}{(1+2k^{2})\left | k \right |}\]\[AB=\sqrt{1+ k^{2}}\left | x_{1}-x_{2} \right |=\frac{2\sqrt{2}(1+k^{2})}{1+2k^{2}}\]
由\(PC=pAB\)得\((2p^{2}-9)k^{4}+(2p^{2}-6)k^{2}-1=0\)
解之得\(k^{2}=\frac{3-p^{2}\pm p\sqrt{p^{2}-4}}{2p^{2}-9}\)
根据题目要求,取\(\sqrt{k_{1}}\)和\(\sqrt{k_{2}}\) 中取较小的一个正数,于是\[ans=\sqrt{\frac{3-p^{2}+ p\sqrt{p^{2}-4}}{2p^{2}-9}}\]

点击此处展开代码

 

1009 中能数学题(数学、打表)

by shad0w_walker

一道简单的数学题,题目的难度主要还是在思维过程上

用\(f(n)\)表示凯神第\(n\)天产生的新妹子。考虑到第\(n\)天新认识的妹子是由第\(n-1\)天和第\(n-2\)天新认识的妹子介绍的,所以数列\(f(n)\)的递推式为\(f(n)=f(n-1)+f(n-2),f(1)=1\)
可见\(f(n)\)是斐波那契数列。
那么题目要求的就是\(p_{n}=\frac{f(n)}{f(n-1)}\)

接着给出这题要用到的重要结论\[\lim_{n\rightarrow \infty}\frac{f(n)}{f(n-1)}=\frac{1}{\phi }(\phi=\frac{\sqrt{5}-1}{2}\approx 0.61803)\]也就是说\(n\)趋向于无穷的时候,\(f(n)\)与\(f(n-1)\)的比值趋向于定值\(1.61803\)
讲到这里,这道题的解法也就有了:当\(n\)较小时\((n \leq 15)\),直接按照题意模拟,当\(n\)较大时\((n>15)\),直接输出\(1.61803\)(题目要求的小数精度)

如果要证明以上结论也很简单,现给出一种证明方法:
斐波那契数列的通项公式为\(f(n)=\frac{1}{\sqrt5}\left (\phi ^{n} +(\frac{1}{\phi })^{n}\right)\)(该通项有多种证法,其中一部分参阅 斐波那契数列_百度百科_通项公式
那么\(\frac{f(n)}{f(n-1)}=\frac{\frac{1}{\sqrt5}\left (\phi ^{n} +(\frac{1}{\phi })^{n}\right)}{\frac{1}{\sqrt5}\left (\phi ^{n-1} +(\frac{1}{\phi })^{n-1}\right)}=\frac{\phi ^{n} +(\frac{1}{\phi })^{n}}{\phi ^{n-1} +(\frac{1}{\phi })^{n-1}}\)
因为\(\phi<1\),所以\(\phi^{n}\rightarrow 0\),所以\(\frac{f(n)}{f(n-1)}\approx\frac{(\frac{1}{\phi })^{n}}{(\frac{1}{\phi })^{n-1}}=\frac{1}{\phi }\)

其实本题完全不需要以上这么多的思考过程——
首先,按照题意模拟,可以得到1,1,2,3,5,8,13…的数列,然后一眼看出\(f(n)\)的递推式或者\(f(n)\)是斐波那契数列。
接着,如果你把\(n\)从1开始的答案一个一个输出来看看,立马就可以看出\(n \leq 15\)时,答案不断逼近\(1.61803\);之后答案稳定于\(1.61803\)。于是解法一目了然

点击此处展开代码

 

1010 高能数学题(water)

by shad0w_walker

水题。
3的倍数有一个规律——所有位的数字和为3的倍数,所以只要累加所有数位然后对3取模判断即可。
另外,这题卡了Java大数做法: )

点击此处展开代码


 

让我们一起期待接下来的第三场校赛!

剧透:你们以为第三场还会给你们涨信心?

本文出自shad0w_walker,转载时请注明出处及相应链接。

本文永久链接: https://www.sdwalker.com/archives/410.html

0

发表评论

电子邮件地址不会被公开。 必填项已用*标注

返回顶部