2020-2021:teams:i_dont_know_png:neerc2015
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:i_dont_know_png:neerc2015 [2020/05/16 20:49] potassium |
2020-2021:teams:i_dont_know_png:neerc2015 [2020/05/22 20:12] (当前版本) potassium fix typos |
||
|---|---|---|---|
| 行 33: | 行 33: | ||
| $$p\times 10=(p<<3)+(p<<1)$$ | $$p\times 10=(p<<3)+(p<<1)$$ | ||
| - | 数归， $(10^k)_2$ 后 $k$ 位都为 $0$ 。按位从低到高枚举填 $0$ 或者 $1$ ，填数不影响前 $k-1$ 个位置的二进制表示，仅需要判断填数后第 $k$ 位的十进制和二进制相等与否即可。需要用大数，复杂度$\mathcal{O}(nl)$。 | + | 数归， $(10^k)_2$ 后 $k$ 位都为 $0$ 。按位从低到高枚举填 $0$ 或者 $1$ ，填数不影响前 $k-1$ 个位置的二进制表示，仅需要判断填数后第 $k$ 位的十进制和二进制相等与否即可。需要用大数，复杂度$O(nl)$。 |
| + | |||
| 行 39: | 行 41: | ||
| upsolved by nikkukun | upsolved by nikkukun | ||
| + | |||
| + | ==== 题目描述 ==== | ||
| + | |||
| + | 给一个仙人掌，现在要你选一条原图中的边 $A$ 和一条原图中不存在的边 $B$，使得删掉 $A$ 再加入 $B$ 后的图还是个仙人掌，求方案数。 | ||
| + | |||
| + | $n \leq 50,000$ | ||
| + | |||
| + | ==== 解题思路 ==== | ||
| + | |||
| + | 若删掉的边是桥，则仙人掌变成两个仙人掌，在它们之间任意连边都是合法的新仙人掌。假装把仙人掌当做是树 DP 可以得到子树大小。 | ||
| + | |||
| + | 若删掉的边在环上，则删掉之后这个环变成了一条链，且与原来和它连接的桥成了一大堆桥，我们暂时称之为桥连通块。推一推可以发现新添加的边只能在某一个桥连通块内自己连接（否则不是仙人掌），那么这个连通块的贡献是块内任意两点连接的个数减去已有的边数，即 $\binom s2 - (s - 1)$，其中 $s$ 为连通块内点的个数。 | ||
| + | |||
| + | 实现时，可以用并查集维护桥的连通块，再对每个环考虑将它上面的每个边拆掉之后，变成的新连通块点数 $s$ 即可。 | ||
| + | |||
| + | |||
| + | |||
| + | |||
| + | |||
| 行 47: | 行 68: | ||
| ==== 题目描述 ==== | ==== 题目描述 ==== | ||
| - | 给一个 $n$ 个点的多边形的三角剖分，边长均为 1 。 $q$ 次询问，每次询问两点间距离。 $n,q\le 10000$。 | + | 给一个 $n$ 个点的多边形的三角剖分，边长均为 $1$ 。 $q$ 次询问，每次询问两点间距离。 $n,q\le 10000$。 |
| ==== 解题思路 ==== | ==== 解题思路 ==== | ||
| 行 55: | 行 76: | ||
| 分治，每次将多边形尽可能均匀地分成 $A,B$ 两部分，询问中两点分别在两边的直接 $BFS$ 处理出距离，在同一边的递归处理。 | 分治，每次将多边形尽可能均匀地分成 $A,B$ 两部分，询问中两点分别在两边的直接 $BFS$ 处理出距离，在同一边的递归处理。 | ||
| - | 注意需要在保证复杂度的情况下，每次的修改不能影响孩子或右半部分。复杂度 $\mathcal{O}(n\log n)$。 | + | 注意需要在保证复杂度的情况下，每次的修改不能影响孩子或右半部分。复杂度 $O(n\log n)$。 |
| 行 79: | 行 100: | ||
| 有个蛤蟆想要从左岸跳到右岸，其中有一些石头 $(n\le 1000)$ ，他还拿着一块石头可以放下来。每次只能跳到石头上，手里的石头只能用一次。问从左岸跳到右岸最长的一步最短需要多长。 | 有个蛤蟆想要从左岸跳到右岸，其中有一些石头 $(n\le 1000)$ ，他还拿着一块石头可以放下来。每次只能跳到石头上，手里的石头只能用一次。问从左岸跳到右岸最长的一步最短需要多长。 | ||
| + | {{.:potassium:neerc15_pic_1.jpg?500}} | ||
| ==== 解题思路 ==== | ==== 解题思路 ==== | ||
| 行 108: | 行 130: | ||
| unsolved | unsolved | ||
| + | |||
| + | |||
| + | |||
| ===== J - Jump ===== | ===== J - Jump ===== | ||
| - | solved by nikkukun | + | idea from nikkukun, qxforever, potassium, implemented by nikkukun |
| + | |||
| + | ==== 题目描述 ==== | ||
| + | |||
| + | 给一个 $n$ 位 $01$ 串，你可以猜 $n + 500$ 次这个串是什么。如果你全猜对，那就告诉你 $n$；如果你有恰好有 $\dfrac n2$ 个位置猜对，告诉你 $\dfrac n2$；否则告诉你 $0$。 | ||
| + | |||
| + | $n \in [1, 1,000]$ | ||
| + | |||
| + | ==== 解题思路 ==== | ||
| + | |||
| + | 假设已经找到了一个串使得恰好有 $\dfrac n2$ 个位置猜对，那么我们只要用 $n-1$ 次询问反转串中二元组 $(i, i+1)$ 后的结果，就能知道整个串任意两位之间的答案正确性： | ||
| + | |||
| + | - 为 $0$，则 $(i, i+1)$ 要么都猜对，要么都猜错 | ||
| + | - 为 $\dfrac n2$，则 $(i, i+1)$ 一对一错 | ||
| + | |||
| + | 现在考虑怎么在 $500$ 次里找到这个恰好有 $\dfrac n2$ 个位置猜对的串。可以随机去找：一次随机中命中该串的概率是 $\binom {1000}{500} \times 0.5^{1000} = 2.52\%$，$500$ 次能找到这个串的概率是 $99.99\%$。 | ||
| + | |||
| + | |||
| ===== K - King’s Inspection ===== | ===== K - King’s Inspection ===== | ||
| 行 128: | 行 171: | ||
| 将出度为 $1$ 的点用并查集缩点，记录链的起点。在缩完点的新图中，只保留与链的起点相连的边。DFS 搜一搜即可。 | 将出度为 $1$ 的点用并查集缩点，记录链的起点。在缩完点的新图中，只保留与链的起点相连的边。DFS 搜一搜即可。 | ||
| + | |||
| + | |||
| + | |||
| ===== L - Landscape Improved ===== | ===== L - Landscape Improved ===== | ||
| 行 133: | 行 179: | ||
| solved by nikkukun | solved by nikkukun | ||
| + | ==== 题目描述 ==== | ||
| + | |||
| + | 长度为 $n$ 的水平线上有一些方块堆叠的地形，位置 $i$ 处地形高度为 $h_i$。你可以在已有的地形上加一些方块，但是要保证每一块方块添加时，它的左下、正下、右下不能是空的。 | ||
| + | |||
| + | 现在你可以添加最多 $m$ 次，求能搭出的最高高度。 | ||
| + | |||
| + | $n \leq 10^5$，$h_i \in [1, 10^9]$，$m \in [0, 10^{18}]$ | ||
| + | |||
| + | ==== 解题思路 ==== | ||
| + | |||
| + | 贪心的情况下搭出的最高点是个金字塔形状的，因此可以二分答案后以每个点作为最高点所需要的方块总数判断。 | ||
| + | |||
| + | 假设当前最高高度为 $x$，位置在第 $i$ 个，则需要加方块的左端点 $l$ 应当满足 $h_l \geq x - (i - l)$，即 $h_l - l \geq x - i$，在单调栈上二分可以找到最近的左端点；右端点同理可求。 | ||
| + | |||
| + | 注意到能额外添加的高度不会超过 $n$，因此二分的上界与 $\max \{h_i\}$ 同级，总时间复杂度 $O(n \log n \log \max \{h_i\})$。 | ||
2020-2021/teams/i_dont_know_png/neerc2015.1589633394.txt.gz · 最后更改: 2020/05/16 20:49 由 potassium
