2020-2021:teams:i_dont_know_png:week_summary_16
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:i_dont_know_png:week_summary_16 [2020/08/17 11:42] nikkukun add contest |
2020-2021:teams:i_dont_know_png:week_summary_16 [2020/09/01 13:13] (当前版本) nikkukun |
||
|---|---|---|---|
| 行 5: | 行 5: | ||
| ^ 比赛时间 ^ 比赛名称 ^ | ^ 比赛时间 ^ 比赛名称 ^ | ||
| - | | 2020.xx.xx | [[比赛链接 | 比赛名称]] | | + | | 2020.08.21 | [[multi2020-hdu-6|2020 Multi-University Training Contest 6]] | |
| - | + | ||
| ===== 团队会议 ===== | ===== 团队会议 ===== | ||
| + | 无 | ||
| 行 16: | 行 14: | ||
| ==== 专题 ==== | ==== 专题 ==== | ||
| + | |||
| + | 无 | ||
| ==== 比赛 ==== | ==== 比赛 ==== | ||
| 行 50: | 行 50: | ||
| ==== 学习总结 ==== | ==== 学习总结 ==== | ||
| + | 无 | ||
| 行 60: | 行 60: | ||
| ==== 比赛 ==== | ==== 比赛 ==== | ||
| - | **比赛名称** | + | **2020.08.16 Codeforces Global Round 10** |
| - | ^ 题目 ^ A ^ B ^ C ^ D ^ E ^ F ^ | + | ^ 题目 ^ A ^ B ^ C ^ D ^ E ^ F ^ G ^ H ^ I ^ |
| - | | 通过 | √ | | | | | | | + | | 通过 | √ | √ | √ | √ | √ | √ | | | | |
| - | | 补题 | | | | | | | | + | | 补题 | | | | | | | | | | |
| ==== 学习总结 ==== | ==== 学习总结 ==== | ||
| - | |||
| 行 75: | 行 74: | ||
| ==== 专题 ==== | ==== 专题 ==== | ||
| + | |||
| + | 无 | ||
| ==== 比赛 ==== | ==== 比赛 ==== | ||
| - | **比赛名称** | + | 无 |
| - | + | ||
| - | ^ 题目 ^ A ^ B ^ C ^ D ^ E ^ F ^ | + | |
| - | | 通过 | √ | | | | | | | + | |
| - | | 补题 | | | | | | | | + | |
| ==== 学习总结 ==== | ==== 学习总结 ==== | ||
| + | 无 | ||
| 行 110: | 行 107: | ||
| ==== qxforever ==== | ==== qxforever ==== | ||
| - | [[题目链接 | 题目名称]] | + | 无 |
| - | + | ||
| - | * **题意**： | + | |
| - | * **题解**： | + | |
| - | * **备注**： | + | |
| ==== Potassium ==== | ==== Potassium ==== | ||
| - | [[题目链接 | 题目名称]] | + | [[https://vjudge.net/problem/HihoCoder-1875/origin | The Kth Largest Value]] |
| - | * **题意**： | + | * **题意**：给一个有向图，定义 $(u,v)$ 是好的当且仅当 $u$ 可以通过某些路径到达 $v$。如果 $(u,v)$ 是好的，这一个偶对的权值定义为 $u\oplus v$。$q$ 次询问，每次求第 $k$ 大的好的偶对的权值。$n\le 50000,m\le 200000,q\le 10,T\le 3$。 |
| - | * **题解**： | + | * **题解**：首先显然可以用 bitset 和拓扑排序求出来所有 $u$ 能够到达的 $v$ 的集合，对每次询问，在 trie 上贪心的往下选，当当前选择 $1$ 后能够到达的点数总和 $\geq k$ 时可以选择 $1$，否则选择 $0$。故枚举每个点，求有多少个点满足能够从 $i$ 连过来且值在某区间内。这样通过求 bitset 的前缀和可以求解，但是这样的复杂度是 $O(n^2+n\log n)$ 的，预处理复杂度太大。将 bitset 分成 $block$ 块，把每块看成一个整体求前缀和，这样预处理复杂度 $O(n^2block)$，询问复杂度 $O(q\cdot 2nblock\cdot\log n)$，空间复杂度 $O(n^2block)$，$block$ 取 $40$ 的时候可以非常极限地卡过。 |
| - | * **备注**： | + | * **备注**：分块 nb |
2020-2021/teams/i_dont_know_png/week_summary_16.1597635731.txt.gz · 最后更改: 2020/08/17 11:42 由 nikkukun
