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

作者: shad0w_walker(admin) 分类: 算法 发布时间: 2016-12-06 14:19 ė 6 没有评论

部分题目还是挺友好的,可是做出的题目数量比较少,总的来说思维量比较大,代码量小。每道题的C语言代码只要点进比赛,看第一或者第二名的即可。

 

A 求n个数中的最大数

点击此处展开代码

 

B 判断一个网格中是否只含有B、W、G三个字符

点击此处展开代码

 

C 每个队有一个得分区间,你可以在这个区间内指定每个队的得分,使得并列第一名尽量多,输出最多的并列第一名人数。

只要指定最高分为所有区间左端点中最大的值,就能保证人数最多,所以取出这个值,判断一下它最多能落在几个区间内。

点击此处展开代码

 

D 这是一道数学题,国王在A点,龙在B点,龙始终朝着国王的方向运动,它的速度为国王的2倍,国王从A点出发可以随意走动,但是要保证能够回到A点且不被龙抓到,请问国王可以活动的区域面积大小为多少。

具体的题解请看这里https://yadi.sk/i/-BcFxkTry7mZm,但是这道题有个简单的方法——首先观察得到最终的面积与AB两点的距离平方成正比,其次观察得到题目样例中距离为1时的面积0.916297857297023=7π/24,所以只要求出两点距离d,那么答案就是7π/24*d*d

点击此处展开代码

 

E 给定一个p,对于每个i(i<p),求一个j,使得j*j mod p = i

只要枚举所有小于p的j,看它能够满足哪些i即可,但是这道题的io比较大,python会TLE

点击此处展开代码

 

F 给定一个湖的轮廓,有人沿着湖骑自行车,问在几个拐弯处,如果不拐弯而直行,会掉进河里。

对于每个拐弯的地点,有左拐和右拐两种,如果是左拐那就会掉进河里,所以只要判断一下下一个点在当前行走方向的左边还是右边即可。

但是这道题有个简单的做法。这个多边形只有90度和270度两种内角,只有270度内角处会掉入河中,所以只要找出270度内角的个数。进一步发现,多边形内角和是有一定约束的,所以在四个都是90度角的矩形基础上,每增加一个270度内角,必然有一个90度内角与之成对出现,所以最后的答案与多边形形状无关,只与多边形的顶点数有关。请先想清楚上述过程再点开代码。

点击此处展开代码

 

G 首先找到度数最小的点,然后给所有与它相连的点以及度数为0的点标上0,其余标上1

我。。懒得写python程序了。。大家去看现场的ac代码吧。。

 

H 按题意递推即可

点击此处展开代码

 

I 你有一个等级Lv,以及一个数字,当你在Lv.k时,你可以选择给这个数字加k,当这个数字是完全平方数时,你可以给它开根,并且你的lv加1。一开始你在Lv.1且数字是2,你想要达到Lv.n+1,请输出n个数,第i个表示在Lv.i时,你需要加i几次才能到下一Lv。

假设每次进入Lv.k时的初始数字为(k-1)k,发现每次只要进行k*k*k+2*k*k+1次加k操作就能达到[k(k+1)]^2,然后开根就是Lv.k+1的初始数了。

点击此处展开代码

 

J

题意:初始有n对男生和女生,编号都是从1–n,并且1号男生和1号女生配对,2号男生和2号女生配对…n号男生和n号女生配对。这些配对的男女生初始顺时针编号从小到大围成一圈。 有两种操作,均是只移动男生: 1 x 将所有男生都顺时针移动x位(x<0时是逆时针移动|x|位),例如x=2时,在3号位的男生就移到了5号位。 2 将所有两两相邻的男生换位,即1号位男生和2号位男生换位,3号位男生和4号位男生换位等。问Q次操作后,从1到n输出所有女生匹配的男生编号。 数据范围n<=1e6,Q<=2e6

分析:注意到所有奇数编号和偶数编号的男生的相对顺序都不变,基于这一点,只需要记录编号为1和2男生的位置 那么剩下所有男生的位置都可以递推出来了。 假设1号和2号男生的位置分别是one和two。 对于操作1很简单:one和two直接加上x,然后对n取模,考虑负数和0的情况。 对于操作2,因为是奇数偶数和相邻偶数位置交换且one的奇偶性和two不同,所以需要判断one的奇偶。

可是这道题的io也很大啊,python还是会TLE哦。

点击此处展开代码

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

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

0

发表评论

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

返回顶部