用户工具

站点工具


2020-2021:teams:hotpot:2020nowcoder1

差别

这里会显示出您选择的修订版和当前版本之间的差别。

到此差别页面的链接

两侧同时换到之前的修订记录 前一修订版
后一修订版
前一修订版
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|)$一定能找到不同,两倍显然长于这个值所以可行
  
-====- ====+====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题
  
 =====总结===== =====总结=====
  
-  * +  * 在同一道题上花的时间稍长,应该注意让时间分配更平均
2020-2021/teams/hotpot/2020nowcoder1.1594956967.txt.gz · 最后更改: 2020/07/17 11:36 由 喝西北风