差别

这里会显示出您选择的修订版和当前版本之间的差别。

--- 2020-2021:teams:running_chicken:2020_summer_week6_report [2020/08/14 13:23]
selia 创建
+++ 2020-2021:teams:running_chicken:2020_summer_week6_report [2020/08/24 00:26] (当前版本)
chenjiyuan3 [todolist（补题）]
@@ 行 1: / 行 1: @@
-======2020/08/08 -- 2020/08/14 周报======
+======2020/08/15 -- 2020/08/21 周报======
 ======团队======
-.08.08 [[.nowcodersummer9|2020牛客暑期多校训练营（第九场）]]
+.08.19 [[.hdu_2020_1|2020杭电多校第一场]]
-.08.14 [[.nowcodersummer10|2020牛客暑期多校训练营（第十场）]]
+.08.21 [[.hdu_2020_2|2020杭电多校第二场]]
 ======个人======
@@ 行 11: / 行 11: @@
 =====todolist（补题）=====
-牛客暑期多校训练营（第九场）
+牛客暑期多校训练营（第一场）CJY G XX C
-牛客暑期多校训练营（第十场）
+牛客暑期多校训练营（第二场）**Finish**
+牛客暑期多校训练营（第三场）CJY J/K ZRX I
+牛客暑期多校训练营（第四场）CJY E/**J** XX G
+牛客暑期多校训练营（第五场）CJY G/J
+牛客暑期多校训练营（第六场）CJY F XX I ZRX D
+牛客暑期多校训练营（第七场）CJY E ZRX A
+牛客暑期多校训练营（第八场）XX J ZRX B/C
+牛客暑期多校训练营（第九场）ZRX L
+牛客暑期多校训练营（第十场）CJY G XX B ZRX F
+加赛1 CJY A/E XX B/C ZRX D
+加赛2 CJY E
+ICPC北京 ZRX E (BFH)
+杭电多校第一场 CJY **E**/**J** XX **J** ZRX C
+杭电多校第二场 CJY B/D XX **H** ZRX K
-Codeforces Educational Round #670
 =====CJY=====
 ====专题====
+分拆数与五边形定理
+Polya与Burnside
 ====比赛====
+.08.15 Educational Codeforces Round 93
 ====题目====
+牛客高校赛（第八场）D
+杭电暑期高校赛 day1 E
 =====ZRX=====
 ====专题====
+dsu on tree
 ====比赛====
+.08.19 [[.hdu_2020_1|2020杭电多校第一场]]
+.08.21 [[.hdu_2020_2|2020杭电多校第二场]]
+atcoder abc 170
+topcoder round 38
+cf global round 10
 ====题目====
+牛客暑期多校训练营（第三场）I
+atcoder abc 170 F
 =====XX=====
@@ 行 36: / 行 84: @@
 ====专题====
-无
+Lyndon分解
 ====比赛====
-/08/12 codeforces  664
+无
 ====题目====
-牛客多校训练营2020第8场F/H
+杭电多校第一场 J
-牛客多校训练营2020第9场 A
+Codeforces 1393 E
-牛客多校训练营2020第10场 D
+Codeforces 1398 F
 ======本周推荐======
@@ 行 54: / 行 102: @@
 =====zrx=====
+**题意**
+hdu2020多校 第一场C
+求F[z] z<=1e10, F[j]=simga i<=j (f(i)), f(i)是i的第mid大的因子，向下取整。
+**思路**：
+e10就打表呗，要是以2e6为长度打表，最后只需要知道2e6个fi是多少即可。
+又因为mid大因子最大为1e5，所以可以暴力枚举因此，复杂度为调和级数。
+**评论**：
+e10的数据量，打表是个好思路
 =====cjy=====
+牛客多校训练营（第八场）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个串能排成按照字母序升序的方案的数量。
 **思路**：
+. （串内）排序：求对于每一个串，求删除第i个字母后的串的排序。设$nxt_{i}$为第i个字母右侧第一个与之不同的字母的位置。从左到右扫一遍，如果$s_{i} > s_{nxt_{i}}$，放到sorted序列左边，否则放到右边。
+. DP：$f_{i,j}$表示第i个串，删除第$sorted_{j}$位置的方案数。利用双指针法进行转移。
+. 判断两个串的大小：hash+二分，二分第一个不同的位置，进行比较
+[[https://codeforces.com/contest/1393/problem/E2|题目]]
+[[https://blog.csdn.net/micaudience/article/details/108036020|代码]]
+**评论**：
+根据字符串的特殊性质进行O(N)的排序。

CVBB ACM Team

用户工具

站点工具

差别

页面工具