A、智乃的二进制

Tag

二进制、二分、lowbit、注意力题（

题解

简易题解：注意到 在时满足题意当且仅当，注意到答案关于a,b单调递增，二分，又注意到最大只有60，所以枚举。

注意到形如的整数一定符合题目要求，这是因为10进制可以看成是2*5进制，将题目条件变为找到两个数字使得符合条件，由于题目要求将其转为2进制后，低位不变，所以显然必须令的低位第二个二进制位在a的最低二进制位左侧。

打表寻找这类数字倒数第二个二进制位的关系

1                0000000000000000000000000001
10               0000000000000000000000001010
100              0000000000000000000001100100
1000             0000000000000000001111101000
10000            0000000000000010011100010000
100000           0000000000011000011010100000
1000000          0000000011110100001001000000
10000000         0000100110001001011010000000
100000000        0101111101011110000100000000

统计下这些数字中低位二进制中，倒数一个1和倒数第二个1之间间隔了几个0，并记录成一个新的数列。

这个的含义是，假设,往后数几个二进制位作为a时能够使得符合题目要求，例如它的意思是10只能+100组成110这一个符合条件的数字，而不能+1000组成1010，则表示100可以和1000，10000分别组成1100，10100这两个数字

有了数列，我们可以很轻松的构造出所有符合题目要求的数字

看着这个数列非常的眼熟，如果你的数据结构掌握的很好，可以注意力惊人的反应过来，这不就是树状数组嘛

我们找一颗树状数组看下，发现这个数列就是树状数组中每个节点的高度，即

接下来要做的事情就很简单了，注意到 在时答案关于a,b单调递增，二分转化为判定性问题，既有多少个符合条件的数字部小于二分给定的，对于部可以暴力枚举，反正只有60种可能性。

B、智乃的瓷砖

Tag

签到

题解

签到，注意"\\"

C、智乃的草坪

Tag

几何、二分，线段覆盖

题解

首先注意到有效洒水器的个数越大，用时越短，反之用时越大，具有单调性。

所以二分答案t，反过来检查有效洒水器的个数，看是否不大于k个。

注意到洒水器全部位于坐标轴上，所以只要能够完整覆盖到矩形的边缘，就能够满足要求。

通过几何手段，利用勾股定理可求得矩形边缘与圆的截线段，接下来跑一个贪心的线段覆盖即可。

另：线段覆盖在跳跃的时候要写成r=max(l.r,r)而不是r=l.r直接赋值，好几个线段覆盖这样写错的。。。不知道为啥喵

D、智乃的果子

Tag

贪心、排序、双端队列

题解

首先这道题的原题是NOIP2004合并果子，如果不知道的话可以先出门学一下原题。

方法一

直接按照原题的方式做，使用优先队列处理，只不过取模的小细节需要处理，这种方法的时间复杂度是的，使用py的话无法通过，请使用方法二

方法二

使用双端队列，注意到每次贪心合并的过程，都是取当前集合中的最小值和次小值进行合并，所以这个合并的过程本身就是单调有序的，不需要使用优先队列排序，故可以把优先队列修改为双端队列，每次从队头取最小，合并后直接放到队尾，整体复杂度降低到，使用py交题的话先用pypy3交，不行再换python3，一般来讲pypy3时编译执行效率更高。

E、智乃的最大子段和取模

Tag

贪心、二分，数据结构

题解

与最大子段和原题相同，都是将其拆分成两个前缀和的差，既找到sum(r)-sum(l-1)的最大值，接下来分两种情况讨论

1. sum(r)-sum(l-1) > 0 说明取模不会产生影响，直接当成原题做。
2. sum(r)-sum(l-1) < 0 则可能由于取模运算导致它变成一个非常大的数字。

对于第二种情况，注意到 sum(x)在过程中取余，它的取值范围是[0,mod)，所以做差之后只可能在(-mod,0]这个区间，故对于这种情况，需要且仅需要补充一个mod，在计算max的过程中补上一个+mod即可。

编码实现上可以使用 std::map,std::set等数据结构进行二分查找。

F、智乃的算法竞赛群友

Tag

贪心、暴力，背包

题解

首先注意到只有三种决策

1.填充td

2.填充qcjjkkt

3.填充qcjjkktd

三种决策的长度分别为2，7，8，最小公倍数是56，如果n=k*56，那么问题变得非常简单，直接贪心使用一种决策填满

否则对剩余的部分做处理，但是有个坑点是不能直接对56取余，至少要做到56*2=112，既n%56+56的部分。

对于这个数据范围，爱怎么搞怎么搞，无论是dp还是枚举都能够很方便的通过本题。

(PS：对于这类问题，可以使用AC自动机(max,+)转移矩阵快速幂求解，感兴趣可自行了解)

G、智乃的箭头魔术

Tag

模拟

题解

按照题意模拟即可

（不一定要写代码模拟，直接现实中折一下按照顺序操作记录下来输入答案也能通过）

H、智乃的矩阵

Tag

棋盘染色、贪心

（B题其实是H题的提示）

二维数组有一种经典的棋盘染色二分图模型，之所以叫棋盘染色是指对于一个二维数组做二分图染色后，其颜色结构形如一个国际象棋的棋盘。

棋盘染色后，注意到对于每个操作，实际没有改变黑色与白色的总和（因为每次操作相当于黑色+1-1，白色+1-1，和不变），既黑白之间不会发生值的改变和交换。

又注意到

1 1
-1 -1

叠加

1 -1
1 -1

得到

2 0
0 -2

发现对于颜色相同的格子，可以任意加减移动一个偶数，所以只要将整个棋盘构造到奇偶性相同，就可以直接利用上述结论。

故只需要检查以下内容

1. 黑色集合的和是否能够平均分配sum/n*n(需要提前判断可整除)
2. 白色集合的和是否能够平均分配sum/n*n(需要提前判断可整除)
3. 在前两个条件的基础上，是否能够通过2*2的操作使得所有数字奇偶性相同

对于3，只需要写个for循环，当碰到不满足条件的数字时贪心的进行修改即可。

I、智乃挖坑

Tag：

二分、前缀和差分

首先原题是 NOIP2012借教室 原题是有线段树和二分两个解法的，本题使用数据结构无简单解法，只能使用二分解法。

首先如果没看过原题的二分解法，需要先去看一下原题的二分解法，简单来讲就是利用差分的O(1)修改O(n)检查特性，二分操作的次数，看是否能满足条件。

这里用到一个三角形差分的技巧，通过做两次前缀和来实现

假设数组一开始是

1 0 0 0 0 0 0 0 0 0

一次前缀和后变为

1 1 1 1 1 1 1 1 1 1

在做一次前缀和后变为

1 2 3 4 5 6 7 8 9 10

假设现在只想加到6，后面不想要了，则一开始的差分数组为

1 0 0 0 0 0 -7 6 0 0 0 

做一次前缀和后，变为

1 1 1 1 1 1 -6 0 0 0 0 

第二次前缀和后，变为

1 2 3 4 5 6 0 0 0 0 0 

然后在对称方向使用同样的方法操作即可。

剩下的部分和NOIP2012借教室的二分解法相同。

J、智乃的幻方

Tag

签到

题解

按照题目要求检查行、列、对角线即可，或者枚举三阶幻方的全部8种解，直接判断是不是这8种解也可以