<div><a href="./scores.php?cids=530,531,538,539,540"><img src="/downloads/Round10.png" width="580" /></a><div style="text-align: right;"><a href="./scores.php?cids=530,531,538,539,540">See More</a></div></div> [title]1001 Revenge of Fibonacci[/title] 重新定义fib的前两项为A和B，询问C是否fib数列中的一项。 由于C的范围有限，暴力计算出所有范围的fib数判断一下。 复杂度：$O(fib(C))$ 难度：$0.5/5$ [title]1002 Revenge of GCD[/title] A与B的$k^{th} GCD$。 可以推出答案是$GCD(A, B)$的第K大因子。这个数的最大值是10^12，因此可以枚举所有因子求出第K大的。 复杂度：$O(sqrt(A))$ 难度：$1.0/5$ [title]1003 Revenge of Collinearity[/title] 枚举三点共线三元组中x最小的（即枚举每个点），极角排序，看极角在$(-pi/2, pi/2]$中的直线上点的个数，$sigma(C(num,2))$是当前点x值最小(x相等y值最小)的三元组个数。累加起来为答案。 这里坐标范围很大，所以不要使用$atan2$，$acos$这种函数，会有误差。 手写atan2极角排序的时候，注意区间是$(-pi, pi]$，而不是$(-pi/2, pi/2]$。如果没有想清楚，这里很容易出现错误的排序函数造成comp冲突，恰好生成了这样一组testcase。在HDOJ上测试会RE。一个typical的错误comp函数： [code] bool operator<(const point& rhs) const { long long dif = (long long)x * rhs.y - (long long)y * rhs.x; return dif == 0? (x == rhs.x? y < rhs.y : x < rhs.x) : dif < 0; } [/code] 复杂度： $O(N^2logN)$ 难度：$1.5/5$ [title]1004 Revenge of LIS II[/title] 相对于kNN I，这里去掉了$k\le10$的限制，使得暴力扫描$O(MK)$复杂度过高。 考虑如何快速求出距离最近的k个点的权值之和，这里的距离具有明显的二分性。这样可以在$log(MAXX)$的时间内求出k个点的坐标范围。求出之后的问题是，区间求和，单点更新，树状数组足够解决这个问题了。 在二分的时候注意K和K+1可能都是符合条件的，如果算出K+1被舍弃的话，减小Distance可能得到的是K-1，并不连续，所以要判断一下这种情况。 第一场时候看了一下部分代码，没有人使用了这里最关键的二分处理，于是决定还是放这个题目了。有少部分上次用树状数组或线段树维护的，这道题算是小小补偿了一下。 复杂度：$O(NlogN + M*(log(MAXX) + log(N)))$ 难度：$2.5/5$

<div><a href="./scores.php?cids=530,531,538,539"><img src="/downloads/Round9.png" width="580" /></a><div style="text-align: right;"><a href="./scores.php?cids=530,531,538,539">See More</a></div></div> [title]1001 Revenge of ex-Euclid[/title] 可以枚举步长，但显然暴力枚举x更简单... 复杂度：$O(C/A)$ 难度：$0.5/5$ [title]1002 Revenge of Nim[/title] Nim游戏变成从前往后有序的，谁是winner？ 如果当前堆数目为1，玩家没有选择，只能取走。如此直到第一个不为1的堆，则当前回合行动者必胜。考虑之后的状态为S，如果S为必败态，则玩家可以取完当前堆，否则，将当前堆数目变为1。 复杂度：$O(N)$ 难度：$1.0/5$ [title]1003 Revenge of kNN[/title] 一维的kNN问题，询问某个点的是求出kNN值并替换之。 排序，对每个询问线性扫描。左右两个指针依次比较距离与index即可。注意询问的ID要对应到排序后的ID，并且排序规则要严格按照题目要求的。 复杂度： $O(NlogN + MK)$ 难度：$1.5/5$ [title]1004 Revenge of LIS[/title] 求出LIS长度为K的N排列个数。 回顾一下LIS的$O(NlogN)$做法：保留一个单调递增的数列，分别表示长度为i的递增子序列结尾的最小值。对于新的数字，要么最大长度加1，要么替换掉第一个大于它的数字。 这样我们得到一个$O(3^N * N^3)$的DP。0表示数字未用，1表示数字用过但不在这个数列里面，2表示数字用过并且在数字里面，每次转移枚举未用的数字，按照上述规则更新这个数列值。 但是对于$N=15$，需要的空间和时间复杂度依旧太大，于是，打表提交。 复杂度： $O(3^N * N^3)$ -> 打表 $O(1)$ 那个... 实在是不好意思，上面是未更新前的题解。事实上验题的elfness大大提出了一个更优美的$O(2^N * N^2)$的做法。 按数字1-N的顺序依次枚举添加的数字，用$2^N$的状态保存在那个min数组中的数字，每次新添加数字可以根据位置计算出新的min数组。 怎么快速计算呢？这里如果枚举N的位置是不可行的，这样$2^n$的state记录的信息不够。很巧妙的思路是枚举放在当前位置的数字，比如说1-N-1的排列状态下，枚举第N位为K，那么1-N-1位的$>=k$的数字全加1，就得到了一个1-N的排列。 所以就*厚颜无耻*的把N加到18了，哈哈。 复杂度： $O(2^N * N^2)$ 难度：$3.0/5$ P.S. 本来的题目是BCD + 一个更难的题目，降低了一个梯度的难度并且加强了pretest来为了鼓励新手，希望大家玩的开心，大神们也不要鄙视题目太水。 PP.S. 可能最近还會继续这个系列，一起来体验各种被模板的可怜算法之Revenge吧。

