2020-2021:teams:alchemist:2020_nowcoder_multiuniversity_3
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:alchemist:2020_nowcoder_multiuniversity_3 [2020/07/22 17:09] mountvoom [D.Points Construction Problem] |
2020-2021:teams:alchemist:2020_nowcoder_multiuniversity_3 [2020/07/24 11:12] (当前版本) hardict [F. Fraction Construction Problem] |
||
|---|---|---|---|
| 行 10: | 行 10: | ||
| ===== lpy ===== | ===== lpy ===== | ||
| + | |||
| + | 写完后最好本地多测测，避免过多罚时 | ||
| + | |||
| + | 构造题还需要加强练习 | ||
| ===== xsy ===== | ===== xsy ===== | ||
| 行 51: | 行 55: | ||
| by cmx | by cmx | ||
| + | 赛场上考虑其主要有三个基本图形：矩形，线，离散点 | ||
| + | |||
| + | 假设矩形边长为$a,b > 1$,线长为$c > 1$,离散点数为$d$ | ||
| + | |||
| + | 则有方程$2(a+b)+2c+2+4d=m,ab+c+d=n$ | ||
| + | |||
| + | 枚举$c+d$并预处理$ab$分解即可暴力求解 | ||
| + | |||
| + | 但WA了几发后发现矩形可能有一条边有缺失 | ||
| + | |||
| + | <code> | ||
| + | XXX **X | ||
| + | XXX XXX | ||
| + | XXX XXX (X表示黑点，*表示白点) | ||
| + | </code> | ||
| + | |||
| + | 这两种在周长上贡献一样，耗费点数不同 | ||
| + | |||
| + | 所以方程变为$2(a+b)+2c+2+4d=m,ab-e+c+d=n,0 \leq e < b$ | ||
| + | |||
| + | 由于网格很大，知道解后即可构造 | ||
| + | |||
| + | 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 | ||
| ===== G. Operating on a Graph ===== | ===== G. Operating on a Graph ===== | ||
2020-2021/teams/alchemist/2020_nowcoder_multiuniversity_3.1595408999.txt.gz · 最后更改: 2020/07/22 17:09 由 mountvoom
