博客食用指北 wxwoo 2019-03-22 置顶 评论系统链接请填写OJ账户(luogu优先),选填邮箱用于验证和回复通知,必须填写无法匿名评论头像请用你的邮箱,到Gravatar设置由于评论管理系统尚未部署完成(其实就是咕咕咕了),不一定会发送邮件
P4315 月下“毛景树” 题解 wxwoo 2019-09-09 题解 / 洛谷 原题目链接 首先树剖边权转点权,把每一条边的权值下放到子节点上 在修改的时候注意最后要避开两个点的LCA,因为LCA的点权所代表的边权不在两个点的路径上 然后看见区间推平就想到了ODT 阅读全文 树链剖分 ODT
P2136 拉近距离 题解 wxwoo 2019-07-27 题解 / 洛谷 原题目链接 此题显然为有向图判负权环板子题 没做过请先右转模板【负环】 此题关键点: 小明和小红的生活中,有N个关键的节点。有M个事件,记为一个三元组(Si,Ti,Wi),表示从节点Si有一个事件可以转移到Ti,事件的效果就是使他们之间的距离减少Wi。 所以建边时,要把权值变为相反数 然后以1为源点进行SPFA求负环,就AC了 ……吗? 阅读全文 负环 SPFA
P4177 [CEOI2008]order 题解 wxwoo 2019-07-10 题解 / 洛谷 原题目链接 先无视租机器,明显的最大权闭合子图 最大权闭合子图: 给定一个有向图,点有点权,选择一个子图,满足子图上如果选择了一个点就必须选择它后继的所有点。最大化点权和。 我们将机器和任务都看成一个点 如果这题没有租机器,这题的建边方式就应该是这样: 源点向订单连流量为利润的边 机器向汇点连流量为购买价格的边 每个订单向需要的机器连流量为inf的边 可以发现,源点连的边都是订单的利润,汇点连的边都是机器的成本,只有机器和订单之间的边是$inf$ 对于每个订单需要的相同机器,租用的价格也不一样 所以我们考虑把$inf$换成租机器的费用 阅读全文 网络流
SP1476 PROFIT - Maximum Profit 题解 wxwoo 2019-06-15 题解 / SPOJ 原题目链接 明显的最大权闭合子图 最大权闭合子图: 给定一个有向图,点有点权,选择一个子图,满足子图上如果选择了一个点就必须选择它后继的所有点。最大化点权和。 经典的网络流问题,具体使用最小割求解 我们将顾客和通讯站都看成一个点,然后如下建边: 源点向顾客连流量为利润的边 通讯站向汇点连流量为成本的边 每个顾客向需要的通讯站连流量为inf的边 阅读全文 网络流
SP2916 GSS5 - Can you answer these queries V 题解 wxwoo 2019-06-14 题解 / SPOJ 原题目链接 前置知识:不带修区间最大子段和 没做过请先右转GSS1 这题比GSS1多了一个对左右端点的区间限制,GSS1的做法不再适用 这时我们就要分两种情况讨论 阅读全文 线段树
SP3978 DISQUERY - Distance Query 题解 wxwoo 2019-05-27 题解 / SPOJ 原题目链接 树上链最值查询 做法很多,LCT,树上倍增,树剖都可以 但由于LCT常数过大,树上倍增比树剖常数大,这里使用树链剖分 边权转点权是树剖常用套路,将边权转成深度较大的点的点权,查询时注意避开两点的LCA的权值 由于不带修改,树剖后用ST表维护,时间复杂度$\mathcal{O}(n\log n)$,比用线段树维护$\mathcal{O}(n\log ^2n)$还少一个log 阅读全文 树链剖分 ST表
hexo中的mathjax数学公式渲染优化 wxwoo 2019-05-15 在使用hexo博客和material-x等博客主题时,难免会遇到mathjax数学公式渲染失败或者与markdown渲染冲突的问题。 xaoxuu给出了解决方案,只需在_config.yml里加入mathjax: true即可解决,可以解决大量的mathjax公式渲染,但仍有部分复杂的公式渲染出现问题。 我在这里给出一种解决方案。 注:部分资料来自互联网 阅读全文 mathjax hexo material-x
CF1156A Inscribed Figures 题解 wxwoo 2019-05-02 题解 / codeforces 原题目链接 PS: 这题比赛时当场出锅…… std被hack…… 整场比赛最后unrated…… 对于每两个相邻的图形,交点数是固定的 也就是说我们可以打表 12345 1 2 3 1 / 3 42 3 / inf3 4 inf / 但是!直接打表是错误的!std就是这样被hack的! 阅读全文 模拟
SP1296 SUMFOUR - 4 values whose sum is 0 题解 wxwoo 2019-04-23 题解 / SPOJ 原题目链接 首先想到$\Theta(n^4)$的暴力枚举,但$n\le 4000$显然不行。 考虑先预处理出c数组和d数组的和,再暴力计算答案。 由于c数组和d数组的和可能会有重复,排序后使用二分来降低时间复杂度 最终时间复杂度$\Theta (n^2\log n)$ 阅读全文 二分
P1791 [国家集训队]人员雇佣 题解 wxwoo 2019-04-19 题解 / 洛谷 原题目链接 选人有利润,选了要付出代价:明显的最小割模型 我们将每个人看成一个点,然后如下建边: 源点向每个人连流量为其总收益的边(即$\sum\limits_{j=1}^n E_{i,j}$) 每个人向汇点连流量为其花费的边 $i$向$j$连流量为$E_{i,j} \times 2$的边 阅读全文 网络流