[title]1001 who is the best?[/title] 我们对于每个$a_i$都进行计数，即$b[a_i]++$，如此之后，我们可以一个循环语句$i=1->n$来寻找最大的$b_i$,注意此时应是$b_i>MAX$，而不是$b_i \leq MAX$，这样才能保证出现的是编号最小的。另外需要注意的是每次做完后数组应当清0，否则会影响下次的答案，由于各种非确定性因素我在小数据就已经把没清0的程序卡死了。 [title]1002 lines[/title] 我们可以将一条线段$[x_i,y_i]$分为两个端点$x_i$和$(yi)+1$，在$x_i$时该点会新加入一条线段，同样的，在$(y_i)+1$时该点会减少一条线段，因此对于2n个端点进行排序，令$x_i$为价值1，$y_i$为价值-1，问题转化成了最大区间和，因为1一定在-1之前，因此问题变成最大前缀和，我们寻找最大值就是答案，另外的，这题可以用离散化后线段树来做。复杂度为排序的复杂度即$nlgn$，另外如果用第一种做法数组应是2n，而不是n，由于各种非确定性因素我在小数据就已经设了n=10W的点。 [title]1003 magic balls[/title] 我们令dp[i][j][l]表示i在最长上升子序列中，已经损失j点能量,第i个人转换了ai和bi的最长上升子序列的数目，可以得到方程 dp[i][j][0]=max{dp[k][j][0](a[k]$<$a[i])+1,dp[k][j][1](b[k]$<$a[i])+1},dp[i][j][1]=max(dp[k][j-1][0](a[k]$<$b[i])+1,dp[k][j-1][1](b[k]$<$b[i])+1)。这样是n^2k的，我们换个思路，即从k能转移到哪些i，我们先将体积离散化，再用m颗线段树来维护已损失j点能量的情况下体积为某数的最长上升子序列。这样可以做到nlgnk，不过线段树常数写的很大的话还是会TLE，考虑到求最大值实际上是求1~x的最大值，这样我们可以通过常数非常小的树状数组来解决。另外nm的同时记录两个值的做法可以看下这组数据。 1 5 2 2 1 4 2 3 5 1 4 1 5 [title]1004 stars[/title] 我们可以通过cdq分治来解决这个问题，通过cdq分治，损失一个lgQ的复杂度在线转离线，按第一维先排序，(x1,y1,z1)至(x2,y2,z2)的星星个数可以表示为(0,y1,z2)至(x2,y2,z2)的星星个数减去(0,y1,z1)至(x1-1,y1,z1)的个数，我们先将第二维离散化，按第二维建立权值线段树，再按第三维建立平衡树(即树套树)，可以通过这题，时间复杂度为nlgQlg2n，空间复杂度为nlgn。另外这题可以用cdq分治套cdq分治套线段树（树状数组）来写，复杂度变为nlg2Qlgn，不过常数可能会稍大些，实际上即使题目变成4维我们也可以通过cdq分治套cdq分治套cdq分治套线段树来写。(复杂度为nlg(维数-1)Qlgn)

