竞赛讨论区 > 【题解】牛客OI周赛2-提高组
头像
牛客网小运营
编辑于 2019-04-10 18:00
+ 关注

【题解】牛客OI周赛2-提高组

(题解由比赛出题人提供,点击右侧“本文相关内容”的题目即可开始做题)

T1 游戏
其实只需要看左上角就行了,因为题目描述写的很清楚,三个人的操作都是为了BLUESKY007能赢,所以游戏一定会结束,那么当横纵坐标最大的非B颜色方格变为B颜色时,可操作的方格范围显然是趋向收敛的,又因为操作规则的要求,左上角的方格在每次操作中都会按规则进行变换,当可操作范围收敛到左上角且左上角变为B颜色时,游戏结束,所以无论中间的操作是怎样进行的,最终左上角的方格一定会变为B颜色,而且进行操作的人数和操作变换长度相同,所以我们只需要判断左上角方格的颜色即可。

T2 水果蛋糕
不妨设n为长,m为宽
m≤2: 显然对于任何一个位置,都不存在另外一个位置使得两者之间距离为,所以此时所有位置都可以放置,此时答案为
m=3: 对于第二行的所有点,都不存在另外一个位置使得两者之间距离为,所以第二行所有位置都可以放置,对于另外两行我们可以发现,(1,1)和(3,4)只能有一个位置放置,(1,2)和(3,5),(1,3)和(3,6),(3,1)和(1,4),(3,2)和(1,5),(3,3)和(1,6)同理。于是当我们最大化放置个数时,每相邻的六列的放置总是相同的且任意相邻六列至多可以放置12个,所以当我们按如图所示的方式开始时会达到最大值,此时答案为

m=4: 同样的,对于任意相邻的六列,仍然满足相邻六列最多放置12个,但是对于不同的n存在不同的方案使得答案最大

所以如果m=4, 能考虑到以上情况的话自然就不是写爆搜的了,所以对爆搜的数据范围设置为,否则会
m≥5:如图为n=7,m=5时的放置方案,类似的,对于任意大小都可以进行类似的放置,此时答案为


T3 好朋友
因为"好朋友"的定义为含有"007",所以有很多情况都会被视为含有"007",例如"10707","17007"等,此时我们发现对于含有"007"的情况的讨论比较复杂,所以我们不妨讨论不含"007的情况,也即对于任意的含有7的数,其中每一个7前都至多有2个0,由此可以设表示在前位有个0的数的个数,在数位DP过程中存当前位置和已有的0的个数,显然在0的个数时,后面的数位上都不可能再有7.在求出不含"007"的数之后,用区间上数的个数减去不含"007"的数的个数即可得到在上含有"007"的数的个数


其他疑问可加以下交流群(加入一个即可啦~)

牛客网OI交流群:811833252
牛客网OI交流群2:370123478
牛客多校算法训练营3:934889305
牛客多校算法训练营4:923675729
牛客多校算法训练营5:975214176


全部评论

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

等你来战

查看全部

热门推荐