======2020/08/15 -- 2020/08/21 周报======

======团队======

2020.08.19 [[.hdu_2020_1|2020杭电多校第一场]]

2020.08.21 [[.hdu_2020_2|2020杭电多校第二场]]

======个人======

=====todolist（补题）=====

2020牛客暑期多校训练营（第一场）CJY G XX C

2020牛客暑期多校训练营（第二场）**Finish**

2020牛客暑期多校训练营（第三场）CJY J/K ZRX I

2020牛客暑期多校训练营（第四场）CJY E/**J** XX G

2020牛客暑期多校训练营（第五场）CJY G/J

2020牛客暑期多校训练营（第六场）CJY F XX I ZRX D

2020牛客暑期多校训练营（第七场）CJY E ZRX A

2020牛客暑期多校训练营（第八场）XX J ZRX B/C

2020牛客暑期多校训练营（第九场）ZRX L

2020牛客暑期多校训练营（第十场）CJY G XX B ZRX F

2020加赛1 CJY A/E XX B/C ZRX D

2020加赛2 CJY E

2015ICPC北京 ZRX E (BFH)

2020杭电多校第一场 CJY **E**/**J** XX **J** ZRX C

2020杭电多校第二场 CJY B/D XX **H** ZRX K

=====CJY=====

====专题====
分拆数与五边形定理

Polya与Burnside
====比赛====
2020.08.15 Educational Codeforces Round 93
====题目====

2020牛客高校赛（第八场）D

2020杭电暑期高校赛 day1 E


=====ZRX=====

====专题====

dsu on tree

====比赛====

2020.08.19 [[.hdu_2020_1|2020杭电多校第一场]]

2020.08.21 [[.hdu_2020_2|2020杭电多校第二场]]

atcoder abc 170

topcoder round 38

cf global round 10

====题目====

2020牛客暑期多校训练营（第三场）I

atcoder abc 170 F

=====XX=====

====专题====

Lyndon分解

====比赛====

无

====题目====

2020杭电多校第一场 J

Codeforces 1393 E

Codeforces 1398 F 

======本周推荐======

=====zrx=====

**题意**

hdu2020多校 第一场C

求F[z] z<=1e10, F[j]=simga i<=j (f(i)), f(i)是i的第mid大的因子，向下取整。

**思路**：

1e10就打表呗，要是以2e6为长度打表，最后只需要知道2e6个fi是多少即可。

又因为mid大因子最大为1e5，所以可以暴力枚举因此，复杂度为调和级数。

**评论**：

1e10的数据量，打表是个好思路

=====cjy=====

2020牛客多校训练营（第八场）D：Disgusting Relationship

**题意**

对于一个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$


**思路**：

首先我们容易想到对于一个环数量组，求出它的f是多少，简单的排列组合可以得到f=$\frac{n!}{1^{a_1}2^{a_2}.n^{a_n}{a_1!}{a_2!}.{a_n!}}$

根据它的组合意义，可以知道它一定是一个整数，因此我们需要它分母含有$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=====

====Twilight and Ancient Scroll====

来源：CF 1393 E2 

算法：**字符串排序**、**双指针**、**hash**、**二分**

**题意**：n个串，每个串删一个字符或者不删，求n个串能排成按照字母序升序的方案的数量。

**思路**：

1. （串内）排序：求对于每一个串，求删除第i个字母后的串的排序。设$nxt_{i}$为第i个字母右侧第一个与之不同的字母的位置。从左到右扫一遍，如果$s_{i} > s_{nxt_{i}}$，放到sorted序列左边，否则放到右边。

2. DP：$f_{i,j}$表示第i个串，删除第$sorted_{j}$位置的方案数。利用双指针法进行转移。

3. 判断两个串的大小：hash+二分，二分第一个不同的位置，进行比较


[[https://codeforces.com/contest/1393/problem/E2|题目]]

[[https://blog.csdn.net/micaudience/article/details/108036020|代码]]

**评论**：

根据字符串的特殊性质进行O(N)的排序。