感谢BestCoder这个比赛平台。感谢Herobs和elfness在题目和技术上给予的帮助。 [title]1001 Alexandra and Prime Numbers[/title] 显然N/M应该是N的最大质因子，这样才能使得M最小。暴力找到最大质因子后用N除就能算出M了。 唯一无解的情况是N=1。 [title]1002 Alexandra and A*B Problem[/title] 最后的A*B应该是xSy的形式，其中y可以为空，并且如果S不以0开头那么x也可以为空。 首先枚举y的长度。在y的长度确定之后，显然x应该越小越好。所以从小到大枚举x。设S的长度为p，y的长度为q，那么可以列方程：$((x*10^p + S)*10^q + y) mod A = 0$。解出y以后，如果$y<10^q$那么解合法。 容易证明，我们只需从0（或1，如果S以0开头）到A枚举x，那么所有的解一定会被枚举到。对于q=0的情况，x的长度不会超过4，所以y的长度也只需要枚举到4就可以了。 对于所有枚举出的长度算出的答案取最优解即可。 当然也可以用其他的枚举方法，只要枚举量大概是1万左右的数量级都是可以的。 [title]1003 Alexandra and COS[/title] 首先在每一行上维护前缀和。 对于每次询问，如果D超过了$\sqrt{N}$，那么直接用前缀和暴力算，每次时间复杂度$O(\sqrt{N})$。 考虑直接预处理出$D \leq \sqrt{N}$的答案。设f[x][y][D]表示答案，那么f[x][y][D]可以利用f[x-D][y-D][D]和上面的前缀和数组迅速算出。预处理的复杂度是$O(N^{2.5})$。 总的时间复杂度就是O(N^2.5 + QN^0.5)。 [title]1004 Alexandra and Two Trees[/title] 做法1： 先考虑在序列上而非树上的情况。设两个序列是a和b。 我们容易找到一个函数f，使得对于任意的i满足f(a[i])=i，并且f(其他)=0。然后把每个b[i]变成f(b[i])。这样就把a变成了1,2,...,n，而原问题的答案不变。 现在问题变成了：每次问b[u2..v2]中，值是u1..v1的元素的个数。这是数据结构的经典题目，可以用线段树或树状数组（离线）或可持久化线段树（在线）做。 对于树上的问题，设两个树是A和B。 我们不可能变换树A使得每次询问在A中都是一段连续区间，但是如果对A进行轻重链剖分，使得每个链的f值是连续的，就能保证每次询问至多查询O(log n)个区间。接下来就可以套用之前的方法用线段树或树状数组（离线）或可持久化线段树（在线）做了。 做法2： 将树上路径(u,v)转化为(1,u)，(1,v)，(1,LCA(u,v))的和与差。每个询问可以转化为9个形如“求(1,u1)和(1,v1)的交集的大小”的询问，这可以通过对树取dfs序后扫描线解决。

