2020-2021:teams:i_dont_know_png:cerc2017
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:i_dont_know_png:cerc2017 [2020/05/06 13:41] potassium |
2020-2021:teams:i_dont_know_png:cerc2017 [2020/05/22 20:14] (当前版本) potassium fix typos |
||
|---|---|---|---|
| 行 1: | 行 1: | ||
| + | ====== 2017-2018 ACM-ICPC, Central Europe Regional Contest (CERC 17) ====== | ||
| + | |||
| [[https://codeforces.com/gym/101620|比赛链接]] | [[https://codeforces.com/gym/101620|比赛链接]] | ||
| 行 26: | 行 28: | ||
| ===== C Cumulative Code ===== | ===== C Cumulative Code ===== | ||
| + | |||
| + | unsolved | ||
| ==== 题目描述 ==== | ==== 题目描述 ==== | ||
| 行 48: | 行 52: | ||
| ===== E Embedding Enumeration ===== | ===== E Embedding Enumeration ===== | ||
| + | |||
| + | unsolved | ||
| ==== 题目描述 ==== | ==== 题目描述 ==== | ||
| 行 119: | 行 125: | ||
| ==== 解题思路 ==== | ==== 解题思路 ==== | ||
| - | 首先考虑扩展区间$[i,i+1]$，不妨设$a_i<a_{i+1}$，则要使得$[i,i+1]$区间位于连续区间中，区间$[l,r]=$$[min_{a_i\leq j\leq a_{i+1}}pos_j,max_{a_i\leq j\leq a_{i+1}}pos_j]$必然也位于同一个区间中，这里的$l,r$容易通过$rmq$求得。可以说，区间$[i,i+1]$依赖区间$[l,l+1],[l+1,l+2],...,[r-1,r]$。 | + | 首先考虑扩展区间$[i,i+1]$，不妨设$a_i<a_{i+1}$，则要使得$[i,i+1]$区间位于连续区间中，区间$[l,r]=$$[min_{a_i\leq j\leq a_{i+1}}pos_j,max_{a_i\leq j\leq a_{i+1}}pos_j]$必然也位于同一个区间中，这里的$l,r$容易通过$rmq$求得。可以说，区间$[i,i+1]$依赖区间$[l,l+1],[l+1,l+2],\ldots,[r-1,r]$。 |
| 把区间$[i,i+1]$抽象为一个节点，对于每一个$i$，求出其依赖区间，连边建图缩点后转化成$DAG$上的动态规划问题，从叶节点向上不断更新实际依赖区间即可。 | 把区间$[i,i+1]$抽象为一个节点，对于每一个$i$，求出其依赖区间，连边建图缩点后转化成$DAG$上的动态规划问题，从叶节点向上不断更新实际依赖区间即可。 | ||
2020-2021/teams/i_dont_know_png/cerc2017.1588743685.txt.gz · 最后更改: 2020/05/06 13:41 由 potassium
