2020-2021:teams:running_chicken:2020_summer_week6_report
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:running_chicken:2020_summer_week6_report [2020/08/21 10:06] chenjiyuan3 [比赛] |
2020-2021:teams:running_chicken:2020_summer_week6_report [2020/08/24 00:26] (当前版本) chenjiyuan3 [todolist（补题）] |
||
|---|---|---|---|
| 行 17: | 行 17: | ||
| 2020牛客暑期多校训练营（第三场）CJY J/K ZRX I | 2020牛客暑期多校训练营（第三场）CJY J/K ZRX I | ||
| - | 2020牛客暑期多校训练营（第四场）CJY E/J XX G | + | 2020牛客暑期多校训练营（第四场）CJY E/**J** XX G |
| 2020牛客暑期多校训练营（第五场）CJY G/J | 2020牛客暑期多校训练营（第五场）CJY G/J | ||
| 行 35: | 行 35: | ||
| 2020加赛2 CJY E | 2020加赛2 CJY E | ||
| - | 2015ICPC北京ZRX E (BFH) | + | 2015ICPC北京 ZRX E (BFH) |
| - | 2020杭电多校第一场 CJY **E**/J XX **J** ZRX C | + | 2020杭电多校第一场 CJY **E**/**J** XX **J** ZRX C |
| + | |||
| + | 2020杭电多校第二场 CJY B/D XX **H** ZRX K | ||
| =====CJY===== | =====CJY===== | ||
| 行 49: | 行 51: | ||
| ====题目==== | ====题目==== | ||
| - | 2015ICPC Beijing C D | + | 2020牛客高校赛（第八场）D |
| - | 2020牛客多校训练营（第九场）D H | + | 2020杭电暑期高校赛 day1 E |
| 行 58: | 行 60: | ||
| ====专题==== | ====专题==== | ||
| - | 从二分图最大匹配到二分图最优匹配 | + | dsu on tree |
| ====比赛==== | ====比赛==== | ||
| - | 2020.08.08 [[.nowcodersummer9|2020牛客暑期多校训练营（第九场）]] | + | 2020.08.19 [[.hdu_2020_1|2020杭电多校第一场]] |
| - | 2020.08.10 [[.nowcodersummer10|2020牛客暑期多校训练营（第十场）]] | + | 2020.08.21 [[.hdu_2020_2|2020杭电多校第二场]] |
| - | 2020.08.12 [[.2015BeiJing|2015ICPC北京赛区]] | + | atcoder abc 170 |
| - | atcoder abc 171 | + | topcoder round 38 |
| - | atcoder abc 172 | + | cf global round 10 |
| ====题目==== | ====题目==== | ||
| - | 2020牛客暑期多校训练营（第四场）I | + | 2020牛客暑期多校训练营（第三场）I |
| - | + | ||
| - | atcoder abc 171 F | + | |
| - | + | ||
| - | atcoder abc 172 E | + | |
| + | atcoder abc 170 F | ||
| =====XX===== | =====XX===== | ||
| 行 105: | 行 104: | ||
| **题意** | **题意** | ||
| - | atcoder abc 171 F | + | hdu2020多校 第一场C |
| - | 长度为n(<=1e6)的只有26个小写字母的串，往进再插入k个(<=1e6)个小写字母，能组成多少种不同的串。 | + | 求F[z] z<=1e10, F[j]=simga i<=j (f(i)), f(i)是i的第mid大的因子，向下取整。 |
| **思路**： | **思路**： | ||
| - | 考虑最终的串，先把n个本身的串插进去，然后要求如果有重复的话，要求本身的串插进去的必须是最后一个出现的位置。 | + | 1e10就打表呗，要是以2e6为长度打表，最后只需要知道2e6个fi是多少即可。 |
| - | 所以枚举第一个字符插到i，前面是随便填的，$26^{i-1}$,然后其他n-1个就通过一个组合数知道了方案数，至于剩下的没有被插入的位置，由于我们规定了原字符是出现的最后一个位置，所有它后面到下一个字符出现前只有25种选法，所以再乘上25的剩下位置次方即可。 | + | 又因为mid大因子最大为1e5，所以可以暴力枚举因此，复杂度为调和级数。 |
| **评论**： | **评论**： | ||
| - | 找到一个好的去重姿势 | + | 1e10的数据量，打表是个好思路 |
| =====cjy===== | =====cjy===== | ||
| - | 2020牛客多校训练营（第九场）D | + | 2020牛客多校训练营（第八场）D：Disgusting Relationship |
| **题意** | **题意** | ||
| - | 有一棵树，n个点，每一条边只能是编号在$[L_i,R_i]$内的人通过，问每个人在通过不超过$K_i$($K_i\leq1$)条自己不能通过的边所能到达的点的数量。 | + | 对于一个n元排列，我们记录其中长度为1的环有$a_1$个，长度为2的环有$a_2$个...长度为n的环有$a_n$个，记录f($a_1$,$a_2$...$a_n$)表示有多少个排列可以使环的 |
| + | |||
| + | 数量分别为以上n个数。 | ||
| + | |||
| + | 求有多少种不同的环数量情况使得f值不能被质数$p$整除，多组询问。 | ||
| + | |||
| + | $n\leq10^{18}$,$T\leq100000$,$p\leq100000$ | ||
| **思路**： | **思路**： | ||
| - | 容易想到用线段树维护加边，这样就转化成在线段树dfs，用可撤销并查集来维护连通块的一个问题。 | + | 首先我们容易想到对于一个环数量组，求出它的f是多少，简单的排列组合可以得到f=$\frac{n!}{1^{a_1}2^{a_2}.n^{a_n}{a_1!}{a_2!}.{a_n!}}$ |
| - | 当然K=0就已经完美解决了，我们发现K=1时要求的是这个连通块往外一步的点的个数，第一反应是去维护这个值，发现做不到，于是我们意识到 | + | 根据它的组合意义，可以知道它一定是一个整数，因此我们需要它分母含有$p$的数量尽可能的多。 |
| - | 要利用树的性质。 | + | 可以发现对于i，它的贡献是$i^{a_i}{a_i!}$。 |
| - | 考虑每个联通块维护除根节点向上以外的所有不属于这个连通块的一部点的数量，发现这个是可以维护的，只要维护每个连通块的最高节点就好 | + | 显然如果$t*{p^k}$产生贡献，${p^k}$能产生更多的贡献。 |
| - | 了。 | + | 如果${p^k}$产生贡献，那么${p^(k-1)}$能产生更多的贡献(k>1)。 |
| - | 再利用栈去维护修改操作就可了。 | + | 因此只剩下1和p可以产生贡献。 |
| - | **评论**： | + | 令n=mp+r，若选择了t个p产生了贡献，那么1的数量不应小于n-t*p-r。 |
| - | 可撤销并查集是一个好东西，就看你会不会用。 | + | 令分母分子p的数量一样，可以得到: |
| + | |||
| + | $\sum\lfloor\frac{m-t}{p_\alpha}\rfloor$ + $\sum\lfloor\frac{t}{p_\alpha}\rfloor$ = $\sum\lfloor\frac{m}{p_\alpha}\rfloor$ | ||
| + | |||
| + | 等价于组合数$C_{m}^{t}$不能整除p，这个用lucas定理很好解决问题，剩余不能产生贡献的部分，方案数等于分拆数，因此需要用五边形定理预处理分拆 | ||
| + | |||
| + | 数。 | ||
| + | |||
| + | **评论**： | ||
| + | 综合了很多的思想和方法，对这类题要格外珍惜！ | ||
| =====XX===== | =====XX===== | ||
2020-2021/teams/running_chicken/2020_summer_week6_report.1597975608.txt.gz · 最后更改: 2020/08/21 10:06 由 chenjiyuan3
