1.矩阵乘法
注意到，矩阵 B 是一个二进制矩阵。考虑红色的部分，它将和 B 的若干列向量点乘。
若我们将红色部分的长度切块，例如分成 8 个 bit 一组，B 的列向量就只有 256 种情况。
将这些值预处理，就可以用取值代替乘法操作了。
2.字符串的幂
枚举确定了 a 之后，依次删去 S 前缀的 a 和后缀的 a此时有两种情况：
剩下的串与 a 或空串的编辑距离为2
剩下的串最前面 |a|± 1 的串，后面 |a|± 1 的串与 a 的编辑距离为 1
暴力枚举上面的所有情况，用哈希判断字符串相等即可。
3.生命游戏
考虑将生命游戏的坐标转45度，变成往 (1,1), (1,-1), (-1, 1), (-1,-1) 四个方向移动，这样 X 和 Y 就独立了。
很容易证明，单个细胞在第 n 时刻会有 4bits(n) 个存活，且这些坐标可以用形如 (±2k,±2k) 的向量组合表示出来。这里的 k 为 n 的二进制中 1 的那些位。
一开始有两个生命的时候，在第 n 时刻他们可能会有部分重叠，求出重叠的部分容斥即可。
可以将其中一个作为参照系，统计有多少种方案，另一个细胞通过两组形如 (±2k,±2k) 的向量移动能到达这个细胞的位置。这一步枚举 n 然后从低位到高位暴力就好。
考虑到 n 可能很大，可以分开枚举 n 的高位和低位，然后再组合到一起。
4.数格点
这道题跟皮克定理没有任何关系。
将多边形分拆成上下凸壳，然后做梯形分解，问题可以化简为一个线段下符合要求的点的个数。
化简后的问题可以写成标准的类欧几里得的形式
5.数据排序
注意到 n ≤ 15，可以用 O(3n) 或者 O(3n) 的DP求解。
f[S] 表示集合 S 是前 |S|大的元素，然后枚举剩下的元素的子集即可。
6.平衡二叉树
高度为 n 的平衡二叉树，不平衡度最大时，必然是一个高度为 n-1 的满二叉树和一个高度为 n-d-1 的最小平衡二叉树，最小平衡二叉树的大小可以通过上面的公式求出，答案就是 2^{n-1} - 1 - f(n-d-1)
7.数组合并
对每个询问，考虑合并后的数组中前 k 个数的最大值：
假设最大值 x 在红色的位置，深绿色的位置是每个数组中第一个大于 x 的位置，那么必然是黄***域优先于红色，优先于紫色，优先于深绿色和蓝色。
此时只需要二分这个最大值即可快速求出第 k 个数所在的位置，这一步可以用线段树上二分来完成。
8.卡牌游戏
9.游戏
基本思想：分块
将所有人按照度数分为小点和大点：小点的度数不超过sqrt(M) ，大点的数量不超过 sqrt(M)。
我们需要为每一个大点维护一个当前在线的好友列表：
当一个小点上线时，更新邻接大点的在线列表
若邻接的大点有在线的，则与第一个组队
当一个小点和一个大点组队时，将小点标记为大点的小弟，并从所有大点的在线列表中将其删除
之后有人想和该小点组队，则直接通知其大佬
即使一个大佬下线，他的小弟仍在这个大佬的队伍中，直至该小弟下线（此时大佬成为虚结点）
当大佬上线时，直接访问自己的在线好友列表，并把其中没有大佬的在线小点纳为小弟。
w 这样当小点上线、下线时，所有与之相关的操作的总复杂度为 O(sqrt(M))。
而大点上线时，邀请别的大点复杂度为 O(sqrt(M)).
而由于只有没有大佬的在线小点才需要通知，所以通知小点的复杂度均摊是 O(N) 的。
10.魔法阵
11.排队
全部评论
(0) 回帖