先给大家道个歉, 验题的时候没有仔细验过1004, 导致样例出了一点问题. 还有1001, 标程一开始是错的, 后来似乎抢救了回来(也许没有抢救回来, 于是1001的题解就不提供了), 导致这个题的难度远超过了1001. 总之, 是我的疏忽, 给大家带来的不便, 十分抱歉. ### 1001 GCD is Funny 终于搞清楚了这个题的做法, 于是来补个题解. 再次对造成的rating变化以及做题感受道歉. 考虑这题操作的本质, 就是每次选择三个数, 然后丢掉一个数, 之后加回去两个相同的数. 本来一个直观的想法就是两两$gcd$, 但是这个反例很容易举, 比如$6, 10, 15, 30$. 之后又一个想法就是求任意一个$size \ge 2$的子集的gcd, 但是这个反例也有一个反例, 比如$6, 10, 15$. 这个想法之所以错了就是因为我们每次要丢掉一个数. 那么是不是只要考虑$2 \le size < n$的子集就好了呢? 对, 这样就好了. 考虑到, 最后留下来的数一定是某个子集的gcd. 我们只要在一开始丢掉了一个数, 考虑留下来两个数是$x,x$, 那么又选了另一个数$y$的话, 我们只要丢掉其中一个$x$就能获得了两个$\gcd(x,y)$, 也就是说接下来每次操作我们都有了一个额外的数用来丢弃, 且不会改变子集$gcd$的种类数. 接下来只要枚举答案$g$, 判断$g$是否可能是gcd就好了. 这个做法比较复杂, 我采用的是直接计算gcd是$g$子集个数(这个是一个经典的容斥, 这里不表), 为了避免使用大数, 取了若干个乘积超过$2^{500}$的质数来取模. 如果模每个质数的方案数都是0, 那么$g$肯定不会存在在最后结果中. 唉, 这个做法真切和标题. ## 1002. Square Distance 显然只需要考虑前一半就好了. 令$dp(i,j)$表示考虑完前$i$个字符, 距离恰好是$j$是否可行. 随便转移一下就好了. ## 1003. LCIS 令$f(i)$是以$a_i$结尾的最大值, $g(i)$是以$b_i$结尾的最大值. 答案就是$\max_{a_i = b_j} \{\min(f(i),g(j)\}$. $f$和$g$随便dp一下就出来了. ## 1004. Black White Tree 考虑所有大小为$i$的子树, 令这些子树中最多有$f(i)$个黑色节点, 最少有$g(i)$个黑色节点, 显然对于所有$g(i) \le j \le f(i)$的$j$, 都存在一个大小为$i$的子树恰好包含$j$个黑色节点. 证明比较简单, 这里略过. 于是只要求出$f$和$g$就好了. 这个就是一个普通的树上背包. 每次只枚举到当前子树的$size$的话, 就可以$O(n^2)$求出$f$和$g$了. 当然这个题复杂度还可以更优秀, 可以做到$O(\frac{n^2}{\log n})$, 这里不表. ## 1005. Square Revolution 令$st_i$表示以$s_i$开始的最短square, $ed_i$表示以$s_i$结尾的最短square. 显然对于一个字符串$s_{[l,r]}$, 它是prefix-suffix-square free的, 当且仅当$r < l + st_l - 1$并且$l > r - ed_r+1$. 考虑枚举$l$, 那么只要在区间$[l,l+st_l-2]$中找出所有满足$l > r-ed_r+1$的$r$就好了. 这个只要离线然后用一个树状数组就可以就出来了. 考虑如何求出$st_i$和$ed_i$. 不妨枚举square的长度为$2L$, 然后每隔$L$个字符设置一个关键点. 显然一个长为$2L$的square必然会跨越两个关键点. 考虑相邻两个关键点$i$和$i+1$ $(i \ge 0)$, 令设后缀$i$和后缀$i+1$的最长公共前缀为x, 前缀$i$与前缀$i+1$的最长公共后缀为y. 1. 如果$x+y < L$, 那么不存在一个长度为$2L$的square覆盖关键点$i$和$i+1$ 2. 如果$x+y \ge L$, 那么存在若干个长度为$2L$的square满足条件, 并且显然这些合法square的端点肯定构成了一个区间. 考虑右端点, 这个区间是$[\max\{(i+1)L-x,iL\}+L,\min\{iL+y, (i+1)L\}+L]$. 知道这些区间后就可以随便用个线段树啊, 并查集啊, 求出$st_i$和$ed_i$. 没事干的可以思考下条件改为square free要怎么做呢?

