2020-2021:teams:alchemist:weekly_digest_11
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:alchemist:weekly_digest_11 [2020/08/21 16:49] hardict [龙鹏宇 Hardict] |
2020-2021:teams:alchemist:weekly_digest_11 [2020/08/21 17:24] (当前版本) mountvoom [肖思炀 MountVoom] |
||
|---|---|---|---|
| 行 35: | 行 35: | ||
| ==== 比赛 ==== | ==== 比赛 ==== | ||
| - | 求求来点正常cf div1 | + | 打了atcoder，rating小涨。 |
| - | + | ||
| - | 遇见类似原题的题不要被轻易影响 | + | |
| ==== 题目 ==== | ==== 题目 ==== | ||
| 行 50: | 行 48: | ||
| ===== 肖思炀 MountVoom ===== | ===== 肖思炀 MountVoom ===== | ||
| - | 该补点难题了 | + | 补题，学点新东西 |
| ====== 本周推荐 ====== | ====== 本周推荐 ====== | ||
| 行 112: | 行 110: | ||
| 整体上$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(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!}$ | ||
| - | 这里令$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!}$ | + | 这里令$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)!}$ | ||
| 将$\frac{1}{j!}$当作一个翻转(两者都可),求$\sum_{i}c_{i}i!A^{i}x^{i}$与$\sum_{i}\frac{1}{(n-i)!}x^{i}$的卷积,然后取结果$n+i$项系数即可 | 将$\frac{1}{j!}$当作一个翻转(两者都可),求$\sum_{i}c_{i}i!A^{i}x^{i}$与$\sum_{i}\frac{1}{(n-i)!}x^{i}$的卷积,然后取结果$n+i$项系数即可 | ||
| 行 122: | 行 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.1597999793.txt.gz · 最后更改: 2020/08/21 16:49 由 hardict