<div><a href="./scores.php?cids=530,531,538"><img src="/downloads/round8.png" width="580" /></a><div style="text-align: right;"><a href="./scores.php?cids=530,531,538">See More</a></div></div> [title]1001 Summary[/title] 数据比较小，直接暴力，然后排序之后统计就可以了。唯一一点就是sum要用long long。 [title]1002 Reading comprehension[/title] 当i是偶数时f[i]=2*f[i-1] 否则f[i]=2*f[i-1]+1 那么我们考虑，f[2*i]=4*f[2*i-2]+2 这样偶项就成为了一个独立的递推数列。 令b[0]=0,b[i]=4*b[i-1]+2 对于f 当i为偶数时，计算b[i/2]就可以了。 当i为奇数时，计算b[i/2]*2+1 计算b[i]可以建立矩阵递推 $\bigl[ \begin{smallmatrix} 4 & 1\\ 0 & 1 \end{smallmatrix} \bigr]$ 最后右边乘上列向量$(0,2)^T$,上面那一项就是b[i]了。 [title]1003 Ordered Subsequence[/title] 首先数字有1万个，先离散化一下，把所有数字对应到1到n之间。这样对结果不影响。 dp[i][j]代表以第i个数字结尾上升子序列长度为j的种数。 dp[i][j]=sum{dp[k][j-1]} for each a[k]$\lt$a[i]&&k$\lt$i 直接写循环会超时。需要优化。 可以用平衡树进行优化，上述的循环过程可以看成是一个区间求和过程。用线段树或者树状数组可以解决。 这样最终的复杂度是n*m*log(n) [title]1004 Primitive Roots[/title] 先暴力求出一个原根。 然后利用结论 设m＞1，g是模m的原根，整数d≥0，则 $g^d$是模m的原根$\Leftrightarrow$(d, $\varphi $(m))＝1 枚举d，构造出所有的解。

<div><a href="./scores.php?cids=530,531"><img src="/downloads/Round7.png" width="580" /></a><div style="text-align: right;"><a href="./scores.php?cids=530,531">See More</a></div></div> 本场命题：小岛(见下图)，敬请期待。 <div><img src="/downloads/xiaodao2.jpg" width="200" /></div> [title]1001 Little Pony and Permutation[/title] 题意： 求一个循环的循环分解。 分析： 直接 while 循环搞搞就好了。 [title]1002 Little Pony and Alohomora Part I[/title] 题意： 求随机排列的期望循环个数。 分析： 【引理 1】对于一个随机排列的某个元素，处在一个长度为 $k$ 的循环中的概率为 $1/n$（与循环的长度无关）。 证明： 方法一： 考察某个元素处在长度为 k 的循环中的方案数，有： $$\binom{n-1}{k-1}(k-1)!(n-k)! = (n-1)$$ 比上总的方案数得到概率。 $$\frac{(n-1)!}{n!} = \frac{1}{n}$$ 方法二： 。。。 我们可以用第一题的方法，将每个排列写成 Cycle Notation，并将每个循环中最小的元素放在末尾。 那么每一个排列的 Cycle Notation 和另一个排列可以建立起一一对应。而 1 处在的循环中的长度等于它在排列中的位置，因此所有长度的概率都是 $\frac{1}{n}$。 考虑 dp 。。设 e[n] 表示长度为 n 的排列的循环个数的期望。。我们枚举其中一个循环的长度。根据期望可加。。有。。。 $$~e[n] = \frac{\sum{i=1}^n e[n-i]}{n}$$ 也就是 e[n] = H[n] （调和级数） 对于调和级数，可以较小项暴力，较大项时用 log() 近似。 [title]1003 Little Pony and Dice[/title] 题意： 有一个 $m$ 面的均匀骰子（[1, $m$]），然后从 0 出发，根据扔的数字，决定向前走的步数，走到 $\geq n$ 时就停止。 求刚好在 $n$ 停止的概率。要求误差1e-5以内。（$1\leq n, m\leq 10^9$） 分析： 当 $n$ 很大时，概率会接近 0，由于误差 $10^{-5}$，当 $n\geq 600000$ 时，直接返回 0。。（实际这个值大约是 550000 左右。。。） 当 $n\geq m$ 时，有： dp[i] = sigma j < i (dp[j])/m dp[i-1] = sigma j < i-1 (dp[j])/m dp[i] - dp[i-1] = dp[i-1]/m dp[i] = dp[i-1]*(1+1/m) 初值 dp[1] = 1/m 解得：$pow(1+1./m,n-1)/m)$。 当 $n\leq m$ 时： 我们考虑直接 DP，需要用部分和优化到 $O(n)$。 [title]1004 Little Pony and Boast Busters[/title] 题意： 给定上下两个排列 A[], B[]，要求询问相同项之间两两连线的交叉数，并支持交换操作。。。 分析： 。。。静态问题就是求排列 P[] 的逆序对。。 其中 P[i] = pA[B[i]]; （这里 pA[] 是 A[] 中某个元素的位置。。类似的 pB[] 是 B[] 中某个元素的位置。。。） 考察交换操作。。无论是交换下排还是上排，都可以看成交换 P[] 中的两项。。。 对于交换下排。。。 [code] swap(B[a], B[b]); pB[B[a]]=a,pB[B[b]]=b, swap(P[a], P[b]); [/code] 对于交换上排。。有。 [code] swap(A[a],A[b]); pA[A[a]]=a,pA[A[b]]=b, swap(P[pB[A[a]]], P[pB[A[b]]]); [/code] 于是转化成动态逆序对问题，支持修改排列中的任意一项。 动态逆序对问题等价于区间 kth 大值（区间 Rank）问题。。可以用经典的树套树方法。。。 。。复杂度 $O(nlog^2n)$。

