2020-2021:teams:i_dont_know_png:week_summary_17
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:i_dont_know_png:week_summary_17 [2020/08/23 22:20] nikkukun [比赛] |
2020-2021:teams:i_dont_know_png:week_summary_17 [2020/09/01 13:13] (当前版本) nikkukun |
||
|---|---|---|---|
| 行 5: | 行 5: | ||
| ^ 比赛时间 ^ 比赛名称 ^ | ^ 比赛时间 ^ 比赛名称 ^ | ||
| - | | 2020.xx.xx | [[比赛链接 | 比赛名称]] | | + | | 2020.08.23 | [[icpc2017-shenyang-regional|The 2017 ACM-ICPC Asia Shenyang Regional Contest]] | |
| ===== 团队会议 ===== | ===== 团队会议 ===== | ||
| 行 16: | 行 15: | ||
| ==== 专题 ==== | ==== 专题 ==== | ||
| + | |||
| + | 无 | ||
| ==== 比赛 ==== | ==== 比赛 ==== | ||
| 行 43: | 行 44: | ||
| ==== 学习总结 ==== | ==== 学习总结 ==== | ||
| + | 无 | ||
| 行 54: | 行 55: | ||
| **比赛名称** | **比赛名称** | ||
| + | |||
| + | **2020.08.22 AtCoder Beginner Contest 176** | ||
| ^ 题目 ^ A ^ B ^ C ^ D ^ E ^ F ^ | ^ 题目 ^ A ^ B ^ C ^ D ^ E ^ F ^ | ||
| - | | 通过 | √ | | | | | | | + | | 通过 | √ | √ | √ | √ | √ | | |
| | 补题 | | | | | | | | | 补题 | | | | | | | | ||
| ==== 学习总结 ==== | ==== 学习总结 ==== | ||
| + | 无 | ||
| 行 68: | 行 71: | ||
| ==== 专题 ==== | ==== 专题 ==== | ||
| + | |||
| + | 无 | ||
| ==== 比赛 ==== | ==== 比赛 ==== | ||
| - | **比赛名称** | + | **2020.08.22 AtCoder Beginner Contest 176** |
| ^ 题目 ^ A ^ B ^ C ^ D ^ E ^ F ^ | ^ 题目 ^ A ^ B ^ C ^ D ^ E ^ F ^ | ||
| - | | 通过 | √ | | | | | | | + | | 通过 | √ | √ | √ | √ | √ | | |
| | 补题 | | | | | | | | | 补题 | | | | | | | | ||
| ==== 学习总结 ==== | ==== 学习总结 ==== | ||
| + | 无 | ||
| 行 90: | 行 95: | ||
| ==== nikkukun ==== | ==== nikkukun ==== | ||
| - | [[题目链接 | 题目名称]] | + | [[https://atcoder.jp/contests/arc092/tasks/arc092_b|ARC092D - Two Sequences]] |
| - | * **题意**： | + | * **题意**：给定两个长度为 $n \leq 2 \times 10^5$ 的序列 $a, b$，元素都在 $[0, 2^{28})$，求所有 $n^2$ 个 $a_i + b_j$ 的异或和。 |
| - | * **题解**： | + | |
| - | * **备注**： | + | |
| - | ==== qxforever ==== | + | * **题解**：显然可以按位考虑贡献。如果我们固定了一个 $a$ 和二进制中的某一位 $k$，相当于考虑有多少个 $b_i$，满足 $a + b_i$ 的第 $k$ 位是 $1$。这个东西就很好玩了：如果给所有 $a + b_i$ 模 $2 \cdot 2 ^{k-1}$，则余数落在 $[2^{k-1},\ 2 \cdot 2^{k-1})$ 之间的数都是满足要求的。 |
| - | [[题目链接 | 题目名称]] | + | * **备注**：归纳一下，二进制表示中 $x$ 的第 $k$ 位为 $1$ 的充要条件是，$x \in [2^{k-1},\ 2 \cdot 2^{k-1}) \pmod {2 \cdot 2 ^{k-1}}$。这个性质可以用来统计加减法操作中的位运算结果。 |
| - | * **题意**： | + | ==== qxforever ==== |
| - | * **题解**： | + | |
| - | * **备注**： | + | 无 |
| ==== Potassium ==== | ==== Potassium ==== | ||
| - | [[题目链接 | 题目名称]] | + | [[https://codeforces.com/problemset/problem/1129/C | CF1129C Morse Code]] |
| - | * **题意**： | + | * **题意**：用 1 到 4 位二进制数表示 26 个英文字母，其中 0011,0101,1110,1111 没有对应的英文字母。给定一个 01 串，求每一个前缀包含的所有本质不同的字母串个数。 |
| - | * **题解**： | + | * |
| - | * **备注**： | + | * **题解**：需要离线处理枚举前缀的结尾。从前缀的结尾 i 往前递推，设 dp[j] 表示 j 之后的字母串种类个数，num 记录最多能向后延伸几位，则有 $dp[j]=\sum_{k=1}^{num}dp[j+k]$，也就是 $[j,j+k−1]$ 表示的一个字母和 $[j+k,i]$ 表示的一段字母串连成一个更大的字母串。考虑去重，直接倒序字典树即可。网上题解大部分使用 SAM 去重，但考虑倒序字典树去重也是个值得记录的想法。 |
| + | * | ||
| + | * **备注**：无 | ||
2020-2021/teams/i_dont_know_png/week_summary_17.1598192408.txt.gz · 最后更改: 2020/08/23 22:20 由 nikkukun
