小白赛26题解

A、牛牛爱学习
答案显然具有单调性，所以考虑二分答案。
对于每次二分check，我们把每本书的知识值从大到小排序后，把按顺序把每本书安排到每一天即可，

B、牛牛爱数学
签到。
把右边式子移到左边，化简后是个完全平方式。
$图片说明$
所以如果a能够整除bc答案就是 $图片说明$
否则就输出-1

C、牛牛种花
考虑对询问离线，将询问和种植的花的位置以x为第一关键词，y为第二关键词升序。
这样保证后面的x不小于前面的x，这样的花只需要统计前面有多少个y小于查询位置的y即可。树状数组维护一下即可。

D、失忆药水
根据题意，我们可以把每个人抽象为一个点，如果a知道b的秘密，那么a和b之间连一条有向边。
刚开始每个人都知道其他n-1个人的秘密，那么就是一个完全图，边都是无向边。
所以问题转换为n个点去连边，最多能连多少条边，并且不形成奇数环
我们知道二分图中，不存在奇数环。
把n个点平均分成两部分，每个点只与另一边的点连边，相同部分的点不连边，那么最多能连ans=n / 2 * (n - n / 2)条边。
(为什么均分边最多?两个数总和不变，要想乘积越大，自然是均分)
答案就是n * (n - 1) / 2 - ans 注意开ll

E、牛牛走迷宫
正常的bfs题，按下、左、右、上的顺序走即可

F、牛牛的序列
首先有个很简单的逻辑坑，题中没说a和b的相对大小
奇数+奇数=偶数 偶数+偶数=偶数 奇数+偶数=奇数
所以对答案的影响就是看有区间内有多少个数的因子和为奇数，奇数的个数才对答案有贡献，偶数不会改变答案的奇偶性。
假设b>a 问题转化为求[1,b]、[1,a-1]中有多少个数因子和为奇数
我们考虑算术基本定理。假设这个数为x，容易得到
$图片说明$
那么根据乘法原理我们容易得到x的因子和sum为
$图片说明$
要想sum为奇数，那么需要每一项等比数列和都是奇数。
注意一下2是一个特殊的素数，只有2是偶数形式的素数。
那么对于2而言，2次幂除了1之外都是偶数，所以2的那一项等比数列和一定是奇数。
那么其他项的等比数列和想要为奇数, 素数因子出现的次数必须为偶数,因为奇数的幂次方还是奇数，但因为有加1的缘故，所以需要偶数个(偶数个奇数相加是偶数，因为有1的缘故，整体和就是奇数)
假设x不存在素因子2，显然他是一个奇数平方数。如果要对x进行加倍并且让因子和sum仍然为奇数，那么只能乘二次幂，也就是说乘的倍数必须是二次幂。因为2的那一项等比数列一定为奇数，倘若多了其他素因子，那么最少会让其中一项等比数列和为偶数，偶数 * 奇数 = 偶数，改变了奇偶性。
所以就是求区间的奇数平方数及其二次幂倍数的个数。
那么容易得到，奇平方数乘上二的偶次幂是一个平方数，也就是sqrt(n).
那么得到了乘上偶次幂的个数后，奇次幂比他大的相邻的偶次幂差二倍，所以乘奇次幂的个数就是sqrt(n/2)。
区间[1,n]的因子和为奇数的个数就是 $\sqrt{n}+\sqrt{\frac{n}{2}}$

G、牛牛爱几何
签到，把四个半圆的面积画一下，容易发现阴影部分的面积都重复计算了两次，那么答案就是两个半径为(n / 2)的的圆的面积减去阴影部分的面积。

H、保卫家园
考虑把问题转化一下，让每个人都有入伍的经历，最大编制的最小值是多少。
这样的话，我们对每个人的入伍时间升序，退伍时间升序。
按顺序让每个人进入队伍中，进入的时候，看看前面入伍的人是不是有可以退伍的，这样的话新进入的人代替要退伍的人的位置即可。
这里的过程可以拿一个优先队列维护退伍时间，退伍时间早的优先。
否则所需要的最大编制个数要加1，我们记录下来每个人在入伍的时候的占据的位置。
对于求出来的最大编制的最小值如果 ≤ 给定的k，说明每个人都可以入伍，输出0即可。
如果＞k，拿个数组记录每个位置有多少个人入伍时候在这个位置，从大到小排序后，选取前k个即可。

I、恶魔果实
直接dfs每个数字能变成多少个数就好，或者10^3跑个floyd也行
然后对于要变的数字计算一下每个数字可以变的方案数，根据乘法原理，直接相乘即可

J、牛牛喜欢字符串
简单贪心。
可以得到n / k个字符串，每一行是一个字符串，这样可以得到一个 n / k行 k列的矩阵，对每一列看哪个字母出现的次数最多即可。假设mx为出现最多的字母，答案就是 $图片说明$