##1001 Price List 求出所有数的和$sum$，如果$q > sum$那么肯定记多了。 时间复杂度$O(n)$。 ##1002 NanoApe Loves Sequence 求出前$i$个数里相邻差值的最大值$f_i$，$i$到$n$里相邻差值的最大值$g_i$，那么$ans=\sum_{i=1}^n \max(|A_{i-1}-A_{i+1}|,f_{i-1},g_{i+1})$。 时间复杂度$O(n)$。 ##1003 NanoApe Loves Sequence Ⅱ 将不小于$m$的数看作$1$，剩下的数看作$0$，那么只要区间内$1$的个数不小于$k$则可行，枚举左端点，右端点可以通过two-pointer求出。 时间复杂度$O(n)$。 ##1004 Keep In Touch 考虑dp，设$f[i][j][k]$表示三个人分别在$i,j,k$时的方案数，直接转移是$O(n^6)$的。 于是考虑加维，设$f[i][j][k][now]$表示三个人分别在$i,j,k$时，目前准备走$now$这个人的方案数，那么转移复杂度就降低到了$O(n^4)$。 ##1005 Price List Strike Back 考虑对序列进行分治，设当前分治区间为$[l,r]$，取$mid=(l+r)/2$，那么所有在$[l,mid)$的询问和$(mid,r]$的询问可以递归分治求解，故只需考虑必然经过$mid$的询问。 设$f[i][j]$表示考虑了$[i,mid]$，目前选出的物品和为$j$时，所选商店到家的距离的最大值最小是多少；$g[i][j]$表示考虑了$(mid,i]$，目前选出的物品和为$j$时，所选商店到家的距离的最大值最小是多少，$f$和$g$都能在$O(100(r-l+1))$的复杂度内求出。 那么对于一个询问$l,r,s,c$，只需要求出$\min(\max(f_i,g_{s-i}))$，然后和$c$比较一下大小就好了。 时间复杂度$O(100(n\log n+m)+m\log n)$。

##1001 预处理前缀和，一旦有两个数模m的值相同，说明中间一部分连续子列可以组成m的倍数。 另外，利用抽屉原理，我们可以得到，一旦n大于等于m，答案一定是YES 复杂度 O（n） ##1002 首先骨牌只要考虑都往右推，其次能带倒骨牌的前提是高度大于等于距离+1。所以如果推一次，那么就是骨牌高度=离下一块骨牌距离+1. 把第一块左边距离设为无穷大，能推nk次，那么就是找nk块左边距离最大的向右推倒即可，所以只需要排序找到前nk-1大的距离。 有个小trick，推的次数可能大于骨牌数量 复杂度 O（nlogn） ##1003 由于y质因数分解式中每个质因数均出现2次，那么y是一个完全平方数，设y=z*z，题目可转换成求z，使得每个质因数出现1次. 我们可以暴力枚举z，检查z是否符合要求，显然当z是质数是符合要求，由素数定理可以得，z的枚举量在logn级别 复杂度 O（$\sqrt[4]{n}log\sqrt[2]{n}$） ##1004 首先最短路不等于k，可以转化成最短路小于k 考虑f[i][d][j]表示连通块大小为i，最短路长度为d，恰好离1距离为d的有j个 转移枚举最短路长度为d-1的有k个，那么首先长度为d的只能向长度为d-1的连边，至少连1条，最多连k条的方案， 接着考虑距离为d的j个点，内部连的方案，最后考虑i-1个点中选j个点的方案（因为1号点离自己距离为0）。 求出f[i][d][j]后，对答案的贡献为从n-1个点中选i-1个点组成连通块大小为i的方案（因为1号点一定在连通块内），乘上剩下n-i个点内部乱连的方案。 复杂度 O（${n}^{3}k$） ##1005 首先有等式(${x}^{a}-1$,${x}^{b}-1$)=${x}^{gcd(a,b)}-1$成立，相当于计算$\sum \sum {x}^{gcd(a,b)}-1$ 。记s[d]=最大公约数为d的对数，答案$\sum s[d]*({x}^{d}-1)$. 先用筛法计算出欧拉函数。把正方形分成上三角和下三角计算，最大公约数为d的数量s[d]=2*(phi[1]+phi[2]+...+phi[n/d])-1,对欧拉函数求一个前缀和，直接枚举最大公约数d复杂度为O（n）。观察s[d]计算公式，可以发现对不同的d，若n/d相同，s[d]不发生变化。根据s[d]分段计算，相同的一段的${x}^{d}-1$可以用等比公式求。复杂度为（$n+T\sqrt{n}logn$)

