2020-2021:teams:die_java:weeksummary10
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:die_java:weeksummary10 [2020/08/14 15:27] fyhssgss [每周推荐] |
2020-2021:teams:die_java:weeksummary10 [2020/08/14 16:43] (当前版本) wxg [王兴罡] |
||
|---|---|---|---|
| 行 21: | 行 21: | ||
| wxg: | wxg: | ||
| - | \\ 题目大意： | + | \\ 题目大意 给了一个度数小于10的图，问你有多少个排列${c_n}$，满足度数为 $i$ 的点就往第 $c_i$ 个边走，每个点最终都能走回自己 |
| - | \\ tag: | + | \\ tag: 图论，思维 |
| - | \\ 做法: | + | \\ 做法: 发现给出排列的图最后都是若干个环，所以每个点入度出度都是1，我们可以用bitset判断 $c_i$ 和 $c_j$ 是否有矛盾，最后枚举排列算答案即可 |
| - | \\ comment: | + | \\ comment: 判断图是否成环的方法非常巧妙 |
| hxm: | hxm: | ||
| - | \\ 题目大意： | + | \\ 题目大意：一个可重复数字集合S的神秘数定义为最小的不能被S的子集的和表示的正整数。 |
| - | \\ tag: | + | 现给定n个正整数a[1]..a[n]，m个询问，每次询问给定一个区间l,r，求由a[l],a[l+1],…,a[r]所构成的可重复数字集合的神秘数。 |
| + | \\ tag:主席树 | ||
| \\ 做法: | \\ 做法: | ||
| - | \\ comment: | + | 假如我们已经求出一个集合所能凑出连续数的最大区间$[1,max]$，那么此时答案为$max + 1$ |
| + | 那么我们此时加入一个数$x$，假若$x > max + 1$，显然对答案没有影响 | ||
| + | 但是假若$x \le max + 1$，显然最大区间变为$[1,max + x]$，答案变为$max + x + 1$ | ||
| + | |||
| + | 那么我们就能得出这题的解法了 | ||
| + | 将区间内的数排序，一开始$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:贪心思路+数据结构优化 | ||
| ---- | ---- | ||
| 行 39: | 行 50: | ||
| 比赛：[[https://www.cnblogs.com/FYH-SSGSS/p/13480766.html|Codeforces Round #663 (Div. 2)]] | 比赛：[[https://www.cnblogs.com/FYH-SSGSS/p/13480766.html|Codeforces Round #663 (Div. 2)]] | ||
| \\ 补第九场J 第十场J | \\ 补第九场J 第十场J | ||
| + | 整理了树上哈希的板子 | ||
| ---- | ---- | ||
| ====== 王兴罡 ====== | ====== 王兴罡 ====== | ||
| - | + | 补了cf664的部分题 | |
| ---- | ---- | ||
| ====== 黄旭民 ====== | ====== 黄旭民 ====== | ||
| - | + | 比赛：无 | |
| + | \\ 整理单纯形板子 | ||
2020-2021/teams/die_java/weeksummary10.1597390051.txt.gz · 最后更改: 2020/08/14 15:27 由 fyhssgss
