520

直接输出2的N次方即可。

icebound的账单

简单模拟，从头到尾扫一遍，把所有的数加起来，判断是否比0大即可。时间复杂度 $$O(n)$$ 。

Mex Query

从第一个数字开始扫描，维护一个数组 $$vis[x]$$ ，使得所有的 $$vis[a[i]]$$ 为1,最后从 $$vis[0]$$ 开始扫描，找到第一个 $$vis[x]=0$$ 的 $$x$$ ,输出 $$x$$ 即可。时间复杂度 $$O(n)$$

神殿

简单模拟。从区间 $$[l,r]$$ 枚举整数 $$P$$ ，每次计算每个数字含1的数量，找到符合题意的即可。时间复杂度 $$O(nlogn)$$ 。

跑图

BFS。将所有传送点当作起点放入队列进行BFS，处理出传送点到每个玩家的距离即可。时间复杂度 $$O(n \times m)$$ 。

icebound的商店

简单DP。观察可以发现物品的价格为斐波那契数列第 $$2$$ 项到第 $$17$$ 项，可以看作完全背包问题。设 $$f[i]$$ 为购买商品价格为 $$i$$ 的方案数。则 $$f[0]=1,f[i]=∑f[i-w[j]]$$ ，其中w[j]为第 $$j$$ 个物品的价格。DP时注意取模。复杂度 $$O(Txn)$$

Nim Game

博弈论+前缀和。由简单的博弈论知识可以得知，对于 $$n$$ 个数字 $$a_{n}$$ 的NIM游戏，后手必胜的状态为 $$a_{1}$$ xor $$a_{2}$$ xor $$a_{3}...$$ xor $$a_{n}=0$$ 。只需要处理异或的前缀和 $$s[n]$$ ，每次输出 $$s[r] \ xor \ s[l-1]$$ 的值即可。

Bitmap

哈希。使用二维哈希预处理出两个矩阵的哈希数组，对于 $$A$$ 矩阵中所有的与 $$B$$ 大小相同的子矩阵 $$C$$ ，减去 $$C[0][0] \times ∑basex \times ∑basey$$ （其中 $$basex$$ 和 $$basey$$ 是行与列的哈希字典集大小)，得到矩阵 $$C$$ 的减去 $$C$$ 左上角的值 $$C[0][0]$$ 的差分矩阵 $$D$$ 的哈希值，对 $$B$$ 做相同处理得到 $$B$$ 的差分矩阵 $$E$$ .如果 $$E$$ 的哈希值与 $$D$$ 的哈希值相等，则可以认为是一个合法的答案。时间复杂度 $$O(n \times n)$$ 。本题数据范围较小，使用一维哈希逐行匹配也可以AC。

Defending Plan: Support

图论。最终答案的位置与边权无关，只看点权，树的加权重心即为答案。找到树的加权重心后dfs得到答案即可。证明参照树的重心：如果我的答案取在树的加权重心后，将答案从树的重心移动到任意一个子树中，答案均会增加，所以答案应该取在树的加权重心。

K Multiple Longest Commom Subsequence

动态规划。设 $$f[i][j]$$ 表示 $$A$$ 串处理到 $$i$$ 位置， $$B$$ 串处理到 $$j$$ 位置的答案。预处理出从 $$A$$ 串 $$i$$ 位置向前数，第 $$k$$ 个与 $$i$$ 位置数字相同的位置 $$p[i]$$ ，用相同方式处理出B串的 $$q[i]$$ 。

则转移方程为 $$f[i][j]=max(f[i-1][j],f[i][j-1],f[i-p[i]][j-q[j]]+1)$$ ,其中第三种转移 $$f[i][j]=f[i-p[i]][j-q[j]]+1$$ 必须在 $$a[i]=b[j]$$ 的情况下转移。

Beautiful Array

组合数学。对 $$x$$ 分解质因数，得到 $$n$$ 个质因子，每个质因子的指数为 $$p_i$$ ，如果不考虑正负，对于每个质因子，可以看成有 $$P_i$$ 个相同的小球，放到 $$y$$ 个不同的盒子里的方案数。用组合数学知识求出方案数，利用乘法原理把他们乘起来，然后考虑正负号，乘上2^(y-1)，得到最终答案。

Power Seq

如果在一个长度为 $len$ 区间之内，存在一个数字管制这个区间，则第 $len/2$ 大的数字必然为答案，从而该问题转化为求解一个区间的第 $k$ 大的数字 以及 求解这个数字在该区间的出现次数的问题。

考虑用线段树维护值域，线段树上每一个点用$set$ 维护区间即可。

维护区间方法 ： 在 $set$ 里加入若干个线段，每个线段代表该区间的所有元素 $\in [l, r]$， 删除 $lower\_bound$ 锁定区间，中间迭代删除，均摊分析复杂度：对于线段树上每一个点的$set$ 中，每个线段只会被删除一次，线段有$O(n+m)$ 条。从而时间复杂度 $$O((n+m) \times (logn) \times (logn))$$