## Aaronson 答案就是$popcount(n)-popcount(\lfloor \frac{n}{2^m} \rfloor) + \lfloor \frac{n}{2^m} \rfloor$. ## Bellovin 观察下就知道$F(f_1,f_2,...,f_n)=F(a_1,a_2,...,a_n)$, 显然这个是字典序最小的, 于是要求的序列就是$f_1,f_2,...,f_n$. ## Colmerauer 这个题本意是要作为1004的, 原来是要输出$W = (\sum_{a=1}^{n}\sum_{b=1}^{m}{a \oplus b \oplus (S(a,b) \text{ mod }2^{32}}) \text{ mod } 2^{32}$ 为了大家开心的做题就变成输出$W = (\displaystyle\sum_{a=1}^{n}\sum_{b=1}^{m}{a \cdot b \cdot S(a,b)}) \text{ mod } 2^{32}$ 对于矩阵种一个元素$M(x,y)$考虑他可以成为那些子矩阵的鞍点, 用单调队列之类的东西处理出$a,b,c,d$, 分别表示在第$x$行中, 这个元素在第$y-a$列到$y+b$列中都是唯一最小值; 第$y$列中, 这个元素在第$x-c$到$x+d$行中都是唯一最大值. 对于第二个公式, 只需要推导下这个元素对整体式子的贡献就好了. 对于第一个公式, 需要推导下这个元素对每个$S(\cdot,\cdot)$的贡献, 然后会发现就是对一个矩阵加个等差数列, 做二维差分就好了. 这个方法细节多, 且不好写, 于是就没出成这样. ## Dertouzos 随便推导下, 令$y=xd$, 如果$d$是$y$的maximum positive proper divisor, 显然要求$x$是$y$的最小质因子. 令$mp(n)$表示$n$的最小质因子, 那么就有$x \le mp(d)$, 同时有$y < n$, 那么$x \le \lfloor \frac{n-1}{d} \rfloor$. 于是就是计算有多少个素数$x$满足$x \le \min\{mp(d), \lfloor \frac{n-1}{d} \rfloor\}$. 当$d$比较大的时候, $\lfloor \frac{n-1}{d} \rfloor$比较小, 暴力枚举$x$即可. 当$d$比较小的时候, 可以直接预处理出答案. 阈值设置到$10^6 \sim 10^7$都可以过. ## Eades 枚举每个数$x$, 考虑这个数成为最大值的对每个$z(\cdot)$的贡献. 对于每个数$x$, 你都可以求出若干个极大区间$[l_x,r_x]$, 表示这个$x$在区间内是最大值, 不妨假设这个$x$在$[l_x,r_x]$出现了$m$次, 每个位置分别为$p_1,p_2,...,p_m$, 那么就可以转化成一个长度为$m+1$的序列$c_0,c_2,...,c_m$. 其中$c_0=p_1-l+1$ $c_{m}=r-p_m+1$ $c_i=p_{i+1}-p_{i}, 1 \le i < m$ 于是对$z_k$的贡献就是$z_k=\sum_{i=0}^{m}c_i \cdot c_{i+k}$ 这个其实就是$c_0,c_1,...,c_m$和$c_m,c_{m-1},...,c_0$的卷积, 做一次fft就好了.