[title]1001 Primes Problem[/title] 首先将10000内的素数筛出来(约1000个），$(p_1,p_2,p_3)$枚举三元组前两个$p_1, p_2$，可知若存在$p_3$满足条件，必有$p_3=n-p_1-p_2$，故令$t=n-p_1-p_2$。若t为不小于$p_2$的素数，则t满足$p_3$的条件。则答案加一。 [title]1002 Math Problem[/title] $f(x) = |a*x^3+b*x^2+c*x+d|$, 求最大值。令$g(x)=a*x^3+b*x^2+c*x+d$，f(x)的最大值即为g(x)的正最大值，或者是负最小值。a！=0时，$g'(x) = 3*a*x^2+2*b*x+c$ 求出$g'(x)$的根（若存在，$x_1, x_2$，由导数的性质知零点处有极值。$ans = max(f(x_i)|L \leq x_i \leq R)$.然后考虑两个端点的特殊性有$ans = max(ans, f(L), f(R))$. [title]1003 Bits Problem[/title] 对于一个n-bit数，可以根据与R最高不同位的位置分成几类。比如R=100100010，可以分成0xxxxxxxx,1000xxxxx,10010000x三类。x处可任取0或者1。对于一类数，设与R不同的最高位为L（从低位数起，base 0)，设n0 = n - 高于L位的1的个数。此时和分两部分，高于L位的有$C^{n_0}_L$乘以L位之前的数字，低于L位的部分有$C^{n_0}_L * n0 / L * (2^{L-1})$ (因为低于L位的部分每一个位的1的个数相同，1的个数总数有$C^{n_0}_L*n_0$，平均到每个位则是$C^{n_0}_L*n_0/L$。所以低位部分和有$C^{n_0}_L*n_0/L*(1+2+...+2^{L-1}) = C^{n_0}_L*n_0/L*(2^{L-1}) $ [title]1004 K-short Problem[/title] 一个线段树问题，将坐标离散化，将建筑和询问放在一起离线排序，先排x，再排y，再先排建筑。按y轴建线段树，因为询问最多第10矮，只要将每一个坐标按大小顺序存10个节点即可，每读到一个建筑，将其插入当前y坐标。询问则询问[-inf，y]的区间里低k小的高度。 PS: 第一次出比赛，出现了一些描述问题，非常抱歉。非常感谢Herobs和Elfness的耐心帮助。

[title]1001 Chessboard[/title] 首先，若$n \lt k$，则棋盘连一个$1×k$的矩形都放不下，输出$0$。 我们只需要考虑$n≥k$的情况。将棋盘类似于黑白染色，按$(i+j)$模$k$划分等价类，给每个格子标一个号。 标号之后，会注意到每条从左下到右上的斜线数字都是相同的，那么对于$s×s$的格子，其内部数字有且恰好有$2s-1$种，所以当$s<={k\over2}$的时候，内部数字有$floor({k\over2})*2-1\lt k$种，所以不能有更佳的方案。 从而证明最优的方案一定是仅剩下一个$s×s$的正方形区域没有被覆盖到，其中$s≤{k\over2}$。 而令$l=n$ mod $k$之后，根据$l$大小的不同，可以构造出中心为$l×l$或$(k-l)×(k-l)$的风车形图案，又通过上面证明这个$l$（或$k-l$）就是之前的$s$，所以是最优的。 所以令$l=n$ mod $k$，如果$l≤{k\over2}$，最多可覆盖的格子数即为$n^2-l^2$，否则为$n^2-(k-l)^2$，显然这样的方案是可以构造出来的（风车形）。 [title]1002 Select[/title] 题目大意： 给定一些集合，选择两个来自不同集合的数，加和大于k，问有多少种选择方案。 解题思路： 答案=从所有数中选择的两个加和大于k的数的方案数-在同一个集合中选择的两个加和大于k的数的方案数 而对于同一个集合中选择的两个加和大于k的方案数是可以直接排序然后利用单调性快速统计出来的。 [title]1003 The K-th Distance[/title] 把所有边(u,v) 以及(v,u)放入一个队列，队列每弹出一个元素(u,v)，对于所有与u相邻的点w，如果w!=v，就把(w,u)入队。这样就能一个一个生成前K小的距离。 注意到每条边实际上会入队两次，只要把K翻倍且把ans除2即可，时间复杂度为O(n+K) [title]1004 RootedTree[/title] 做法一： 状压dp，先考虑二叉树的情况，设$f[opt]$为以opt（二进制状态）中所有节点构成一棵有根树的方案。则我们每次需要枚举以哪个节点为根和哪些节点放在左子树，然后剩下的节点放在右子树，最后将两棵子树的方案相乘累加到$f[opt]$。但是这样做可能会重复，我们可以随便固定某个节点一定在左子树，这样就可以解决重复的问题。多叉树可以通过左儿子右兄弟的方法转化成二叉树的问题，这时只需要加一维状态$f[opt][0/1]$, 0的意义和二叉树一样，1的意义是以$opt$构成一个有根树森林的方法，转移方式和二叉树类似。dp的状态总数为$O(2^n)$，转移先枚举根节点再枚举子集，所以总复杂度为$O(n3^n)$。 做法二： 还是状压dp。记录$sum[mask]$代表点集为$mask$的合法有根树方案数，$sub[mask]$代表点集为mask的合法森林方案数，$dp[mask][j]$代表点集为mask且以$j$为根的有根树方案数。 $dp[mask][j] = sub[mask - \{j\}] (L_j <= |mask| <= R_j)$ $sum[mask] = \sum_{j=0}^{n-1}dp[mask][j]$ $sub[mask]$的求法和做法一相同。 由于求森林的时候不需要枚举根，所以求sub的复杂度为$O(3^n)$，求$dp$ 和$sum$的时候不需要枚举子集，时间复杂度为$O(n2^n)$ ,总复杂度为$O(3^n)$。

[title]1001 Revenge of Segment Tree[/title] 求一个序列的所有连续子序列的序列和的和。 考虑每个数出现在多少个子序列之中，假设第i个数为Ai，区间为$[L, R]$。那么包含Ai的区间满足$L \leqslant i \bigcap R \geqslant i$。累加$(L+1)*(N-R)*A[i]$就可以了。 当然不能上来用个线段树无聊大家，是吧。PS. I'm a ds-antier QAQ 复杂度：$O(N)$ 难度：$0.5/5$ [title]1002 Revenge of LIS II[/title] 求序列第二长的上升子序列。 看上去输出第二大的LIS就可以了。嗯，1 1 2可以hack不少了。 LIS的$O(N^2)$做法是$dp[i] = max(dp[j]|a[j] < a[i]) + 1$。如果需要第二大的，再额外DP一个至少有两个不同递增序列结束在i的最大长度。那么$dp_{dirty}[i] = max(dp_{dirty}[j]|a[j] < a[i]) + 1$，或者$dp_{dirty}[i] = max(dp[j]|Count[dp[j]] > 1) + 1$。 这个思路不是很容易推广到$O(NlogN)$的LIS算法中，诸位可以思考一下。 复杂度：$O(N^2)$ 难度：$1.5/5$ [title]1003 Revenge of Nim II[/title] Nim游戏的后手作弊移走一些整堆的物体（不能全拿走），可以保证先手必败吗？ Nim游戏先手必败的条件是$XORSum(a[i]) = 0$。后手的目的就是找到这样的一个非空子集。把这里的$a[i]$看做一个每位为0或1的行，所有的数字组成一个矩阵，矩阵空间的运算是XOR。如果这个矩阵满足性质$Rank_{mat} = RowNum_{mat}$，那么它的任意一个子集的$XORSum$都不相等，且非空子集的$XORSum$不为0，否则矩阵的Rank就会小于RowNum。 如果$Rank_{mat} < RowNum_{mat}$呢？那么对于某个子集满足$Rank_{Submat} < RowNum_{Submat}$，其他的行可以由这个矩阵的某些行XOR得到，就一定存在一个$XORSum(a[i]|a[i]\subset subA) = 0$的subA存在。 复杂度： $O(MAXB^3) | MAXB = log(MAXA)\approx40$ 难度：$2.0/5$ [title]1004 Revenge of iSea[/title] 给出N道难度递增的题目，难度用可能做出的百分比表示，选出K道题目使得做出K-1道题目的概率最大。 假设答案是$\{PC[i]\}$，做出k-1的概率为$\sum\limits_{1\leq i\leq k}(1-P[PC_i])*\prod_{1\leq j\leq k\bigcap j \ne i}P[PC_j]$。直接尝试转化这个式子的效果并不明显。 换个思路，假设最优解已经包含了k-1个了，现在来选取最后一个。K-1个全部做出的概率是$P_{all}(k-1)$，有一道为做出的概率是$P_{less}(k-1)$，现在选取的是$PC_k$，那么做出K-1道的概率是 $P_{all}(k-1)*(1-P[PC_k]) + P_{less}(k-1) * P[PC_k] = $ $P_{all}(k-1) + P[PC_k]* (P_{less}(k-1) - P_{all}(k-1))$ 这是一个关于$PC_k$的一次函数，如果$P_{less}(k-1) - P_{all}(k-1)$为正，选取最大的$PC_k$，否则选取最小的。 这样，可以证明答案一定选取两边的概率，枚举比较一下就可以算出最大的概率了。 还有最后一个问题，需要求字典序最小的。对于左边选取的Pi，当然index越小越好，对于右边的，如果存在相同的value，应该选取index较小的。比如90 80 30 30，如果答案是第一个和最后一个，为了取得最小的字典序，需要用第三个来替换一下第四个。 复杂度：$O(K ^ 3)$ 难度：$2.5/5$