竞赛讨论区 > 【题解】牛客小白月赛4
头像
牛客网小运营
发布于 2019-01-11 16:29
+ 关注

【题解】牛客小白月赛4

(题解由比赛出题人提供,点击右侧“本文相关内容”的题目即可开始做题)
T1 三角形
首先将木棍按长度排序,于是可以确定组成的最大三角形的三根木棍,这三根木棍在排序后的数组中下标显然是连续的,如果偷走的木棍不是这三根木棍中的其中一个,那么答案显然,否则分类处理一下这三种情况即可。

T2 博弈论
答案不可能超过10000,因为数列生成的四位数只有O(n)个,所以从小到大枚举答案暴力判断即可。

T3 病菌感染
事实上答案永远是NO,以下是一个简单的证明:
当一个方格被感染时,该方格至少会有两条边进入到感染区域内,最多会有两条边加到感染区域的边界上,因而,感染区域的周长不会增加,既然整个区域的周长为4*n,那么最终要想全部感染,最初的感染区域必须至少包含n个方格。

T4 郊区春游
先用floyd预处理出R个郊区之间的两两最短路,就可以使用状态压缩DP来解决这个TSP问题啦。

T5 浮点数输出
。。。

T6 等价串
注意到 01 可以变成 10,并且如果A变成B,那么B也一定可以变成A,并且可以添加3个0或者3个1,那么问题就迎刃而解了

T7 黑白棋
理解好规则就差不多了。

T8 相邻的糖果
每次贪心从后往前吃。

T9 合唱队形
最优操作显然是男生和女生交换,那么枚举需要交换的男生,假如他旁边有女生联通块,那么他显然尽量与不在这些联通块里面的女生交换。

T10 强迫症
显然最少的操作数是数字的总个数减去数字的总数。

其他疑问可加以下交流群(加入一个即可啦~)
牛客多校算法训练营1:453799454
牛客全国算法训练营2:330766563
牛客多校算法训练营3:934889305

全部评论

(1) 回帖
加载中...
话题 回帖