2020-2021:teams:i_dont_know_png:week_summary_14
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:i_dont_know_png:week_summary_14 [2020/08/06 21:36] potassium add contest |
2020-2021:teams:i_dont_know_png:week_summary_14 [2020/08/07 17:51] (当前版本) qxforever [qxforever] |
||
|---|---|---|---|
| 行 7: | 行 7: | ||
| | 2020.08.01 | [[multi2020-nowcoder-7 | 2020 Nowcoder Multi-University Training Contest 7]] | | | 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.03 | [[multi2020-nowcoder-8 | 2020 Nowcoder Multi-University Training Contest 8]] | | ||
| - | | 2020.08.06 | [[ntuwftrial-2016 | 2016 台⼤ WF 选拔赛]] | | + | | 2020.08.06 | [[ntuwftrial-2016 | 2016-2017 National Taiwan University World Final Team Selection Contest]] | |
| ===== 团队会议 ===== | ===== 团队会议 ===== | ||
| + | |||
| + | 无 | ||
| 行 18: | 行 20: | ||
| ==== 专题 ==== | ==== 专题 ==== | ||
| + | |||
| + | 无 | ||
| ==== 比赛 ==== | ==== 比赛 ==== | ||
| 行 36: | 行 40: | ||
| ==== 学习总结 ==== | ==== 学习总结 ==== | ||
| - | [[Prufer 序列]] | + | 2020.08.07 [[.:nikkukun:pruefer-sequences| Prufer 序列]] |
| - | [[生成函数]] | + | 2020.08.07 [[.:nikkukun:generating-function | 生成函数]] |
| 行 47: | 行 51: | ||
| ==== 专题 ==== | ==== 专题 ==== | ||
| + | 无 | ||
| ==== 比赛 ==== | ==== 比赛 ==== | ||
| - | **比赛名称** | + | **2020.08.02 AtCoder Beginner Contest 174** |
| ^ 题目 ^ A ^ B ^ C ^ D ^ E ^ F ^ | ^ 题目 ^ A ^ B ^ C ^ D ^ E ^ F ^ | ||
| - | | 通过 | √ | | | | | | | + | | 通过 | √ | √ | √ | √ | √ | √ | |
| | 补题 | | | | | | | | | 补题 | | | | | | | | ||
| - | ==== 学习总结 ==== | + | **2020.08.07 Codeforces Global Round 5** |
| + | ^ 题目 ^ A ^ B ^ C1 ^ C2 ^ D ^ E ^ F ^ | ||
| + | | 通过 | √ | √ | √ | √ | √ | | | | ||
| + | | 补题 | | | | | | | | | ||
| + | ==== 学习总结 ==== | ||
| + | 无 | ||
| 行 64: | 行 74: | ||
| ==== 专题 ==== | ==== 专题 ==== | ||
| + | |||
| + | 无 | ||
| ==== 比赛 ==== | ==== 比赛 ==== | ||
| - | **比赛名称** | + | 无 |
| - | + | ||
| - | ^ 题目 ^ A ^ B ^ C ^ D ^ E ^ F ^ | + | |
| - | | 通过 | √ | | | | | | | + | |
| - | | 补题 | | | | | | | | + | |
| ==== 学习总结 ==== | ==== 学习总结 ==== | ||
| + | s1.swap(s2) | ||
| 行 96: | 行 104: | ||
| ==== qxforever ==== | ==== 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 ==== | ==== 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$ 也必然是合法循环节。枚举一下筛掉不合法的即可。 | ||
| + | * **备注**：对于循环节倍数性质的观察很重要。 | ||
| + | |||
| - | * **题意**： | ||
| - | * **题解**： | ||
| - | * **备注**： | ||
2020-2021/teams/i_dont_know_png/week_summary_14.1596720970.txt.gz · 最后更改: 2020/08/06 21:36 由 potassium
