2020-2021:teams:farmer_john:2020牛客暑期多校第五场
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:farmer_john:2020牛客暑期多校第五场 [2020/07/31 14:46] jjleo [题意] |
2020-2021:teams:farmer_john:2020牛客暑期多校第五场 [2020/10/07 21:24] (当前版本) jjleo |
||
|---|---|---|---|
| 行 1: | 行 1: | ||
| - | ======比赛名称====== | + | ======2020牛客暑期多校第五场====== |
| [[https://ac.nowcoder.com/acm/contest/5670|比赛链接]] | [[https://ac.nowcoder.com/acm/contest/5670|比赛链接]] | ||
| =====A.===== | =====A.===== | ||
| 行 29: | 行 29: | ||
| 可以发现第二种操作相当于进行循环同构，因此连续的第一种操作等价于将某个元素放到任意一个位置。因此只需要找所有循环同构中找一个最长上升子序列，调整其它数字位置即可。 | 可以发现第二种操作相当于进行循环同构，因此连续的第一种操作等价于将某个元素放到任意一个位置。因此只需要找所有循环同构中找一个最长上升子序列，调整其它数字位置即可。 | ||
| =====E.===== | =====E.===== | ||
| - | **upsolved by** | + | **solved by Bazoka13** |
| ====题意==== | ====题意==== | ||
| + | 给定一个排序，每次将第$i$位数字移动到$b[i]$位，问有几种数列按照该方法进行足够多次可以完成排序。 | ||
| ====题解==== | ====题解==== | ||
| + | 求所有循环节结点数的$lcm$即可，注意高精，python除法用$//$ | ||
| =====F.===== | =====F.===== | ||
| - | **solved by ** | + | **solved by Bazoka13** |
| ====题意==== | ====题意==== | ||
| ====题解==== | ====题解==== | ||
| + | 按照题意模拟的水题，不过题面描述貌似不太通顺导致卡到10min才过 | ||
| =====G.===== | =====G.===== | ||
| **upsolved by JJLeo** | **upsolved by JJLeo** | ||
| ====题意==== | ====题意==== | ||
| 给定一棵有根树，每个点有一个颜色$c_i$，每个点可以取一个权值$d_i$，设以其为根的子树中颜色为$d_i$的点的数量为$x$，则该点权值为$xd_i$。现在问所有点权值组成集合的$\operatorname{mex}$最大为多少。$(n \le 20000)$ | 给定一棵有根树，每个点有一个颜色$c_i$，每个点可以取一个权值$d_i$，设以其为根的子树中颜色为$d_i$的点的数量为$x$，则该点权值为$xd_i$。现在问所有点权值组成集合的$\operatorname{mex}$最大为多少。$(n \le 20000)$ | ||
| - | 本题时限8s。 | + | |
| + | 本题时限8s，空间64MB。 | ||
| ====题解==== | ====题解==== | ||
| - | 因此 | + | 时限很大，因此直接$O(n^2)$找每个点可能的权值（直接dfs一次记录dfn序常数更小），然后二分图跑最大匹配。但是本题卡空间，所以拿bitset存边，然后用增广路算法跑，虽然复杂度是$O(n^3)$的但是跑不满可以卡过。 |
| =====H.===== | =====H.===== | ||
| **upsolved by JJLeo** | **upsolved by JJLeo** | ||
| ====题意==== | ====题意==== | ||
| + | 给出一个长度为$n$的序列，$q$次询问一个区间所有子区间$AND$值所组成集合的大小，强制在线。$(n,q \le 10^5)$ | ||
| ====题解==== | ====题解==== | ||
| + | 固定右端点，有可能的取值为$O(\log n)$种，因此我们可以从左到右，固定右端点，将$a_i$与右端点为$i-1$的所有值进行$AND$操作，得到所有可能的取值及其左端点的范围，这一部分总复杂度为$O(n \log n)$。接下来以每个点为右端点为根，建立主席树，对于$[l,r],[l+1,r],\cdots , [L,r]$均为某一个值$x$，直接在$r$为根对应的线段树上给$l$位置加一即可。考虑去重：如果相同的数上一次加一的位置若$< l$，则在老的位置减一即可，否则不做加一操作，直接用上次的值即可。 | ||
| =====I.===== | =====I.===== | ||
| **solved by 2sozx** | **solved by 2sozx** | ||
| 行 65: | 行 67: | ||
| **upsolved by JJLeo** | **upsolved by JJLeo** | ||
| ====题意==== | ====题意==== | ||
| + | 合并一个代码的两个分支使得总代码行数最短，代码中有的部分是分支1，有的部分是分支2，还有公用的部分。要求两个分支合并后代码执行顺序要和合并前相同，且只有完全相同的行才可以放在公共部分，否则必须出现在#ifdef branch1 和 #ifdef branch的代码块内，当然也可以用#else 和 #endif。 | ||
| ====题解==== | ====题解==== | ||
| + | 设$f_{i,j,k}$表示此时到分支1的第$i$行，分支2的第$j$行，此时处于分支1/分支2/公用的代码块内。限定分支1可以到分支2，分支2不能切到分支1，且只有两行完全一致才能在共用代码块，具体行数变化分类讨论一下即可。另外要给每个转移标个号最后逆序记录方案输出。 | ||
| =====记录===== | =====记录===== | ||
| 0min：开局分题\\ | 0min：开局分题\\ | ||
| 行 79: | 行 82: | ||
| =====总结===== | =====总结===== | ||
| * MJX：熟悉熟悉Python，别犯低级错误 | * MJX：熟悉熟悉Python，别犯低级错误 | ||
| + | * ZYF：前期梦游，昏昏欲睡。最后一个多小时K题完全理解错题意，被之前某括号匹配误导，难受。 | ||
| + | * CSK：熟悉熟悉python+1，白给一发才发现除号错误，甚至跑去用java白给了一发 | ||
2020-2021/teams/farmer_john/2020牛客暑期多校第五场.1596177994.txt.gz · 最后更改: 2020/07/31 14:46 由 jjleo
