2020.08.19 2020杭电多校第一场

2020.08.21 2020杭电多校第二场

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

分拆数与五边形定理

Polya与Burnside

2020.08.15 Educational Codeforces Round 93

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

2020杭电暑期高校赛 day1 E

dsu on tree

2020.08.19 2020杭电多校第一场

2020.08.21 2020杭电多校第二场

atcoder abc 170

topcoder round 38

cf global round 10

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

atcoder abc 170 F

Lyndon分解

无

2020杭电多校第一场 J

Codeforces 1393 E

Codeforces 1398 F

题意

hdu2020多校 第一场C

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

思路：

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

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

评论：

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

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定理很好解决问题，剩余不能产生贡献的部分，方案数等于分拆数，因此需要用五边形定理预处理分拆

数。

评论：

综合了很多的思想和方法，对这类题要格外珍惜！

来源：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+二分，二分第一个不同的位置，进行比较

题目

代码

评论：

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