2020-2021:teams:i_dont_know_png:cerc2017
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:i_dont_know_png:cerc2017 [2020/05/06 13:36] nikkukun [解题思路] |
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|比赛链接]] | ||
| 行 5: | 行 7: | ||
| solved by qxforever | solved by qxforever | ||
| - | === 题目描述 === | + | ==== 题目描述 ==== |
| - | === 解题思路 === | + | ==== 解题思路 ==== |
| ===== B Buffalo Barricades ===== | ===== B Buffalo Barricades ===== | ||
| 行 17: | 行 19: | ||
| 平面上有一些牛，依次在某些点加入一些栅栏，问此次加入的栅栏和之前加入的且在左下角的栅栏组成的密闭空间中有多少头牛。保证没有栅栏同$x$或同$y$。 | 平面上有一些牛，依次在某些点加入一些栅栏，问此次加入的栅栏和之前加入的且在左下角的栅栏组成的密闭空间中有多少头牛。保证没有栅栏同$x$或同$y$。 | ||
| - | === 解题思路 === | + | ==== 解题思路 ==== |
| 不妨只考虑添加完所有栅栏后，某一个$y$下的牛、栅栏分布情况。容易想到这是一个牛和栅栏交替的结构，而栅栏可以跨$y$继续向下延伸，故考虑用$set$存一下栅栏的情况（加入时间、$x$位置），然后按$y$从大到小进行枚举处理。 | 不妨只考虑添加完所有栅栏后，某一个$y$下的牛、栅栏分布情况。容易想到这是一个牛和栅栏交替的结构，而栅栏可以跨$y$继续向下延伸，故考虑用$set$存一下栅栏的情况（加入时间、$x$位置），然后按$y$从大到小进行枚举处理。 | ||
| 行 27: | 行 29: | ||
| ===== C Cumulative Code ===== | ===== C Cumulative Code ===== | ||
| - | === 题目描述 === | + | unsolved |
| - | === 解题思路 === | + | ==== 题目描述 ==== |
| + | |||
| + | ==== 解题思路 ==== | ||
| ===== D Donut Drone ===== | ===== D Donut Drone ===== | ||
| 行 35: | 行 39: | ||
| upsolved by Potassium | upsolved by Potassium | ||
| - | === 题目描述 === | + | ==== 题目描述 ==== |
| 有一个围成一个甜甜圈的$r\times c$矩阵$a$（上下可达、左右可达），初始位置在$(1,1)$，有$q$次、两种操作：走$k\leq 10^9$步并询问位置；将$a_{xy}$赋为$z$。 | 有一个围成一个甜甜圈的$r\times c$矩阵$a$（上下可达、左右可达），初始位置在$(1,1)$，有$q$次、两种操作：走$k\leq 10^9$步并询问位置；将$a_{xy}$赋为$z$。 | ||
| 行 41: | 行 45: | ||
| $r,c\leq 2000,q\leq 5000$。 | $r,c\leq 2000,q\leq 5000$。 | ||
| - | === 解题思路 === | + | ==== 解题思路 ==== |
| 观察到$q$比较小，可以考虑记录循环节，但由于循环节是$O(rc)$级别的，考虑降级，即记录$(x,1)$走$c$步后位于$(nxt[x],1)$。询问比较容易，问题在于修改。 | 观察到$q$比较小，可以考虑记录循环节，但由于循环节是$O(rc)$级别的，考虑降级，即记录$(x,1)$走$c$步后位于$(nxt[x],1)$。询问比较容易，问题在于修改。 | ||
| 行 49: | 行 53: | ||
| ===== E Embedding Enumeration ===== | ===== E Embedding Enumeration ===== | ||
| - | === 题目描述 === | + | unsolved |
| - | === 解题思路 === | + | ==== 题目描述 ==== |
| + | |||
| + | ==== 解题思路 ==== | ||
| ===== F Faulty Factorial ===== | ===== F Faulty Factorial ===== | ||
| 行 57: | 行 63: | ||
| solved by Potassium | solved by Potassium | ||
| - | === 题目描述 === | + | ==== 题目描述 ==== |
| 给定$n,p,r(n\leq 10^{18},p\leq 10^7)$，求一个序列$a$满足$a_i=i,i\neq t;a_i<i,i=t$（$t$可任选），且$\Pi_{i}a_i\equiv c\text{ mod }p$。 | 给定$n,p,r(n\leq 10^{18},p\leq 10^7)$，求一个序列$a$满足$a_i=i,i\neq t;a_i<i,i=t$（$t$可任选），且$\Pi_{i}a_i\equiv c\text{ mod }p$。 | ||
| - | === 解题思路 === | + | ==== 解题思路 ==== |
| 根据$r$是否为$0$讨论。 | 根据$r$是否为$0$讨论。 | ||
| 行 73: | 行 79: | ||
| solved by Potassium | solved by Potassium | ||
| - | === 题目描述 === | + | ==== 题目描述 ==== |
| 给一个连通无向图，初始位置在$1$号节点，目标为$n$号节点。每一天，所处位置的机器会等概率随机抽取与当前节点相邻的节点，你可以选择留在原地或者去往这个节点，问采取最优策略的情况下，到达目标的期望时间为多少。 | 给一个连通无向图，初始位置在$1$号节点，目标为$n$号节点。每一天，所处位置的机器会等概率随机抽取与当前节点相邻的节点，你可以选择留在原地或者去往这个节点，问采取最优策略的情况下，到达目标的期望时间为多少。 | ||
| - | === 解题思路 === | + | ==== 解题思路 ==== |
| 设$f[i]$表示点$i$到点$n$的期望时间，那么我们必然是从$f$大的向$f$小的节点走。设与$i$直接相连的的集合为$P$，有 | 设$f[i]$表示点$i$到点$n$的期望时间，那么我们必然是从$f$大的向$f$小的节点走。设与$i$直接相连的的集合为$P$，有 | ||
| 行 105: | 行 111: | ||
| solved by nikkukun | solved by nikkukun | ||
| - | === 题目描述 === | + | ==== 题目描述 ==== |
| - | === 解题思路 === | + | ==== 解题思路 ==== |
| ===== I Intrinsic Interval ===== | ===== I Intrinsic Interval ===== | ||
| 行 113: | 行 119: | ||
| upsolved by Potassium | upsolved by Potassium | ||
| - | === 题目描述 === | + | ==== 题目描述 ==== |
| 给一个$1..n$的排列$a$，$q$次询问区间$[l,r]$，问最小的覆盖$[l,r]$区间的、满足排完序后连续的区间。 | 给一个$1..n$的排列$a$，$q$次询问区间$[l,r]$，问最小的覆盖$[l,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],...,[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$上的动态规划问题，从叶节点向上不断更新实际依赖区间即可。 | ||
| 行 129: | 行 135: | ||
| solved by nikkukun | solved by nikkukun | ||
| - | === 题目描述 === | + | ==== 题目描述 ==== |
| 给一棵树，求所有的正整数$k$满足：可以把树切成若干个大小为$k$的连通块，$n<1000000$。 | 给一棵树，求所有的正整数$k$满足：可以把树切成若干个大小为$k$的连通块，$n<1000000$。 | ||
| - | === 解题思路 === | + | ==== 解题思路 ==== |
| $O(\sqrt n)$枚举每个因数，对于一个因数$k$，判断是否合法。 | $O(\sqrt n)$枚举每个因数，对于一个因数$k$，判断是否合法。 | ||
| 行 143: | 行 149: | ||
| upsolved by qxforever | upsolved by qxforever | ||
| - | === 题目描述 === | + | ==== 题目描述 ==== |
| 给$n$个长度为$7$的数字，一次操作表示将某个连续区间内所有数字轮换任意次数。要让所有数字最终处于最大值，问最少操作数。 | 给$n$个长度为$7$的数字，一次操作表示将某个连续区间内所有数字轮换任意次数。要让所有数字最终处于最大值，问最少操作数。 | ||
| - | === 解题思路 === | + | ==== 解题思路 ==== |
| 首先排掉$7$位均相同的数字，其他数字的轮换必然有且只有一个最大值，问题转化为“有$n$个$[0,6]$之间的数，一次操作是一个区间加某个值模$7$，问多少步能够使得所有数字变为$0$”。 | 首先排掉$7$位均相同的数字，其他数字的轮换必然有且只有一个最大值，问题转化为“有$n$个$[0,6]$之间的数，一次操作是一个区间加某个值模$7$，问多少步能够使得所有数字变为$0$”。 | ||
| 行 159: | 行 165: | ||
| solved by Potassium | solved by Potassium | ||
| - | === 题目描述 === | + | ==== 题目描述 ==== |
| 给定平面上一堆平行于坐标轴或者成$45$度的正方形，求总覆盖面积。 | 给定平面上一堆平行于坐标轴或者成$45$度的正方形，求总覆盖面积。 | ||
| - | === 解题思路 === | + | ==== 解题思路 ==== |
| 对两种情况分别做二维前缀和，对每个格子的四部分用二进制表示状态即可。 | 对两种情况分别做二维前缀和，对每个格子的四部分用二进制表示状态即可。 | ||
2020-2021/teams/i_dont_know_png/cerc2017.1588743372.txt.gz · 最后更改: 2020/05/06 13:36 由 nikkukun
