2020-2021:teams:die_java:weeksummary10
| 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:die_java:weeksummary10 [2020/08/14 15:10] fyhssgss 创建 |
2020-2021:teams:die_java:weeksummary10 [2020/08/14 16:43] (当前版本) wxg [王兴罡] |
||
|---|---|---|---|
| 行 1: | 行 1: | ||
| ====== Update on Wiki ====== | ====== Update on Wiki ====== | ||
| * 创建了本周训练周报 | * 创建了本周训练周报 | ||
| - | * 创建了暑期牛客第七次集训界面 | + | * 创建了暑期牛客第九次集训界面 |
| - | * 创建了暑期牛客第八次集训界面 | + | * 创建了暑期牛客第十次集训界面 |
| - | * 创建了暑假cf第二次集训界面 | + | |
| ---- | ---- | ||
| ====== 团队训练 ====== | ====== 团队训练 ====== | ||
| - | [[front_page_SummerTrain8|2020牛客暑期多校训练营（第七场）]] | + | [[front_page_SummerTrain11|2020牛客暑期多校训练营（第九场）]] |
| - | \\ [[front_page_SummerTrain9|2020牛客暑期多校训练营（第八场）]] | + | \\ [[front_page_SummerTrain12|2020牛客暑期多校训练营（第十场）]] |
| - | \\ [[front_page_SummerTrain10|2020-2021 BUAA ICPC Team Supplementary Training 02]] | + | |
| ---- | ---- | ||
| ====== 每周推荐 ====== | ====== 每周推荐 ====== | ||
| - | fyh:2020-2021 BUAA ICPC Team Supplementary Training 02 H.Split Game | + | fyh: |
| - | \\ 题目大意：给一个多边形，全在第一象限，有一条过原点的直线，问最多能把这个多边形划分成多少区域 | + | \\ 题目大意：给一个无向图，你要不在图中找到一个长度大于等于$\lceil \frac{n}{2} \rceil$ 的简单路径，要不就找若干个二元组（其中这些二元组的元素不能重复，至少要多于等于$\lceil \frac{n}{2} \rceil$ ），使得任意两个二元组组成的子图，至多有两条边。 |
| - | \\ tag:计算几何 | + | \\ tag:dfs树，构造 |
| - | \\ 做法:先考虑给定一条分界线怎么数区域，我的做法是先算出所有交点然后看这条线两侧有多少个山峰，便是多少个区域，我们便可以从这个思路继续拓展，继续想直线在旋转的过程中答案的增量，十分善良的是数据已经是按照逆时针转好的，注意讨论这个点前驱后继组成的形状。 | + | \\ 做法:随便找一点开始求他的dfs树，如果dfs树中有深度大于等于$\lceil \frac{n}{2} \rceil$ 的点，就直接输出即可，否则就找所有深度相同的点，两两配对，一定能保证配出$\lceil \frac{n}{4} \rceil$ 对。怎么证明呢？ |
| - | \\ comment:计算几何的细节处理 | + | 先证这任意两个二元组组成的子图吧，根据dfs树的性质，**所有非树边一定是祖先连往子孙，不可能存在子树之间的连边** ，深度相同的点显然是属于两个子树，所以保证两个二元组$(a,b),(c,d)$ 其中$deep[a]=deep[b],deep[c]=deep[d]$ 令$deep[a]<deep[c]$，a和b 不可能连边，c和d不可能连边，那两条边只可能是a和c，b和d为父子关系的时候才可以算上。 |
| + | 再证一定大于$\lceil \frac{n}{4} \rceil$ 对，因为不存在深度大于$\lceil \frac{n}{2} \rceil$ 了，所以最大深度不过$\lceil \frac{n}{2} \rceil$ ，每一个深度只有当有0个或者1个节点的时候才会放弃这个深度，根据抽屉原理一定能选出$\lceil \frac{n}{4} \rceil$ 对满足。 | ||
| + | \\ comment:虽然这题出的有点强行，但是利用dfs树的一些性质还是十分巧妙 | ||
| - | wxg: 2020-2021 BUAA ICPC Team Supplementary Training 02 E.line game | + | wxg: |
| - | \\ 题目大意：有 $n$ 条线段,端点为 $(0,i) ,(1,p_i)$ 每次可以花 $v_i$ 的价值选线段 $i$ ,把 $i$ 和 与 $i$ 相交的线段全部删了, 问删完所有线段的最小代价. | + | \\ 题目大意 给了一个度数小于10的图，问你有多少个排列${c_n}$，满足度数为 $i$ 的点就往第 $c_i$ 个边走，每个点最终都能走回自己 |
| - | \\ tag: dp，cdq分治，单调栈 | + | \\ tag: 图论，思维 |
| - | \\ 做法: 具体见周报 | + | \\ 做法: 发现给出排列的图最后都是若干个环，所以每个点入度出度都是1，我们可以用bitset判断 $c_i$ 和 $c_j$ 是否有矛盾，最后枚举排列算答案即可 |
| - | \\ comment: 非常巧妙的dp题，用到各种dp的优化方法 | + | \\ comment: 判断图是否成环的方法非常巧妙 |
| - | hxm:2020-2021 BUAA ICPC Team Supplementary Training 02 D.Forest Game | + | hxm: |
| - | \\ 题目大意：现在有一棵$n$个节点的树，每次从中删去一个点，得到这个点所在树的大小的代价。问给定一棵树随机删除的所有情况代价和 | + | \\ 题目大意：一个可重复数字集合S的神秘数定义为最小的不能被S的子集的和表示的正整数。 |
| - | \\ tag:计数，点分治，fft | + | 现给定n个正整数a[1]..a[n]，m个询问，每次询问给定一个区间l,r，求由a[l],a[l+1],…,a[r]所构成的可重复数字集合的神秘数。 |
| + | \\ tag:主席树 | ||
| \\ 做法: | \\ 做法: | ||
| - | 每一种删除方案对应一种排列 | + | 假如我们已经求出一个集合所能凑出连续数的最大区间$[1,max]$，那么此时答案为$max + 1$ |
| - | 我们考虑每个点对的贡献，每个点对中一个点对另一个点产生贡献当且仅当另一个点是这两点之间所有点中第一个删除的，那么距离为$m-1$的点对(即路径上有$m$个点)产生的代价为$2 \times C_{n}^{m}(m-1)!(n-m)!$ | + | 那么我们此时加入一个数$x$，假若$x > max + 1$，显然对答案没有影响 |
| - | 那么我们只需要计算每种距离的点对有几个 | + | 但是假若$x \le max + 1$，显然最大区间变为$[1,max + x]$，答案变为$max + x + 1$ |
| - | 使用点分治+$fft$统计 | + | |
| - | \\ comment:点分治+$fft$统计不同长度点对个数 | + | 那么我们就能得出这题的解法了 |
| + | 将区间内的数排序，一开始$ans = 0$，然后逐一将数加入集合之中， 一但出现$x > max + 1$的情况，由于是有序的，后面的数也无法更新答案，此时答案就是最优的 | ||
| + | 但是暴力排序枚举显然不行，我们可以用主席树优化 | ||
| + | 每求出一个新的区间$[1,max]$后，$[1,max + 1]$内的数都可以参与贡献，那么此时新的区间为$[1,\sum a_i]$，其中$a_i \le max + 1$ | ||
| + | 当$max$不变时算法结束 | ||
| + | 显然$max$是成倍增长的，所以复杂度为$O(nlog^2(\sum a_i))$ | ||
| + | \\ comment:贪心思路+数据结构优化 | ||
| ---- | ---- | ||
| 行 41: | 行 48: | ||
| ====== 傅云濠 ====== | ====== 傅云濠 ====== | ||
| - | 补题选拔赛第十场的H和F | + | 比赛：[[https://www.cnblogs.com/FYH-SSGSS/p/13480766.html|Codeforces Round #663 (Div. 2)]] |
| - | \\ 学习了笛卡尔树 | + | \\ 补第九场J 第十场J |
| + | 整理了树上哈希的板子 | ||
| ---- | ---- | ||
| ====== 王兴罡 ====== | ====== 王兴罡 ====== | ||
| - | 比赛：[[https://atcoder.jp/contests/abc174|atcoderAtCoder Beginner Contest 174]] | + | 补了cf664的部分题 |
| ---- | ---- | ||
| ====== 黄旭民 ====== | ====== 黄旭民 ====== | ||
| - | 比赛：[[https://atcoder.jp/contests/abc174|atcoderAtCoder Beginner Contest 174]] | + | 比赛：无 |
| - | \\ 整理：整理了点分治板子 | + | \\ 整理单纯形板子 |
2020-2021/teams/die_java/weeksummary10.1597389002.txt.gz · 最后更改: 2020/08/14 15:10 由 fyhssgss
