2020-2021:teams:alchemist:weekly_digest_11
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:alchemist:weekly_digest_11 [2020/08/21 14:54] maxdumbledore [比赛] |
2020-2021:teams:alchemist:weekly_digest_11 [2020/08/21 17:24] (当前版本) mountvoom [肖思炀 MountVoom] |
||
|---|---|---|---|
| 行 7: | 行 7: | ||
| ==== 专题 ==== | ==== 专题 ==== | ||
| - | 本周暂无 | + | 学习了一点计算几何 |
| ==== 比赛 ==== | ==== 比赛 ==== | ||
| 一场atcoder,一场cf global round | 一场atcoder,一场cf global round | ||
| 行 22: | 行 22: | ||
| ==== 比赛 ==== | ==== 比赛 ==== | ||
| - | 百度之星一场 | + | cf div2 |
| ==== 题目 ==== | ==== 题目 ==== | ||
| 行 35: | 行 35: | ||
| ==== 比赛 ==== | ==== 比赛 ==== | ||
| - | 求求来点正常cf div1 | + | 打了atcoder，rating小涨。 |
| - | + | ||
| - | 遇见类似原题的题不要被轻易影响 | + | |
| ==== 题目 ==== | ==== 题目 ==== | ||
| 行 50: | 行 48: | ||
| ===== 肖思炀 MountVoom ===== | ===== 肖思炀 MountVoom ===== | ||
| - | 该补点难题了 | + | 补题，学点新东西 |
| ====== 本周推荐 ====== | ====== 本周推荐 ====== | ||
| 行 57: | 行 55: | ||
| ===来源：=== | ===来源：=== | ||
| - | [[https://ac.nowcoder.com/acm/contest/5674/C|牛客2020多校训练第九场 C Groundhog and Gaming Time]] | + | [[https://codeforces.com/contest/1392/problem/F|Codeforces Global Round 10 F. Omkar and Landslide]] |
| ===标签：=== | ===标签：=== | ||
| - | 区间，动态规划，线段树 | + | 思维题 |
| ===题意：=== | ===题意：=== | ||
| - | 给出$n$个区间$[L_i,R_i]$，等概率取其中一个子集$a$，得到的贡献为$|[L_{a_1},R_{a_1}]\cap[L_{a_2},R_{a_2}]\cap...\cap[L_{a_m},R_{a_m}]|^2$，求贡献的期望值（模$998244353$意义下）。 | + | 给出一个$n(1\le n \le 10^6)$长的严格递增序列$h$，每一次找到满足所有$h_{i+1}-h_i\ge 2$的下标$i(1\le i< n)$，进行操作$h_i=h_i+1,h_{i+1}=h_{i+1}-1$，得到新的$h'$。然后再重复操作若干次，直到无法操作为止，求出最终的序列。 |
| - | $1\le n\le 5\times 10^5,0\le L_i\le R_i\le 10^9$ | ||
| ===题解：=== | ===题解：=== | ||
| - | 这里给出两个方法，一种是大家用的比较多的方法；另一种是$dp$通解，也就是不仅可以做平方贡献，随便和区间有关的贡献都可以。 | + | 题意很简单，不过感觉真是想不到。 |
| - | 问题首先转化为所有子集的贡献和。 | + | 首先发现，每一次操作$1$的转移，顺序是没有什么关系的，或者说可以看做每一次随便挑选一对可变的$h_i,h_{i+1}$进行变换（这里变换是指让两者值最多相差$1$），然后再挑选一直到不能变为止。暂时不会证明，不过手动几个例子是很容易看出来的。 |
| - | 将区间交的平方，看作是区间交里面元素两两配对的个数，进一步，是左点。那么问题就是每一对元素，要求出其被区间交覆盖的总次数。我们将所有区间按左端点从小到大排序，按顺序加入区间$i$，这样我们看每个离散化后的原子区间，被区间覆盖的次数，就是左到右不递增了。那么必包含区间$i$时，每个原子区间的每个配对右点在区间交中带来的贡献数的和，就是$（原子区间长度乘以左边的点的个数的和的两倍+原子区间长度平方）\times（2^{覆盖数}-1）$。 | + | 接下来我们安排一种变换轮次，每一次从左往右将新的$h_i$加入到轮次中来，到左边$1\sim i$序列无法变换，再加入下一个。对于每一个新加入的$h_i$，我们首先对$h_{i-1},h_i$进行一次变换，然后让序列$1\sim i-1$“消化”这个增加的$1$，接下来再变换$h_{i-1},h_i$... |
| - | 这些信息，包括次数和乘积等，可以用线段树加以维护，每一次区间更新，然后区间查询即可。 | + | 很显然，考虑$1\sim i-1$中有唯一一对相邻相等元素$h_k,h_{k+1}$，消化的过程中，会消除了这对元素，产生了一对新的$h_{k+1},h_{k+2}$；考虑没有相邻相等元素，那么消化的过程中会在最左边产生一对新的相邻相等元素。 |
| - | 第二种方法是题解的方法： | + | 通过归纳，我们知道，因为一开始是没有相邻相等元素的，所以最后的相邻相等元素不会超过$1$对。 |
| - | - 线段的交取决于最大的左端点以及最小的右端点，同时维护两个东西比较困难。 | + | 剩下的，就只用靠数学方法求解了。 |
| - | - 所以我们先按照线段左端点从大到小排序，那么排序后的线段的交取决于最小的右端点，以及第一个被选 择的线段的左端点。 | + | |
| - | - 考虑到直接维护右端点比较麻烦，所以考虑在一开始就钦定一个点 X 作为最小的右端点。 | + | |
| - | - 所有右端点大于等于 X 的线段都可以选择，反之不能选择。 | + | |
| - | - 其次被选择的线段中至少有一个线段的右端点等于 X 那么这个方案就是合法的。 | + | |
| - | + | ||
| - | 所以可以写出一个$O(n^2)$的$dp$： | + | |
| - | + | ||
| - | - $dp[i][j][0/1]$代表前$i$个线段中钦定的$X$为$j$，是/否有一个线段的右端点为$X$ | + | |
| - | - $dp[i][j][0/1]=dp[i-1][j][0/1]\ (j<L[i] \lor j>R[i])$ | + | |
| - | - $dp[i][j][0]=dp[i-1][j][0]\times 2+(j-L[i])^2,dp[i][j][1]=dp[i-1][j][1]\times 2\ (L[i]\le j<R[i])$ | + | |
| - | - $dp[i][R[i]][0]=dp[i-1][R[i]][0],dp[i][R[i]][1]=dp[i-1][R[i]][0]+dp[i-1][R[i]][1]\times 2+(R[i]-L[i])^2$ | + | |
| - | + | ||
| - | 最后使用线段树或其他数据结构就可以将该$dp$优化到$O(n\log n)$ | + | |
| ===评论：=== | ===评论：=== | ||
| - | 赛场上想的方法也是用线段树，很麻烦，第一种平方的处理很有意义。 | + | 赛场上其实想的很多，但没总结出这个最多一对的性质，其实打表已经比较明显了，以后还是注意好好观察。 |
| - | + | ||
| - | 好题，两种方法的思考都很有技巧，尤其是第二种，普适性似乎很广，当做一种套路记住好了。 | + | |
| 行 104: | 行 86: | ||
| === 来源： === | === 来源： === | ||
| - | [[http://acm.hdu.edu.cn/showproblem.php?pid=6390|HDU 6390]] | + | [[http://acm.hdu.edu.cn/showproblem.php?pid=6061|HDU 6061]] |
| === 标签： === | === 标签： === | ||
| - | 莫比乌斯反演 | + | 多项式卷积,NTT |
| === 题意： === | === 题意： === | ||
| - | $G_u(a,b)=\frac{\varphi{ab}}{\varphi{a}\varphi{b}}$ | + | 先给定一个$f(x)=\sum_{i=0}^{n}c_{i}x^{i}$,然后求解$g(x)=f(x-\sum_{i}a_{i})=\sum_{i=0}^{n}b_{i}x^{i}$ |
| - | 求解$\sum_{i=1}^{n}\sum_{j=1}^{m}G_u(i,j)$ | + | 输出$b_{i}$ |
| === 题解： === | === 题解： === | ||
| - | $gcd(a,b)=d,\varphi(ab)=\varphi(a)\varphi(b)\frac{d}{\varphi(d)}$ | + | $A=-sum{a[i]}$并取模变成求解$f(x+A)$少去正负计算 |
| + | |||
| + | 然后按$f(x+A)$每一项进行一个展开(会成一个三角表) | ||
| + | |||
| + | 目标多项式系数$b_j=\sum_{i \geq j} c_i A^{i-j} C_i^j$ | ||
| + | |||
| + | 化解后有$j!A^jb_j=\sum_{i=j}^{n} \frac{c_{i}i!A^i}{(i-j)!}$ | ||
| + | |||
| + | 整体上$g(x)=\sum_{i=0}^{n}\frac{x^{i}}{A^{i}i!}\sum_{j=0}^{n-i}\frac{c_{i+j}(i+j)!A^{i+j}}{j!}$ | ||
| - | $G_u(a,b)=\frac{gcd(a,b)}{\varphi(gcd(a,b))}$ | + | 这里令$k=n-(i+j),g(x)=\sum_{i=0}^{n}\frac{x^{i}}{A^{i}i!}\sum_{j+k=n-i}\frac{c_{n-k}(n-k)!A^{n-k}}{j!} |
| + | =\sum_{k=0}^{n}\frac{x^{k}}{A^{k}k!}\sum_{n+k=i+j}\frac{c_{i}(i)!A^{i}}{(n-j)!}$ | ||
| - | $ans=\sum_{d}\frac{d}{\varphi(d)}\sum_{a,b}[gcd(a,b)==d]$，可以看出是经典莫比乌斯反演问题 | + | 将$\frac{1}{j!}$当作一个翻转(两者都可),求$\sum_{i}c_{i}i!A^{i}x^{i}$与$\sum_{i}\frac{1}{(n-i)!}x^{i}$的卷积,然后取结果$n+i$项系数即可 |
| - | 时间比较紧，需要线性预处理$1\sim n$逆元，进一步$\sum_{a=1}^n \sum_{b=1}^m [gcd(a,b)==d]=\sum_{i=1}^\frac{n}{d}\sum_{j=1}^\frac{m}{d}[gcd(i,j)==1]$，可以整除分块进一步优化 | ||
| 行 131: | 行 121: | ||
| === 来源： === | === 来源： === | ||
| - | [[https://ac.nowcoder.com/acm/contest/5675/J|牛客第十场 J. Identical Trees]] | + | [[https://atcoder.jp/contests/abc175/tasks/abc175_d|D - Moving Piece]] |
| === 标签： === | === 标签： === | ||
| - | 树形dp，二分图最大权匹配，树哈希 | + | 枚举，贪心 |
| === 题意： === | === 题意： === | ||
| - | 给定两棵同构的树，需要找到一个对应关系使得相同的标号尽可能多。 | + | 给定步数和诸多环，求在某个环上走的最大收益。 |
| === 题解： === | === 题解： === | ||
| - | 树形dp，dp[i][j]表示把第一棵树的i结点和第2棵树的j节点对应起来所需要的最小花费。 | + | 枚举每个点作为起点然后分类讨论，如果步数不够一圈就模拟一下找一个最大值。 |
| - | 转移的时候对它们的子树做一个二分图最大权匹配即可，这样总的复杂度仍然是$O(n^3)$ | + | 如果够一圈则在模拟走一圈内的最大值和走多圈和余下步数的最大值取个最大值即可。 |
| === 评论： === | === 评论： === | ||
| - | cmx鸽鸽写的时候树哈希被卡了，需要注意 | + | 分类没有处理好WA了很多发，这种简单题也要注意细节。 |
2020-2021/teams/alchemist/weekly_digest_11.1597992843.txt.gz · 最后更改: 2020/08/21 14:54 由 maxdumbledore
