====== 2020.08.22-2020.08.28 周报 ======


===== 团队训练 =====

^  比赛时间  ^  比赛名称  ^
|  2020.08.23  |  [[icpc2017-shenyang-regional|The 2017 ACM-ICPC Asia Shenyang Regional Contest]]  |

===== 团队会议 =====

无


===== 个人训练 - nikkukun =====

==== 专题 ====

无

==== 比赛 ====

**2020.08.21 yukicoder contest 262**

^  题目  ^  A  ^  B  ^  C  ^  D  ^  E  ^  F  ^  G  ^
|  通过  |  √  |  √  |  √  |  ×  |  √  |     |  √  |
|  补题  |     |     |     |     |     |  √  |     |

D 是个假题，出题人连平面上 $ax^2 + by^2 + cx + dy + e = 0$ 形式的圆必然要满足 $a = b$ 都不知道就开始出假数据了。

**2020.08.21 Codeforces Round #665 (Div. 2)**

^  题目  ^  A  ^  B  ^  C  ^  D  ^  E  ^  F  ^
|  通过  |  √  |  √  |  √  |  √  |  √  |  √  |
|  补题  |     |     |     |     |     |     |

有生之年竟然能 AK 一场 CF（虽然是 Div. 2），很舒服。

**2020.08.22 AtCoder Beginner Contest 176**

^  题目  ^  A  ^  B  ^  C  ^  D  ^  E  ^  F  ^
|  通过  |  √  |  √  |  √  |  √  |  √  |     |
|  补题  |     |     |     |     |     |     |

==== 学习总结 ====

无



===== 个人训练 - qxforever =====

==== 专题 ====

==== 比赛 ====

**比赛名称**

**2020.08.22 AtCoder Beginner Contest 176**

^  题目  ^  A  ^  B  ^  C  ^  D  ^  E  ^  F  ^
|  通过  |  √  |  √  |  √  |  √  |  √  |     |
|  补题  |     |     |     |     |     |     |

==== 学习总结 ====

无



===== 个人训练 - Potassium =====

==== 专题 ====

无

==== 比赛 ====

**2020.08.22 AtCoder Beginner Contest 176**

^  题目  ^  A  ^  B  ^  C  ^  D  ^  E  ^  F  ^
|  通过  |  √  |  √  |  √  |  √  |  √  |     |
|  补题  |     |     |     |     |     |     |

==== 学习总结 ====

无






===== 本周推荐 =====

==== 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$ 的异或和。

  * **题解**：显然可以按位考虑贡献。如果我们固定了一个 $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 ====

[[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 去重，但考虑倒序字典树去重也是个值得记录的想法。
  * 
  * **备注**：无