旅

北航第十一届程序设计竞赛网络预赛题解

A. 模式

计算机学院是6系，软件学院是21系，对于输入的学号只需要判断$\lfloor \frac{id}{10000} \rfloor$是多少即可。

B. 并联变阻器

题意即统计满足$a,b\le N$且$\frac{ab}{a+b}$是整数的二元组$(a,b)$的个数，条件也即$a,b\le N$且$(a+b)|ab$。

令$r=\gcd(a,b)$，则有$\gcd(\frac{a}{r},\frac{b}{r})=1$，再令$a=rx,b=ry$，那么$(a+b)|ab$ 可以表示为$r(x+y)|r^2xy$，也就是$(x+y)|rxy$。

由于$x$与$y$互质，所以$\gcd(x+y,x)=\gcd(x+y,y)=\gcd(x,y)=1$，$(x+y)$与$x,y$也是互质的，则必然有$(x+y)|r$。

令$r=k(x+y)$，则$a=kx(x+y),b=ky(x+y)$，可以发现$a,b\le N$对应着$x,y\le\sqrt{N}$，只需要枚举不超过$\sqrt{N}$的互质数对$(x,y)$，即可计算出对应的每一组解，这样做的时间复杂度是$O(\sqrt{N}^2)=O(N)$的，其中求最大公约数的部分可以通过预处理达到$O(1)$。

注意到本题的数据组数较大，单组数据使用$O(N)$算法也会超时，但是枚举所有解的时候也确定了这组解是属于$N\ge\max(a,b)$的所有$N$，所以将这组$(a,b)$统计到对应的$\max(a,b)$，再求一遍前缀和即可得到所有答案，预处理复杂度$O(N)$，单点查询$O(1)$。

C. 抽奖箱

题意可以稍作简化，考虑成$n$次抽奖，每次只有$m$位老师和$a_i$位学生，需要求抽到$k$位老师时，在这$k$位学生之前的同学平均情况下有多少位。不同班的学生之间互相不影响。

注意到样例解释里不同情况下的概率是不一样的，不便于分析，可以将抽取的序列补全成抽完$(m+a_i)$个结果的一个排列，这样每个排列的概率都是$\frac{1}{(m+a_i)!}$。

一个直观的结论是，可以认为学生是等概率分布在老师之间的，即任意两个相邻的老师之间平均情况下有相同数量的学生，那么$m$位老师将序列划分成$(m+1)$个段，每段平均情况下有$\frac{a_i}{m+1}$个学生，所求即前$k$个段里平均情况下的学生个数，也就是$\frac{a_i\cdot k}{m+1}$。如果理解了数学期望的线性性，应该会很快得到这个结论。详细的证明可以参考超几何分布的期望。

D. 最大公约数

最大公约数满足结合律，所以题目所说相等的$\gcd$就是原数列的$\gcd$，不妨设为$d$。

设$f[i]$为前$i$个数能分的最大段数，枚举最后一个段是$[j+1,i]$，则有$\gcd_{k=j+1}^{i}{a_k}=d$，而$f[i]=max{f[j]}+1$。如果$j$不存在，可以认为$f[i]$是不合法的部分，令$f[i]=0$即可。

不难证明满足条件的$j$是一段前缀区间，而且$f[i]$是单调的，所以最大的$f[j]$一定是尽量靠右的，可以直接找到这个$j$来对$f[i]$更新答案。

区间$\gcd$可以预处理ST表得到，或者顺着推以每个点结尾的区间$\gcd$即可，可以证明以每个点结尾的区间$\gcd$的值个数是不超过$logn$个的，所以整体的复杂度是$O(n \log^2n)$。

E. 矩阵

设 $X_i$代表第$i$行所减少的权值，设 $Y_j$代表第$j$ 列所增加的权值。

则 $C_{ij} = Y_j - X_i$, 推出 $X_i + C_{ij} \leq Y_j$ 和 $Y_j - C_{ij} \leq X_i$，根据差分关系建边。原问题就变成：是否所有的环权值都为$0$。$n + m$ 只有 $100$，所以floyd和spfa找环什么的都可以过。

PS:没想到大部分人都用高斯消元过掉了。

F. 序列

对于一个固定的排列$p$，权值为 $1 + \sum_{i=1}^{n-1}[p_i > p_{i+1}]$。所以相邻两个数字，如果前面数字大于后面数字则对答案贡献$1$。

公式：$\binom{n}{2} \binom{n-1}{1} \cdot (n-2)! + n! = \frac{(n+1)!}{2}$。

G. 就是这么巧

这题的结论： 1.对于符合条件的$(a,b)$，$\frac{a^2+b^2}{ab+1}$是一个完全平方数

2.对于给定的$n,\frac{a^2+b^2}{ab+1}=n^2$的所有解是数列中的相邻两项。

证明：

令：$\frac{a^2+b^2}{ab+1}=k > 0$，$a \ge b，$并移项化简得:$a^2-kb \cdot a+b^2-k=0$。

对于给定的$k，$我们将$a,b$的范围从正整数扩大为整数。那么$a,b$不会异号（否则$a^2-kb \cdot a+b^2-k \ge a^2+k+b^2-k > 0$，矛盾)，即$ab \ge 0$。

已知a是一元二次方程$x^2-kb \cdot x+b^2-k=0$的一个解，设另一个解为$a’$，根据韦达定理:

公式$a+a’=kb$就是$A_{n-1}+A_{n+1}=kA_{n}$。

就是说任意给定一组解$(b,a)$，我们可以求出另一组解$(a’,b)$，且$a’< b \le a$，继续迭代可以得到一个无穷数列{$A_i$},$(A_i,A_{i+1})$都是解。

