ACM—TC 联合招新赛1题解
难度指数:3
这题我本来想放在上一场当防AK题,但是
觉得太简单了又放这场当篇难题了。
解题思路:首先简化问题,如果没有单人皮划艇,显然是将所有人按体重排序,从前往后两两结合最优。题目多了两个单人皮划艇,相等于可以去除两个人,数据范围非常小,只需枚举这两个人即可。
新知识点:
AC代码:
1 |
|
难度指数:3
解题思路:事实上,只有字符R、起点、终点才是我们会落脚的地方。我们要从起点经过若干个字符R到达终点,那么只需计算每个落脚点之间的距离$DIS_i$,使用最大的$DIS_k$作为第一次跳跃的距离就可以到达终点。
AC代码:
1 |
|
难度指数:1.001
看没人写出来的份上加个0.001
解题思路:刚开始第$i$糖果有$i$颗糖,第$j$次你可以选择一袋糖果,在其他糖果袋中加入$j$颗糖。
ps:多种解要求字典序最小,可观察样例,初始时有1 、2两袋糖果,此时有两种解法:
第一种
1 | 1 |
第二种
1 | 2 |
第二种的12字典序小于2。
综上所述,显然只需要输出
1 | n |
即可。
新知识点:
AC代码:
1 |
|
难度指数:4.5
构造题,一般来说这种题都会有一种通解,也就是按某种规律构造,解决这种问题,我们只需找到构造通解的规律即可。
解题思路:找规律。观察第二个样例。前三个数是1到n,后三个数也是1到n的排列,我们可以大胆猜想,只需2n的数就可以构造出正确答案,并且前n个数是1到n。对于后三个数132则可以有很多猜想。
例如:
1 | 1 n 2 n-1 3 n-2 |
1 | 1 3 5 7... 2 4 6 8... |
验证一下n=5,使用猜想二构造时答案正确,并且这种构造字典序十分小,这时候就可以交一发加以验证。
AC代码:
1 |
|
难度指数:2.5
没什么好说的,模拟题,注意细节即可。
AC代码:
1 |
|
难度指数:2
结构体水题。
AC代码:
1 |
|
难度指数:4.7
预处理出答案,最后O1(一次性)查询
新知识点:三维数组
AC代码:
1 |
|
难度指数:0.00001
无 fa ke 说
AC代码:
1 |
|
难度指数:4.4
平局和输都算赢。
AC代码:
1 |
|
难度指数:4.4
三重枚举会时间超限,枚举$i、j$,第三个数就是$n-i-j$。
AC代码:
1 |
|