2020-2021:teams:alchemist:2020_nowcoder_multiuniversity_3
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:alchemist:2020_nowcoder_multiuniversity_3 [2020/07/24 10:51] hardict [D.Points Construction Problem] |
2020-2021:teams:alchemist:2020_nowcoder_multiuniversity_3 [2020/07/24 11:12] (当前版本) hardict [F. Fraction Construction Problem] |
||
|---|---|---|---|
| 行 76: | 行 76: | ||
| 由于网格很大，知道解后即可构造 | 由于网格很大，知道解后即可构造 | ||
| + | |||
| + | by Hardict | ||
| + | |||
| + | ===== E.Two Matchings ===== | ||
| + | |||
| + | cmx赛场上AC的 | ||
| + | |||
| + | 一开始发现其实题目就是一堆二元环交换问题，发现具体解和原序列顺序无关 | ||
| + | |||
| + | 排升序后，$(1,2)(3,4)...$这样即为最小解 | ||
| + | |||
| + | 但题目要求两个完全不同(每一位都不想等)置换，使和最小 | ||
| + | |||
| + | 后面发现$4|n$使，$(1,4)(2,3)$这种下去即可，$4\nmid n$使可能有六个一组的情况，而且可能不只一个 | ||
| + | |||
| + | 而$(1,4)(2,3)$和$$(1,2)(3,4)$相比可以通过简单加减转换 | ||
| + | |||
| + | 运用$dp$即可 | ||
| + | |||
| + | $dp[i] = dp[i - 4] + (a[i] - a[i - 3]) * 2$ | ||
| + | |||
| + | $dp[i] = min(dp[i], dp[i - 6] + (a[i] - a[i - 5]) * 2)$ | ||
| + | |||
| + | by Hardict | ||
| + | |||
| + | ===== F. Fraction Construction Problem ===== | ||
| + | |||
| + | 首先$d=f$即$gcd(a,b)>1$解是显然的 | ||
| + | |||
| + | $(d,f)=x,\frac{c}{d}-\frac{e}{f}=\frac{c\frac{f}{x}-e\frac{d}{x}}{\frac{df}{x}}$ | ||
| + | |||
| + | 不妨$(d,f)=1$.转换为$\frac{cf-ed}{xdf};xd,xf \leq b$ | ||
| + | |||
| + | 我们即可知道$b$的两个不同素因子p,q，然后$d=p,f=q$ | ||
| + | |||
| + | 利用$exgcd$求得$cf-ed=1$,$c$取最小正数解$c_{0}$ | ||
| + | |||
| + | 故整体解为$c=ac_{0},e=ae_{0},d=px,f=qx,x=\frac{b}{pq}$ | ||
| + | |||
| + | 而若$b$为$1$或素因子的幂是无解的 | ||
| by Hardict | by Hardict | ||
2020-2021/teams/alchemist/2020_nowcoder_multiuniversity_3.1595559086.txt.gz · 最后更改: 2020/07/24 10:51 由 hardict
