2020-2021:teams:running_chicken:2020_summer_week6_report
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:running_chicken:2020_summer_week6_report [2020/08/21 10:39] chenjiyuan3 [cjy] |
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===== | ||
| 行 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-2021/teams/running_chicken/2020_summer_week6_report.1597977584.txt.gz · 最后更改: 2020/08/21 10:39 由 chenjiyuan3
