------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
看了别人的题解后我自愧不如,所以我又在原题解上做了一点点的修改(包括T4的代码,请放心食用)
T1 午枫的切蛋糕
个人难度:入门|考察内容:分支结构
由题意得,要沿着直径或者半径平分成(n+1)块蛋糕。不难看出,如果(n+1)是偶数,就能沿着直径切(因为直径只能平均切成2份,所以只能为2的倍数),否则要沿着半径切。但是我们会发现n是大于等于0的,所以(n+1)可能会等于1,因为整个蛋糕已经是1份,所以无需再切。
代码如下:
T2 午枫的卡片游戏
个人难度:入门|考察内容:排序
这道题要我们比较卡片点数大小,虽然小枫的出牌顺序已经固定,但是答案不会因为将位置改变而发生变化,所以我们可以先用两个数组存放卡牌点数并升序排序,如果小午的牌大于小枫的牌,那么就将小午胜的局数加一并弃掉小午和小枫的牌,否则只弃掉小午的牌并让小午的下一张牌和小枫当前的牌比较。
代码如下:
T3 午枫的分割数组
个人难度:入门|考察内容:贪心
既然要数量最多的数的大小,那我们可以直接只选数组中最大的一个数,因为是小午将数组切分成前后两部分,所以可以“邪恶地”只给小枫数组最后一个数,如果第1~n-1个数没有大于第n个数的数(注意,这里是大于),就输出“NO”。
代码如下:
T4 小午的构造
个人难度:普及-|考察内容:模拟
仔细观察后就会发现,ac,aa,wa三个单词都含a,所以需要多增一个变量wordx并一直重复以下操作:
如果 x > y+z+wordx :
wordx++; x--;
结束后又出现了一个问题,如果还剩一个a呢?题目中要wa的数量尽可能少并且还要在最多单词的情况下,所以我们可以把一个wa拆开:
wa a->w a a->w aa
这样就需要再做一次判断:
如果 x < y+z+wordx 并且 z>0 :
z--;
最后输出,x > y+z 的情况就完成了。
接着再来考虑 y+z > x >y 的情况,如果a的数量大于c,那么a的数量就是能组成的最多单词数,wa的数量就是a减去c的数量。
最后剩下了 x < y 的情况,那么最多只能输出a的数量,输出 x 和 0 。
代码如下:
T5 午枫的MEX
个人难度:入门|考察内容:位运算
这道题需要先列一个表格:
n 1 2 3 4 5 6 7 8 答案 1 4 4 8 8 8 8 16
答案看上去就是2log2(n)+1,但是我们会发现一个特殊情况,在1的时候输出的是1,所以需要一个判断。
代码如下:
答案虽然已经分析出来了,但是背后的原理我们也可以分析一下(如果不感兴趣可以直接跳过)
因为是异或,所以位数只减不增,我们随便举一个二进制数做例子:
1010100011
那么能使它变成最大的数就是取反之后的数:
0101011100
因为每个数取反后都会比原数小,所以取反的数就无需考虑,最后的最大值+1就是2log2(n)+1。
那么为什么1的答案是1呢?因为1只有它自己能异或,而自己异或自己的答案是0,所以最大值+1=1。
T6 午枫的陪伴时间
个人难度:普及/提高-|考察内容:贪心,动态规划
这一道题让我们选择小午的要求并计算最少花费,在n项要求中可能会有重复的日期,所以我们先需要算出一日的最少花费:
我们先举个例子:
陪之前 陪之后 省了多少钱 15 13 2 21 18 3 (这个省的最多,选这个) 1000 2000 -1000 1111 1111 0
接着再用动态规划解决多日的最少花费:
代码如下:
以上是全部内容,如果觉得哪里可以优化或更正可以在评论区留言(qwq)