当$k>1$时，这个数列是递增的；并且关于原点对称，因为$(-a,-b)$也是一组是解；并且0是数列中的某一项（否则必然存在$A_i<0<A_{i+1} $）；从而对于给定的$k$，所有的解都在这个数列中。

H. 高中数学题

题目给出了一个仅含$a_n$、$S_n$的公式，根据高中数学知识，很容易解出它的通项：$a_n = 2n + 1$

我们要求的是这个序列的前$n$项异或和

对于自然数的前$n$项异或和$X_n$，有如下规律：

本题中的序列就是自然数序列左移一位，再加1得到的

因此先将自然数序列的前$n$项异或和算出，之后将其左移一位再单独考虑最后一位的情况就好了。

I. 神奇宝贝大师

首先很重要的一点，我们可以发现X方向位置的选择和Y方向位置的选择是相互独立的。如果能想到这点这题就非常非常简单了。

假设我们最后答案是(ansx, ansy)，我们只要独立的找到ansx和ansy就好了。 而只考虑X方向或者Y方向的话，就把原题转换成了一维的问题：给一个数组$a$，找一个位置$x$使得$\sum{a_i \cdot |i-x|}$最小。

而这个一维的问题就很好解决了。可以$O(n)$扫一遍维护一下前后的距离暴力统计取min，或者直接找中间位置。而这个题更加简单一些，2000的数据范围直接$O(n^2)$暴力枚举都是可以的。

J. 铅导体

这个题目的操作是在原图的每条边上加上一个$dt$，我们可以发现，最终影响答案的是每条路径的边数。我们不妨把所有从$S$到$T$的路径表示为$A+B \cdot dt$的形式，$A$代表原图该路径的长度，$B$代表该路径的边数。

而$A+B \cdot dt$是一束直线，且我们显然可以将其优化为$n$条直线(对每个$B$，取最小的$A$)。那么对于每个询问$dt$，答案就是这一束直线在$x=dt$处的最小值。我们可以处理出一个最多由$n$条边组成的下凸壳，对每个询问二分查找其所在的凸壳上的段，即可直接求出答案。

由于前面求$n$条直线的复杂度为$O(nm)$,求下凸壳的复杂度为$O(n)$,回答询问的复杂度为$O(q \log n)$,所以总的复杂度为$O(nm + q \log n)$。题目中的$nm$比较大，但是实际上在图中跑的速度还是很快的。另外，由于数据未进行特别的构造，导致暴力处理$n$条直线，并且询问时枚举$n$条直线计算最值的算法也通过了此题。

K. 危险密码

两个字符串的编辑距离即一个串通过添加、删除、修改三种操作变成另外一个串的最少操作次数。

对于一个字符串$s$，设它的长度为$n$，可以发现$h=(\sum_{i=0}^{n-1}{a_i\cdot K^{n-1-i}})\;\text{mod}\;M$，枚举添加、删除、修改的一个字符串，计算新串的$h’$即可。

对于修改第$i(0\le i<n)$个位置为$c$，$h’=h+(c-a_i)\cdot K^{n-1-i}$。

对于添加和删除需要一些额外的信息，令$pre_i$表示字符串$s$的前$i$个字符表示的$h$值，$pre_n$即$s$的$h$，再令$suf_i=pre_n-pre_i\cdot K^{n-i+1}$。

对于在第$i(0\le i\le n)$个字符前添加一个$c$，$h’=pre_i\cdot K^{n-i+1}+c\cdot K^{n-i}+suf_{i+1}$。

对于删除第$i(0\le i<n)$个字符，$h’=pre_{i-1}\cdot K^{n-i}+suf_{i+1}$。

L. 偶回文串

题意即统计有多少个连续的子串满足在它里面出现的字符都出现了偶数次，满足这样条件的子串总能通过重排字符的顺序得到一个偶回文串。

任意一个子串里某个字符的出现次数可以被表示成两个前缀字符串里出现次数的差，例如$abbababbabbab$的子串$ababba$，就可以表示成$abbababba$和$abb$的差，如果这两个前缀串里任意一个字符出现的次数在模$2$意义下是相等的，那么他们的差对应的子串就是一个合法的解。 以第$i$个字符结尾的前缀串和以第$i+1$个字符结尾的前缀串只差一个字符，可以通过线性递推得到所有的前缀串的$26$个字符出现次数的奇偶性，可以发现每个前缀串对应$26$个不是$0$就是$1$的数字，可以将其压缩成一个二进制数字$s_i$，$s_i$的第$k$位对应第$k$个字符出现次数的奇偶性，添加一个字符可以利用二进制不进位加法，其中二进制不进位加法可以用异或$(xor)$来表示。

算出所有的$s_i$之后，可以通过$\text{C++ STL map}$或手写散列函数统计相同的$s_i$出现个数，也可以直接进行排序将相同的$s_i$排到一起。不妨设有$a$个$s_i$是相等的，那么它们可以对应$\frac{a\cdot(a-1)}{2}$个子串，分别考虑每组相等的$s_i$，将贡献累加即可。时间复杂度$O(n \log n)$。

M. 我是鱼

一个数和自己异或($\oplus$)结果为0，所以如果只有一个数是奇数全部异或起来就能得到结果，如果有两个数是奇数，假设为$a$，$b$，把所有数异或起来的结果等于$a \oplus b$，设$c=a \oplus b$，则$c \not = 0$，$c$的二进制表示中必有某一位为1，假设为第$x$位，那么将所有第$x$位为$0$的异或起来，所有为$1$的异或起来就能得到$a$，$b$。