<div><img src="/downloads/6-10.png" width="580" /></div> [title]1001 Goffi and Median[/title] 题意： 给你一个序列，判断中位数大还是平均数大 分析： 直接搞就好了 [title]1002 Goffi and Squary Partition[/title] 题意： 给你N和K,问能否将N拆分成K个互不相同的正整数,并且其中K-1个数的和为完全平方数 PS：这道题目原来是要求输出一种可行方案的，所以下面题解是按照输出方案的思想搞的。 分析： 我们尝试枚举那个完全平方数 S,然后看能否将他拆分为 K-1 个数,并且不用到N-S 这一步可以用贪心+一次调整来搞定。为了保证 K-1 个数都不同,我们尝试尽量用 1,2,3...这些连续自然数来构造,如果 N-S 出现在这些数中,那么将 N-S 移除,再新加一个数。如果这样都不能拆分成 K-1 个数,那么这个 S 肯定不行。 现在考虑已经用上述方法拆分了,我们需要判断这个拆分是否可行。会产生问题的只有最后一个数,这个数可能和 N-S 一样,也可能出现在之前的序列。如果是出现在之前的序列,那么这个拆分也是不靠谱的。如果和 N-S 一样,那么分两种情况 1. N-S 曾出现在之前的序列,那么显然这个拆分也是不靠谱的 2. N-S 比倒数第二个数大,对于这种我们可以通过调整最后一个数和倒数第二个数的大小,来使得这个拆分成立,假设最后一个数为 a,倒数第二个为 b,只要 a-1,b+1 就好了。当然如果 a-1 = b+1 这个拆分也是不靠谱的这道题目就这样搞定了,其实没必要找所有的完全平方数,只要找小于 N 与 N 最接近的完全平方数就好了。 [title]1003 Goffi and GCD[/title] 题意： 给你 N 和 K,问有多少个数对满足 gcd(N-A, N) * gcd(N - B, N) = N^K 分析： 由于 gcd(a, N) <= N,于是 K>2 都是无解,K=2 只有一个解 A=B=N,只要考虑 K = 1 的情况就好了 其实上式和这个是等价的 gcd(A, N) * gcd(B, N) = N^K,我们枚举 gcd(A, N) = g,那么gcd(B, N) = N / g。问题转化为统计满足 gcd(A, N) = g 的 A 的个数。这个答案就是 ɸ(N/g) 只要枚举 N 的 约数就可以了。答案是 Σɸ(N/g)*ɸ(g) g | N 计算 ɸ 可以递归,也可以直接暴力计算,两个都可以。 [title]1004 Goffi and Graph[/title] 题意： 给你一个无向带权连通图,每条边的权值会随时间线性变化,求下面式子的值 \[\Large\frac{\int_{0}^{T}{(\displaystyle\sum_{i=1}^{n}{F(i,t)})\mathrm{d}t}}{T}\] 其中 F(i, t)表示在时间 t,1~i 所有路径最小边的最大值 分析： 先不要被上述的积分式子吓到,我们先来分析 F(i, t)如何求。显然 F(i, t)肯定在最大生成树上,这是一个经典问题,就不证明了（反证法可证）。 也就是说每个时间如果求出最大生成树,那么 F(i,t)也就搞定了,这驱使我们使用数值积分来做,但是数值积分比较慢,在这道题目情况下可能会超时。 事实上我们发现最大生成树的形态只和边权的相对位置有关。因此我们只要求出 F(i, t)的边变化的时间就好了。只有当 m 条直线相交时,才会发生边权相对位置改变的情况。我们只要求出 m^2 个事件点,然后相邻两个事件点计算答案就好了。 由于只是一条直线,积分所求的就是若干个梯形的面积,我们每次计算只要取中点这样就能保证高精度地计算出答案。事实上验题人一开始是用端点计算的,然后精度误差不忍直视。 我用自适应 simpson 验过这题,速度挺快的,但是貌似有个数据会导致 simpson 出错,不知是不是我的 simpson 写搓了。