2020-2021:teams:farmer_john:week_18
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:farmer_john:week_18 [2020/09/04 15:26] jjleo [JJLeo] |
2020-2021:teams:farmer_john:week_18 [2020/09/04 17:53] (当前版本) jjleo [JJLeo] |
||
|---|---|---|---|
| 行 16: | 行 16: | ||
| * comment：写的太容易出bug了，写完感觉神清气爽 | * comment：写的太容易出bug了，写完感觉神清气爽 | ||
| ====Bazoka13==== | ====Bazoka13==== | ||
| - | ===题目名称=== | + | ===Codeforces 1381E=== |
| - | * 分类： | + | * 分类：计算几何 |
| - | * 题意： | + | * 题意：给定一个二维坐标系里的简单多边形，$q$ 组询问，每次给定一条垂直于 $x$ 轴的直线，求出根据这条直线翻折多边形后的面积 |
| * 题解： | * 题解： | ||
| - | * comment： | + | * 考虑一维线段的翻折，即总长度减去位于翻折线左侧和中点左侧的长度，加上位于翻折线左侧中点右侧的长度 |
| + | |||
| + | * 一维的做法可以利用微分的思想拓展到二维平面，对于每个端点找出水平线段，根据中点的连线将多边形分成左右两部分，之后扫一遍求积分即可 | ||
| + | |||
| + | * comment：微分依然停留在能看懂，做不出的阶段啊QAQ | ||
| ====JJLeo=== | ====JJLeo=== | ||
| ===CF1396E Distance Matching=== | ===CF1396E Distance Matching=== | ||
| 行 30: | 行 34: | ||
| * 题意：给你一棵$n$个节点的树，保证$n$为偶数，边权为$1$，问是否存在一个完美匹配，使得两两点之间距离之和恰好等于$k$。$(n \le 10^5, k \le n^2)$ | * 题意：给你一棵$n$个节点的树，保证$n$为偶数，边权为$1$，问是否存在一个完美匹配，使得两两点之间距离之和恰好等于$k$。$(n \le 10^5, k \le n^2)$ | ||
| - | * 题解：我们考虑一条边，它将整棵树分为两部棵子树，大小分别为$x$和$n-x$，两者奇偶性相同。所有两点位于两侧的匹配都会经过这条边，而其它匹配一定是在各自子树内完成的，因此这条边被经过的次数的奇偶性一定和$x$相同，同时也有一个显然的上界$\min(x,n-x)$，设该边贡献的权值为$a$，则有$(x \mod 2 )\le a \le \min(x, n - x)$。 | + | * 题解：我们考虑一条边，它将整棵树分为两棵子树，大小分别为$x$和$n-x$，两者奇偶性相同。所有两点位于两侧的匹配都会经过这条边，而其它匹配一定是在各自子树内完成的，因此这条边被经过的次数的奇偶性一定和$x$相同，同时也有一个显然的上界$\min(x,n-x)$，设该边贡献的权值为$a$，则有$(x \mod 2 )\le a \le \min(x, n - x)$。 |
| * 我们以树的重心为根，那么除了根节点外，以每个节点为根的子树都小于另一部分，即$\min(x,n-x)=x$，因此对于每一条边我们可以得到公式$\sum (siz_i\mod 2) \le k \le \sum siz_i$，且$k$的奇偶性和$\sum siz_i$相同。下面通过构造证明这个必要条件也是充分的。 | * 我们以树的重心为根，那么除了根节点外，以每个节点为根的子树都小于另一部分，即$\min(x,n-x)=x$，因此对于每一条边我们可以得到公式$\sum (siz_i\mod 2) \le k \le \sum siz_i$，且$k$的奇偶性和$\sum siz_i$相同。下面通过构造证明这个必要条件也是充分的。 | ||
| 行 41: | 行 45: | ||
| * comment：完美利用了树的重心性质。 | * comment：完美利用了树的重心性质。 | ||
| + | |||
| + | ===CF1400G Mercenaries=== | ||
| + | * 分类：组合数学，容斥。 | ||
| + | |||
| + | * 题意：$n$个人，选出一个非空子集，第$i$个人要求如果他被选出来那么子集的大小必须在$[l_i,r_i]$，同时有$m$个限制，形如第$a_i$个人和第$b_i$个人不能同时被选，问合法的选择方案数量，对$998244353$取模。$(1 \le n \le 3 \cdot 10^5, 0 \le m \le \min(20, \dfrac{n(n-1)}{2}))$ | ||
| + | |||
| + | * 题解：如果没有第二个限制，只需要对所有区间差分一下然后枚举人数就完成了。因此我们考虑使用容斥进行计算违反了第二个限制的方案并将其减去。设$f_{S}$为至少包含状态$S$中的矛盾的方案数，其中$S$是一个二进制数，最终答案即为$$\sum_{S=0}^{2^m-1}(-1)^{\operatorname{popcount}(S)}f_S$$我们设不考虑第二个限制，允许自己所在队伍有$i$个人的数量为$c_i$；状态为$S$时所包含的人数为$cnt_S$，他们的区间交集为$[L_S,R_S]$那么有$$f_S=\sum_{i=L_S}^{R_S}\binom{n-cnt_S}{i}$$其中$cnt_S$不超过$2$m，因此我们在$O(nm)$的时间内预处理出$$g_{i,j}=\binom{n-i}{j}$$的前缀和，从而$O(1)$得到$f_S$。最后用总方案数减去不合法方案数即可，总时间复杂度为$O(nm+m2^m)$。 | ||
| + | |||
| + | * comment：非常巧妙地在第一个限制的基础上套用容斥解决了第二个限制。 | ||
| + | |||
| + | ===CF1394D Boboniu and Jianghu=== | ||
| + | * 分类：树形dp。 | ||
| + | |||
| + | * 题意：给定一棵$n$个节点的树，每个节点有两个权值$a_i,b_i$，要求将树分为数条互不相交的链，每条边都必须被划分，点可以重复，且每条链的$a_i$单调（非严格单增或单减），求所有链的$b_i$之和的最小值。$(n \le 2 \times 10^5)$ | ||
| + | |||
| + | * 题解：先考虑所有边都各自成一条链，然后再对边进行合并从而减少答案。考虑给边进行定向，由$a_i$小的点指向大的点；如果两个点$a_i$相同那么边的方向任意，需要在后续dp过程中进行讨论。设$f_i$为以$i$为根的子树中若$i$与它父亲的边向下所能减少的最大权值，$g_i$为以$i$为根的子树中若$i$与它父亲的边向上所能减少的最大权值，$S_i$为节点$i$的子节点集合，那么有$$f_i=\max_{S\in S_i}(\sum_{j\in S}f_j+\sum_{j \notin S \operatorname{and} j \in S_i}g_j+ b_i \cdot \min(|S|,|S_i|-|S|+1))$$ $$g_i=\max_{S\in S_i}(\sum_{j\in S}f_j+\sum_{j \notin S \operatorname{and} j \in S_i}g_j+ b_i \cdot \min(|S|+1,|S_i|-|S|))$$ 前面的式子不好处理，我们可以化简得到$$\sum_{j\in S}f_j+\sum_{j \notin S \operatorname{and} j \in S_i}g_j=\sum_{j\in S_i}g_j + \sum_{j \in S}(f_j-g_j)$$ 前者为定值，我们可以将子节点的$f_j-g_j$从大到小排序，设为$sum_i$，同时设$cnt_i$为节点$i$的子节点数，则有$$f_i=\sum_{j\in S_i}g_j+max_{j=0}^{cnt_i}(sum_j+b_i \cdot \min(j,cnt_i-j+1))$$ $$g_i=\sum_{j\in S_i}g_j+max_{j=0}^{cnt_i}(sum_j+b_i \cdot \min(j+1,cnt_i-j))$$ 最后根节点的答案特判一下，即为$$root_i=\sum_{j\in S_i}g_j+max_{j=0}^{cnt_i}(sum_j+b_i \cdot \min(j,cnt_i-j))$$时间复杂度$O(n \log n)$。 | ||
| + | |||
| + | * comment：巧妙的链匹配，回忆并理解了牛客dls那场的树上边覆盖。 | ||
| =====个人训练===== | =====个人训练===== | ||
| ===== 2sozx ===== | ===== 2sozx ===== | ||
| 行 50: | 行 72: | ||
| ===== Bazoka13 ===== | ===== Bazoka13 ===== | ||
| ==== 比赛 ==== | ==== 比赛 ==== | ||
| + | * [[.bazoka13:codeforces_666_div1|codeforces 666 div1]] | ||
| ====题目==== | ====题目==== | ||
| ===== JJLeo ===== | ===== JJLeo ===== | ||
| 行 56: | 行 78: | ||
| ==== 题目 ==== | ==== 题目 ==== | ||
| + | 见团队训练。 | ||
2020-2021/teams/farmer_john/week_18.1599204360.txt.gz · 最后更改: 2020/09/04 15:26 由 jjleo
