Warning: session_start(): open(/tmp/sess_aedc2f1e7eda00c9db01e32b1419c33a, O_RDWR) failed: No space left on device (28) in /data/wiki/inc/init.php on line 239
Warning: session_start(): Failed to read session data: files (path: ) in /data/wiki/inc/init.php on line 239
Warning: Cannot modify header information - headers already sent by (output started at /data/wiki/inc/init.php:239) in /data/wiki/inc/auth.php on line 430
Writing /data/wiki/data/cache/6/6a0f3843c5ea426c08feea4e44f84973.captchaip failed
Warning: Cannot modify header information - headers already sent by (output started at /data/wiki/inc/init.php:239) in /data/wiki/inc/Action/Export.php on line 103
Warning: Cannot modify header information - headers already sent by (output started at /data/wiki/inc/init.php:239) in /data/wiki/inc/Action/Export.php on line 103
Warning: Cannot modify header information - headers already sent by (output started at /data/wiki/inc/init.php:239) in /data/wiki/inc/Action/Export.php on line 103
====== 2020.08.01-2020.08.07 周报 ======
===== 团队训练 =====
^ 比赛时间 ^ 比赛名称 ^
| 2020.08.01 | [[multi2020-nowcoder-7 | 2020 Nowcoder Multi-University Training Contest 7]] |
| 2020.08.03 | [[multi2020-nowcoder-8 | 2020 Nowcoder Multi-University Training Contest 8]] |
| 2020.08.06 | [[ntuwftrial-2016 | 2016-2017 National Taiwan University World Final Team Selection Contest]] |
===== 团队会议 =====
无
===== 个人训练 - nikkukun =====
==== 专题 ====
无
==== 比赛 ====
**2020.07.31 yukicoder contest 259**
^ 题目 ^ A ^ B ^ C ^ D ^ E ^ F ^ G ^
| 通过 | √ | √ | √ | √ | | | |
| 补题 | | | | | √ | √ | |
**2020.08.02 AtCoder Beginner Contest 174**
^ 题目 ^ A ^ B ^ C ^ D ^ E ^ F ^
| 通过 | √ | √ | √ | √ | √ | √ |
| 补题 | | | | | | |
==== 学习总结 ====
2020.08.07 [[.:nikkukun:pruefer-sequences| Prufer 序列]]
2020.08.07 [[.:nikkukun:generating-function | 生成函数]]
===== 个人训练 - qxforever =====
==== 专题 ====
无
==== 比赛 ====
**2020.08.02 AtCoder Beginner Contest 174**
^ 题目 ^ A ^ B ^ C ^ D ^ E ^ F ^
| 通过 | √ | √ | √ | √ | √ | √ |
| 补题 | | | | | | |
**2020.08.07 Codeforces Global Round 5**
^ 题目 ^ A ^ B ^ C1 ^ C2 ^ D ^ E ^ F ^
| 通过 | √ | √ | √ | √ | √ | | |
| 补题 | | | | | | | |
==== 学习总结 ====
无
===== 个人训练 - Potassium =====
==== 专题 ====
无
==== 比赛 ====
无
==== 学习总结 ====
s1.swap(s2)
===== 本周推荐 =====
==== nikkukun ====
[[https://yukicoder.me/problems/no/1143 | yukicoder contest 259 E - 面積Nの三角形]]
* **题意**：给定 $n \leq 10^6$，求有多少个边长是整数且均大于 $1$ 的三角形面积为 $n$。
* **题解**：考虑海伦公式 $S = \sqrt {p (p-a)(p-b)(p-c)}$，其中 $p = \dfrac {a + b + c}2$。做代换 $\begin{cases} x = p-a \\ y = p-b \\ z = p-c \\ p = x + y + z \\ \end{cases}$，有 $S^2 = xyz(x + y + z)$，且显然 $(x, y, z)$ 与 $(a, b, c)$ 一一对应。注意到 $n$ 的因数是 $O(n^{1/3})$ 级别的，因此可以暴力枚举 $x, y \mid n^2$，解一个二次方程可以得到 $z$，验证结果是否满足三角形三边关系即可。
* **备注**：通过换元得到一个较好的关系式，进而解决问题。如果一开始就考虑用三角函数去表示面积的话，后面基本就没法做了。这个代换法称为 Ravi 变换，更多应用 [[https://shakayami-math.hatenablog.com/entry/2019/03/04/022518 | 见此]]。
==== qxforever ====
[[https://codeforces.com/contest/903/problem/G| CF903G]]
* **题意**：给两条链 $A,B$ ，$A_i$ 到 $A_{i+1}$ 和 $B_i$ 到 $B_{i+1}$ 有流量。$A$ 到 $B$ 有一些连边。可以修改 $A$ 中某些边的流量，$q$ 组询问 $A_1$ 到 $B_n$ 的最大流。 $n,q\le 2\times 10^5$
* **题解**：考虑最小割，我们在 $A$ 和 $B$ 中最多割掉一条边，以及一些 $A,B$ 之间的连边。假设在 $A,B$ 中割的边为 $i,j$ ，可以枚举 $i$ ，用线段树维护出对应 $j$ 的最小割。而修改时，每个 $i$ 对应的割边已经确定，只需要在线段树上点修改维护最小值即可。
* **备注**：非常妙的图的性质配合线段树维护。
==== Potassium ====
[[https://codeforces.com/problemset/problem/827/E | CF827E Rusty String]]
* **题意**：给一个 ‘a’ ‘b’ ’?‘ 三种字符组成的串，’?‘ 代表可以选取 ’a‘ ’b‘ 任意一种字符。求所有可能的循环节长度，循环节在字符串结尾可以被截断。
* **题解**：设 $x$ 为循环节，暂时把 '?' 作为通配符处理，分别处理 'a' 'b'，则设 $f(x)=[s_x='a'], g(x)=[s_x='b']$ ，$h(x)=\sum_{i=x}^{n-1}f(i)g(i-x)$ ，$x$ 不是循环节当且仅当 $h(x)\neq 0$。考虑 '?' 不是通配符，于是充要条件变成充分条件。观察到当 $p$ 是合法循环节时 $kp$ 也必然是合法循环节，且如果全部 $kp$ 都是合法循环节，那么 $p$ 也必然是合法循环节。枚举一下筛掉不合法的即可。
* **备注**：对于循环节倍数性质的观察很重要。