=====比赛信息===== * **日期：2020.7.12** * **比赛地址：** [[https://ac.nowcoder.com/acm/contest/5666#rank|传送门]] * **做题情况：lxh(I)，tyx(F)，gyp(HJ)** =====题解===== ====A - ==== ===solved by === ===written by === ===题意=== ===数据范围=== ===题解=== ====B - Infinite Tree==== ===solved by -, upsolved by tyx=== ===题意=== 有一棵有无限个节点的树，这棵树的根节点是1，每个数$x$的父亲是$\frac{x}{f(x)}$，其中$f(x)$是$x$最小的质因数，现在给出$m$，对于$1!,2!,3! ... m!$这$m$个点，每个点有一个权值$w_i$，现在要求在树上选一个点$p$，最小化$\sum_{i=1}^m w_i \times dis(p, i!)$，其中$dis$为两点距离，每条边长度为1 ===数据范围=== 多组数据，$1 \le m \le 10^5$，$0 \le w_i \le 10^4$，$\sum m \le 10^6$ ===题解=== 显然这棵树上有很多点是不需要的，我们可以仿照建立虚树的方法，把需要的点拉出来建立一棵点数较少的树。因此我们需要知道某两个点的LCA，由于这棵树的性质，我们知道把一个点的编号除以它的最小质因数就到了它的父亲，所以对于两个点数，我们把他们分别质因数分解后把所有质因子从小到大排列，例如20和30，排列后为{2,2,5},{2,3,5}，这是这一排列的最长公共后缀相乘得到的点就是他们的LCA，因为这是两个点不断向父亲移动最早可以到达的同一个点。对于本题，我们只需要对$1!,2!,3! ... m!$这几个点进行处理，当我们从$(i-1)!$进展到$i!$时，我们可以知道$i$有哪些质因子，然后我们发现$i$离他们的LCA的距离它的所有质因子个数和之前有的小于$i$最大质因子的个数，这个数量可以由树状数组查询得到，然后我们从$(i-1)!$不断向上跳，看是否需要新建一个点，之后我们在新建的树上求一个带权重心的答案即可。 ====D - Quadratic Form==== ===solved by -, upsolved by gyp=== ===题意=== 给定n阶正定方阵A和n维向量b，求向量x使得$x^TAx\le 1$，且$x^Tb$最大。求$(x^Tb)^2$ ===数据范围=== $n\le200$ ===题解=== 显然，取最大值的时候，有$x^TAx=1$。由拉格朗日乘子法，$x^Tb$取最值的情况要求$A(\lambda x)=b$ 那么有$x^Tb=\lambda x^TAx=\lambda$，$(x^Tb)^2=\lambda x^Tb=(\lambda x)^Tb=b^TA^{-1}b$ 所以只需要求$b^TA^{-1}b$，用高斯消元即可。 ====E - Counting Spanning Trees==== ===solved by -, upsolved by tyx=== ===题意=== 给出一个二分图，两侧分别有$x$和$y$个点，现在对于左侧点$i(1 \le i \le x)$，它与右侧的点1到点$a_i$有连边，问这个二分图的生成树有多少个，答案对$mod$取模 ===数据范围=== $1 \le x,y \le 10^5$, $1 \le mod \le 10^9$，$1 \le a_i \le y$ ===题解=== 结论题，答案是两边的点的度数全部相乘再除以两侧分别的最大值，可以利用前缀和求出右侧点的度数，然后两侧分别排序后相乘即可。结论证明没太看懂，在[[https://arxiv.org/pdf/0706.2918.pdf|这里]]可以看 ====F - Infinite String Comparision==== ===solved by tyx=== ===题意=== 给出两个无限长字符串的循环节$a,b$，问两个字符串是否相同，例如$a=zzz$，$b=zzzz$，由于两个字符串无限循环后相同所以判定为相同 ===数据范围=== $1 \le |a|,|b| \le 10^5$，输入字符串总长度不超过$2 \times 10^6$ ===题解=== 比赛的时候猜如果两个串不同，枚举到更长的字符串两倍长度就能找到不相同，实际上结论是到长度$|a|+|b|-gcd(|a|,|b|)$一定能找到不同，两倍显然长于这个值所以可行 ====H - Minimum-cost Flow==== ===solved by gyp=== ===题意=== 给定n个点，m条边的无向图，每条边有一个花费。q组询问，每组包含一个真分数表示每天边的流量上限。求从1到n，流量为1的最小费用 ===数据范围=== $n\le 50，m\le 100，q\le 10^5，\sum m\le 10^4，\sum q\le 10^6$ ===题解=== 设每条边流量上限是1，求出流量为i（$i\le m$）的最小费用c[i]，只需用费用流。 然后对每个分数，O(1)即可求得答案 ====I - 1 or 2==== ===solved by lxh, written by lxh,tyx=== ===题意=== 给出一些点极其度数，还有一些无向边，问能否有一种选边的方案，满足每个点的度数（1或2）。 ===数据范围=== 点数 $1 \le n \le 50$ 边数 $1 \le m \le 100$ ===题解=== 由于这题的点的特殊性，我们可以采取对点按度数拆点，对边拆成两个点进行一般图最大匹配的方式来判断方案是否存在（也可以输出方案）。 ====J - Easy Integration==== ===solved by gyp=== ===题意=== 求$\int^1_0(x-x^2)^ndx$ ===数据范围=== $n\le 10^6$ ===思路=== 分部积分可以证明，$\int^1_0x^n(1-x)^mdx=\frac m{n+1}\int^1_0 x^{n+1}(1-x)^mdx$ =====Replay===== 第一小时：tyx和lxh开始想A但是没有什么想法，gyp开始写J，tyx发现F通过的人数很多于是A了F，gyp的J题通过 第二小时：tyx开始想I，gyp和lxh开始想H，但是都没有什么想法 第三小时：gyp和lxh发现H题的性质于是通过了H，tyx开始想B但是没有想出 第四小时：lxh重新开始想A但是依然没有想法，三个人开始想I并想出了一种做法，但是答案错误 第五小时：三个人发现刚刚相处的做法有问题，又重新想了一种做法最后在快结束的时候通过了I题 =====总结===== * 在同一道题上花的时间稍长，应该注意让时间分配更平均