如果有写的不好的文章欢迎评论，我会在有时间的时候重写一篇更好的。

M_sea的博客

——どうか悔いることなく 明日へ続く道 歩いて——

51nod2558 选址

51nod分析假设答案位置在某条边上，感性理解可得答案关于答案位置与这条边的某个端点的距离是单谷函数。枚举答案在哪条边上并三分，问题变为求最远点。显然某个点到达边上某个位置一定是先到达一个端点再走过来，因此 Floyd 预处理两两之间的最短路即可。代码// =================================== // author: M_sea // website:...

  • M_sea
  • 2020 年 03 月 27 日
  • 暂无评论

    • BZOJ3218 a + b Problem

    BZOJ分析容易看出最小割。考虑连边：对于每个方格，从 $s$ 向它连容量为 $b_i$ 的边，从它向 $t$ 连容量为 $w_i$ 的边。对于每个方格，新建一个节点 $i'$，从 $i$ 向 $i'$ 连容量为 $p_i$ 的边，从 $i'$ 向 $a_j\in [l_i,r_i]$ 且 $j<i$ 的方格 $j$ 连容量为 $+\infty$ 的边。考虑正确性：显然对于每个方格，$...

  • M_sea
  • 2020 年 03 月 27 日
  • 暂无评论

    • 洛谷3514 [POI2011]LIZ-Lollipop

    Luogu分析容易发现，如果存在一个子串的和为 $w$，则一定存在一个子串的和为 $w-2$。不妨设 $[l,r]$ 内的和为 $w$，则如果 $a_l=1,a_r=1$，则 $[l+1,r-1]$ 的和为 $w-2$；否则，若 $a_l=2$，则 $[l+1,r]$ 的和为 $w-2$；若 $a_r=2$，则 $[l,r-1]$ 的和为 $w-2$。于是我们只需要求出最大的偶数和和最大的奇...

  • M_sea
  • 2020 年 03 月 27 日
  • 暂无评论

    • CF505E Mr. Kitayuta vs. Bamboos

    CodeforcesLuogu分析二分答案，则我们需要判定是否能够让所有竹子的高度 $\leq mid$。由于竹子的高度不能小于 $0$，所以正着做不太好做；考虑反过来做，即每根竹子初始高度为 $mid$，每天会变矮 $a_i$，你每天可以选 $k$ 根竹子让他们变长 $p$，判断最后所有竹子的高度是否能 $\geq h_i$，且操作过程中竹子的高度不能 $<0$。考虑贪心，每次选出不...

  • M_sea
  • 2020 年 03 月 16 日
  • 暂无评论

    • CF504E Misha and LCP on Tree

    CodeforcesLuogu分析考虑对原树树链剖分，则两条路径都拆成了 $\mathcal{O}(\log n)$ 个区间。每次取最前面的区间出来比较，如果相同则消掉一个区间，否则答案在该区间内，二分即可。问题在于如何求出某条重链的哈希值。因为重链的 DFS 序是连续的一段，因此可以将树按 DFS 序拍成序列，然后正反各做一遍哈希，则一条重链的哈希值相当于某个区间的哈希值。代码实现有些复杂...

  • M_sea
  • 2020 年 03 月 15 日
  • 暂无评论

    • 51nod1805 小树

    51nod分析考虑一棵满足条件的树的 prufer 序列，可以发现有恰好 $m$ 个数没有出现过。考虑容斥，则我们需要求出至少 $i$ 个数没有出现的方案数，即为代码// =================================== // author: M_sea // website: http://m-sea-blog.com/ // ================...

  • M_sea
  • 2020 年 03 月 15 日
  • 暂无评论

    • 51nod1667 概率好题

    51nod分析甲胜和乙胜类似，三者概率之和为 $1$，因此只考虑计算甲胜的概率，即甲胜的方案数除以总方案数。设甲的第 $i$ 个数为 $X_i$，乙的第 $i$ 个数为 $Y_i$，则甲胜当且仅当则我们相当于要求这个 $k_1+k_2+1$ 元不定方程的非负解数，其中一些变量有上界。考虑容斥掉上界的限制，即钦定一些变量超过了上界，则我们只需要计算不定方程 $\sum_{i=1}^n x_i=...

  • M_sea
  • 2020 年 03 月 14 日
  • 暂无评论

    • 51nod1678 lyk与gcd

    51nod分析于是只要对于每个 $d$ 暴力维护 $\sum_{d|i}a_i$ 即可。代码// =================================== // author: M_sea // website: http://m-sea-blog.com/ // =================================== #include <bits...

  • M_sea
  • 2020 年 03 月 14 日
  • 暂无评论

    • 51nod1325 两棵树的问题

    51nod分析考虑钦定一个点一定在选出的子集中。我们把钦定的这个点作为根，那么如果 $x$ 在子集中，则 $x$ 在两棵树上的父节点都应该在子集中。那么问题就转化成了最大权闭合子图，直接网络流即可。代码// =================================== // author: M_sea // website: http://m-sea-blog.com/ /...

  • M_sea
  • 2020 年 03 月 14 日
  • 暂无评论

    • 51nod1444 破坏道路

    51nod分析首先做一个转化：最多破坏等于最少不破坏。还有一个显然的性质是，两条路径只会有一段重叠部分。因此可以 $\mathcal{O}(n^2)$ 枚举重叠部分，然后判断是否合法并更新答案即可。这样需要预处理两两之间的最短路，因为边权全部为 $1$，BFS 即可。代码// =================================== // author: M_sea // ...

  • M_sea
  • 2020 年 03 月 14 日
  • 暂无评论