这里会显示出您选择的修订版和当前版本之间的差别。
两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
2020-2021:teams:hotpot:2020nowcoder1 [2020/07/17 11:36] 喝西北风 |
2020-2021:teams:hotpot:2020nowcoder1 [2020/07/17 15:25] (当前版本) misakatao 更新 |
||
---|---|---|---|
行 21: | 行 21: | ||
===题解=== | ===题解=== | ||
- | ====B - ==== | + | ====B - Infinite Tree==== |
===solved by -, upsolved by tyx=== | ===solved by -, upsolved by tyx=== | ||
行 36: | 行 36: | ||
显然这棵树上有很多点是不需要的,我们可以仿照建立虚树的方法,把需要的点拉出来建立一棵点数较少的树。因此我们需要知道某两个点的LCA,由于这棵树的性质,我们知道把一个点的编号除以它的最小质因数就到了它的父亲,所以对于两个点数,我们把他们分别质因数分解后把所有质因子从小到大排列,例如20和30,排列后为{2,2,5},{2,3,5},这是这一排列的最长公共后缀相乘得到的点就是他们的LCA,因为这是两个点不断向父亲移动最早可以到达的同一个点。对于本题,我们只需要对$1!,2!,3! ... m!$这几个点进行处理,当我们从$(i-1)!$进展到$i!$时,我们可以知道$i$有哪些质因子,然后我们发现$i$离他们的LCA的距离它的所有质因子个数和之前有的小于$i$最大质因子的个数,这个数量可以由树状数组查询得到,然后我们从$(i-1)!$不断向上跳,看是否需要新建一个点,之后我们在新建的树上求一个带权重心的答案即可。 | 显然这棵树上有很多点是不需要的,我们可以仿照建立虚树的方法,把需要的点拉出来建立一棵点数较少的树。因此我们需要知道某两个点的LCA,由于这棵树的性质,我们知道把一个点的编号除以它的最小质因数就到了它的父亲,所以对于两个点数,我们把他们分别质因数分解后把所有质因子从小到大排列,例如20和30,排列后为{2,2,5},{2,3,5},这是这一排列的最长公共后缀相乘得到的点就是他们的LCA,因为这是两个点不断向父亲移动最早可以到达的同一个点。对于本题,我们只需要对$1!,2!,3! ... m!$这几个点进行处理,当我们从$(i-1)!$进展到$i!$时,我们可以知道$i$有哪些质因子,然后我们发现$i$离他们的LCA的距离它的所有质因子个数和之前有的小于$i$最大质因子的个数,这个数量可以由树状数组查询得到,然后我们从$(i-1)!$不断向上跳,看是否需要新建一个点,之后我们在新建的树上求一个带权重心的答案即可。 | ||
- | |||
- | ====C - ==== | ||
- | |||
- | ===solved by === | ||
- | |||
- | ===题意=== | ||
- | |||
- | ===数据范围=== | ||
- | |||
- | ===题解=== | ||
====D - Quadratic Form==== | ====D - Quadratic Form==== | ||
行 61: | 行 51: | ||
===题解=== | ===题解=== | ||
- | 显然,取最大值的时候,有$x^TAx=1$。由拉格朗日乘子法,$x^Tb$取最值的情况要求$A(\lamda x)=b$ | + | 显然,取最大值的时候,有$x^TAx=1$。由拉格朗日乘子法,$x^Tb$取最值的情况要求$A(\lambda x)=b$ |
- | 那么有$x^Tb=\lamda x^TAx=\lamda$ | + | 那么有$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==== | ====E - Counting Spanning Trees==== | ||
行 97: | 行 89: | ||
比赛的时候猜如果两个串不同,枚举到更长的字符串两倍长度就能找到不相同,实际上结论是到长度$|a|+|b|-gcd(|a|,|b|)$一定能找到不同,两倍显然长于这个值所以可行 | 比赛的时候猜如果两个串不同,枚举到更长的字符串两倍长度就能找到不相同,实际上结论是到长度$|a|+|b|-gcd(|a|,|b|)$一定能找到不同,两倍显然长于这个值所以可行 | ||
- | ====G - ==== | + | ====H - Minimum-cost Flow==== |
- | ===solved by === | + | ===solved by gyp=== |
===题意=== | ===题意=== | ||
- | h | + | |
+ | 给定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==== | ====I - 1 or 2==== | ||
- | ===solved by lxh,written by lxh,tyx=== | + | ===solved by lxh, written by lxh,tyx=== |
===题意=== | ===题意=== | ||
行 125: | 行 125: | ||
由于这题的点的特殊性,我们可以采取对点按度数拆点,对边拆成两个点进行一般图最大匹配的方式来判断方案是否存在(也可以输出方案)。 | 由于这题的点的特殊性,我们可以采取对点按度数拆点,对边拆成两个点进行一般图最大匹配的方式来判断方案是否存在(也可以输出方案)。 | ||
- | ====J - ==== | + | ====J - Easy Integration==== |
- | ===solved by === | + | ===solved by gyp=== |
===题意=== | ===题意=== | ||
+ | |||
+ | 求$\int^1_0(x-x^2)^ndx$ | ||
===数据范围=== | ===数据范围=== | ||
+ | |||
+ | $n\le 10^6$ | ||
===思路=== | ===思路=== | ||
- | ====K - ==== | + | 分部积分可以证明,$\int^1_0x^n(1-x)^mdx=\frac m{n+1}\int^1_0 x^{n+1}(1-x)^mdx$ |
- | + | ||
- | ===solved by === | + | |
- | + | ||
- | ===题意=== | + | |
- | + | ||
- | ===数据范围=== | + | |
- | + | ||
- | ===题解=== | + | |
=====Replay===== | =====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题 |
=====总结===== | =====总结===== | ||
- | * | + | * 在同一道题上花的时间稍长,应该注意让时间分配更平均 |