##1001 Oracle Provider : cxzxxjd 先记录 $0-9$这$10$个数字分别有多少个。不难看出，最小的一个存在的数字和其余的数字降序排列的相加就是答案，但是最小的那个数字不能是$0$，因为题面上说明是正整数。将这两个数加起来时，注意处理进位问题。考虑无解的情况，即一串数字中仅存在$1$个非$0$数字或不存在。 (PS.这道题目原本的时限是$1s$，考虑到题目的难度和评测机的问题，开了$4s$，大家可以自己在FST以后看一下时间。 如果是时限是$1s$的话，$sort$是过不了的，输出也需要优化一下) 时间复杂度 $O(Tn)$。 ##1002 Arrange Provider : frank_c1 首先，根据题意可得B数组应是单调不升的，C数组是单调不降的。 可以发现$ A_1 = B_1 = C_1 $，所以如果$ B_1 \neq C_1 $无解。 进一步，我们发现如果$ B_i < B_{i-1} $，$ A_i = B_i $；如果$ C_i > C_{i-1} $，$ A_i = C_i $。但是如果$ B_i < B_{i-1} $和$ C_i > C_{i-1} $同时满足，就会产生冲突导致无解。 考虑$ B_i = B_{i-1} $和$ C_i = C_{i-1} $同时满足的情况，此时应有$ A_i \in (B_i,C_i) $且$ A_i $没有在之前使用过。因为$ (B_i,C_i) $是不断变大的，我们只需维护一下这个区间内有多少值已经被使用过了，用乘法原理统计答案即可。注意到如果某时刻$ A_i $没有值可以使用，也会导致无解。 时间复杂度$ O(Tn) $。 ##1003 Wool Provider : frank_c1 考虑三角形三条边$ a,b,c $ $ (a \ge b) $的关系$ a - b < c, a + b > c $，即$ c \in (a-b,a+b) $。 令加入的边为$ c $，枚举所有边作为$ a $的情况。对于所有可行的$ b $，显然与$ a $相差最小的可以让$ (a-b,a+b) $覆盖范围最大，所以可以贪心地选择不大于$ a $的最大的$ b $。 于是我们可以先将边按长度排序，然后$ a_i $和$ a_{i + 1} $建一条线段。线段并是不合法的部分。 将所有线段按左端点排序，按序扫描一遍，过程中统计答案即可。 时间复杂度$ O(Tn\ \log n) $。 ##1004 Palace Provider : zkx06111 先不考虑删点。平面上$ n $个点求最近点对是一个经典问题。 对所有点按照$ x $坐标排序。然后分治，求出左半边和右半边的最近点对，对于两边的最近距离取较小的，记为$ d $。取从分治的中间点向左右各距离为$ d $的范围中的所有点，把这些点按照$ y $坐标排序。对于每个点，扫一下与它$ y $坐标差小于等于$ d $的点，更新答案，可以证明这样的点是很少的，不超过6个。时间复杂度$ O(Tn\ \log ^ 2 n) $。 考虑删点的情况： $\cdot $ 删去的点不属于最近点对，对于答案没有影响。 $\cdot $ 平面上存在两对没有公共点的最近点对，则删去的点至多属于一对最近点对，对于答案没有影响。 $\cdot $ 平面上所有最近点对有公共点，且删去的点是某个公共点，最近点对会发生变化。 只有第三种情况，删点会对答案造成影响。而只要求出最近点对，那个对答案造成影响的点一定在最近点对上。 所以只需要先对于所有点求出最近点对。然后分别删去其中的两个点，各求一遍最近点对。删去那两个点后的贡献单独计算，其余情况只需要计算全局最近点对的贡献即可。 时间复杂度$ O(Tn\ \log ^ 2\ n) $。如果把$ y $轴排序改为归并，可以做到$ O(Tn \log n) $的时间复杂度。 $EXT$ 删去两个点怎么做？ ##1005 Jewelry Provider : frank_c1 枚举区间右端点$ r $，考虑$ l $的可行域的大小。 注意到每个字符的贡献一定是一段区间，所以$ l $的可行域是若干段区间的并。 每次右端点向右移时，至多会有一个字符的区间发生改变。 所以我们需要一个支持插入一条线段，删除一条线段和查询线段并操作的数据结构。 和扫描线类似，我们可以用经典的线段树来维护。 时间复杂度$ O(Tn\ \log n) $。