2020-2021:teams:farmer_john:2020牛客暑期多校第二场
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:farmer_john:2020牛客暑期多校第二场 [2020/07/17 16:02] jjleo [题解] |
2020-2021:teams:farmer_john:2020牛客暑期多校第二场 [2020/07/18 18:22] (当前版本) bazoka13 [总结] |
||
|---|---|---|---|
| 行 1: | 行 1: | ||
| - | ======2020牛客暑期多效第二场====== | + | ======2020牛客暑期多校第二场====== |
| [[https://ac.nowcoder.com/acm/contest/5667|比赛链接]] | [[https://ac.nowcoder.com/acm/contest/5667|比赛链接]] | ||
| =====A.===== | =====A.===== | ||
| 行 40: | 行 40: | ||
| **upsolved by JJLeo** | **upsolved by JJLeo** | ||
| ====题意==== | ====题意==== | ||
| + | 字符串匹配。字符集为正整数，要求模式串每一位都小于等于文本串，文本串长度为$n$，模式串长度为$m$。$(1 \le n \le 150000, 1 \le m \le \min\{n, 40000\})$ | ||
| ====题解==== | ====题解==== | ||
| + | $\text{Shift-And}$算法。考虑如何构造出辅助表，即模式串的每一位能否匹配文本串的每一位。只需从小到大将两个串排序，然后从小到大扫一遍将对应的位从$0$改为$1$即可。然而这样空间复杂度为$O(\dfrac{nm}{w})$会$\text{MLE}$，事实可以发现本质只有$m$种不同的$\text{bitset}$，将每一位和每个$\text{bitset}$进行一下对应即可，空间复杂度降为$O(\dfrac{m^2}{w})$，时间复杂度为$O(\dfrac{nm}{w})$。 | ||
| =====H.===== | =====H.===== | ||
| **solved by 2sozx** | **solved by 2sozx** | ||
| 行 54: | 行 56: | ||
| **upsolved by JJLeo** | **upsolved by JJLeo** | ||
| ====题意==== | ====题意==== | ||
| + | 区间$[l,r]$可以变成$[l-1,r],[l+1,r],[l,r-1],[l,r+1]$，现在有$m$个方案可以让你花费$c$禁止掉两个不同区间之间的双向变换，求最小代价使得$[1,n]$无法变成$l=r$的区间，或判断无解。$(2 \le n \le 500, 0 \le m \le n(n-1))$ | ||
| ====题解==== | ====题解==== | ||
| + | 题目可以转化成如下的平面图，所有有限制的边长度为花费，无限制的边长度为正无穷，转对偶图求最短路即可。{{:2020-2021:teams:farmer_john:jjleo:2020now2i.png?800|}} | ||
| =====J.===== | =====J.===== | ||
| **solved by JJLeo** | **solved by JJLeo** | ||
| ====题意==== | ====题意==== | ||
| + | 给出一个目标排列$a$，长度为$n$，大质数$k$，现在求一个置换使得$1,2, \cdots ,n$经过$k$次变换成为$a$，或判断无解。$(1 \le n \le 10^5, 10^8 \le k \le 10^9)$ | ||
| ====题解==== | ====题解==== | ||
| + | 考虑把每个环单独拿出来看，设环长为$l$，$m = k \mod l$，则相当于已知每个点的前$m$个点是哪个点，依据这个将对应置换推出来即可。无解条件为$l \mod m = 0$且$m \ne 1$。 | ||
| =====K.===== | =====K.===== | ||
| **upsolved by JJLeo** | **upsolved by JJLeo** | ||
| ====题意==== | ====题意==== | ||
| + | 给出三个同心圆，三个点各自等概率地分布在三个圆上，求三点形成三角形的期望面积。保留一位小数，保证第二位小数既不是$4$也不是$5$。 | ||
| ====题解==== | ====题解==== | ||
| + | <del>最关键的后半段话没看到....</del>题目明示精度要求很低，固定一个点，双重循环将$[0,2\pi]$均匀分为$500$份，暴力枚举另外两个点的分布直接计算，计算三角形面积用叉乘取绝对值即可。 | ||
| =====记录===== | =====记录===== | ||
| + | 10min:MJX 慢人一步发现 D 题签到，AC，ZYF 冲H\\ | ||
| + | 28min:ZYF WA2 后 MJX 冲 B\\ | ||
| + | 62min:MJX WA3 T1 后和 ZYF 讨论C 后开始冲 C，CSK 接手 B\\ | ||
| + | 93min:B C 相继挂7次后 CSK冲 F\\ | ||
| + | 104min:CSK AC，继续冲B C\\ | ||
| + | 141min:ZYF AC C，之后又是漫长的思考时间\\ | ||
| + | 210min:MJX 发现 H 之前的错误情况可做，冲 H 挂了，和ZYF 冲J\\ | ||
| + | 221min:ZYF AC J\\ | ||
| + | 224min:MJX AC H,之后一起冲 B\\ | ||
| + | 250min:挂14次后终于冲破了 B，之后分别看 EG\\ | ||
| + | after:ZYF 半天补完了剩下的题，ZYF YYDS! | ||
| + | |||
| =====总结===== | =====总结===== | ||
| + | * ZYF要避免自己把自己绕晕，同时加强对学过知识的熟练程度，例如$\text{Shift-And}$和$\text{FWT}$学过却完全想不起来。 | ||
| + | * MJX要加快自己读题速度以及写签到题的速度，开始和别人差了一截。 | ||
| + | * CSK不能上头，及时调整思路，注意沟通 | ||
2020-2021/teams/farmer_john/2020牛客暑期多校第二场.1594972968.txt.gz · 最后更改: 2020/07/17 16:02 由 jjleo
