Panda2134's Blog

Not only coding

CDQ分治学习笔记

orz__stdcall 前言昨天写一个数据结构题……大致就是给出一个排列，每次删除一个数字，求每次删除之前的逆序对数目。不难发现，这个问题是动态的二维偏序，我们可以把它转为三维数点。不妨假设在某个二维平面中有一个坐标系，横坐标为排列中的下标，纵坐标为排列中的值，也就是排列中一个数 $a_i$ 对应坐标 $(i, a_i)$ 。先用树状数组求出初始逆序对数目，每次删点 $(x, y...

Posted by panda_2134 on March 25, 2018

利用单调性优化动态规划

参考了这个题解，虽然有错误，但是讲的很不错。感觉网上某些斜率优化的题解就是混的，没有严谨的证明，所以我试着证明一下= = 如果证明错了就使劲喷我好了= = 斜率优化 HDU3507 题意把一个序列 ${c_n}$ 划分成若干份，每份的代价为 $\left( \sum c_i \right)^2 + M$. 最小化总代价和。思路 $f(i)$ 表示前 $i$ 个的最小总代...

Posted by panda_2134 on March 19, 2018

Coreoftree

– categories: 解题报告 comments: true title: “[NOIP2007]树网的核” layout: post tags: 图论树树的直径数据结构单调队列 two-pointers BZOJ-1999 题意给出一棵树，求一条路径使得树上点到它的距离的最大值最小。 $n \leq 300000$. 思路...

Posted by panda_2134 on March 18, 2018

[HNOI2013]游走

题意一个无向简单连通图，边权为 $1\dots m$ 的整数。问分配边权后，从点 1 随机游走到点 $n$ 的最小期望距离。思路刚看完《训练指南》上面的矩阵一部分，做一做相关省选题练练手，结果第一题就不会做…… 这是最开始的错误思路：我们对每个点显然可以列出递推式，设 $a_u$ 为点 1 走到点 $u$ 的期望距离。那么一定有： \[a_u = \sum_{<u,...

Posted by panda_2134 on March 15, 2018

[六省联考2017]相逢是问候

day1 没上200……不应该啊……正常点的话215应该没问题？题意给定一个长为 $n (n \le 10^5)$ 的序列，要求支持 2 个操作：把某个区间每个元素 $a_i$ 换成 $c^{a_i}$ ，其中 $c$ 是给定常数。求区间和思路 PoPoQQQ大爷：这……这不是……上帝和集合的正确用法吗？然而我做过上帝和集合的正确用法，却没能做出来这题 &...

Posted by panda_2134 on March 14, 2018

[六省联考2017]分手是祝愿

上午做了六省联考2017 Day2. 挂的一塌糊涂，除了某个做过的题 A 了之外其他题目加起来只有55. 这个题目的贪心都没想到。 cxy神犇接近AK。技不如人，如果不多刷题的话，可能只有失败的后果吧。现在也不要想别的了，挂了就是自己弱，没别的。就是自己弱。太弱了，就没有大学上了。去除杂念，专心刷题，才有可能超越啊。思路我们考虑50分的情况。对于...

Posted by panda_2134 on March 13, 2018

莫比乌斯反演学习笔记

莫比乌斯函数我们定义 \(\begin{equation} \mu(n) = \begin{cases} 1 & \text{当} n = 1 \\ (-1)^k & \text{当}n \text{为} k \text{个互异质数的积} \\ 0 & \text{当} n \text{某个质因子次数大于等于} 2 \en...

Posted by panda_2134 on March 12, 2018

[六省联考2017]寿司餐厅

省选提前到 4 月 6 日了，慌的要命，赶紧找找去年的题目做一做。 Luogu-3749 思路 Kiana的美食评判标准的“记忆性”说明选择了多个区间，影响不会扩大。“选择即有对应的影响，选择了多个物品，影响不会扩大，求最大权和……” 不就是最大权闭合子图吗？每个区间建 1 个点，每个代号建 1 个点，分别赋相应的权值，再找出最大权闭合子图即可。代码 #include <...

Posted by panda_2134 on March 8, 2018

[HNOI2013]切糕

bzoj3144 题意给出一个 $P \times Q \times R$ 的长方体，横着切一刀，使得在满足相邻切点 $z$ 轴距离小于 $D$ 的前提下，切面权值和最小。思路题中是个显然的最小割模型，但是“某些点不能同时割”的限制比较棘手，不是很好处理…… 尝试了几种建图方法，但都没办法证明正确性。看了题解才发现其中一种几乎就是正解…… 对于最小割相关问题，思考的时候不应...

Posted by panda_2134 on March 8, 2018

ISAP算法学习笔记

ISAP，即改进的SAP算法。算法基于：如果每次在残量网络中从汇点开始反向BFS， s-t 距离是单调不减的。流程如下：首先用BFS从汇点出发计算每个点到汇点的距离标号。 Advance: 每次走满足 $d_v = d_u - 1$ 的路径，即走最短路。维护每个点的当前弧。（实践证明，只有ISAP需要当前弧优化……原始对偶加了之后反而更慢……Dinic加了之后有时候快很多...

Posted by panda_2134 on March 7, 2018