xia0ji233's blog

很开心，图论的知识也是积少成多，回首往昔，我对图论的算法仅限于最短路算法($\text {dijkstra}$)和最小生成树($\text {kruskal&prime}$) 。今天来学学这个 $\text {2-SAT}$ 问题。 2-SAT简介 $\text {SAT}$ 是适定性（Satisfiability）问题的简称。一般形式为 k - 适定性问题，简称 k-SAT。而当 $k>2$ 时该问题为 NP 完全的。所以我们只研究 $k=2$ 的情况。 $\text {2-SAT}$，简单的说就是给出 个集合，每个集合有两个元素，已知若干个 ，表示 与 矛盾（其中 与 属于不同的集合）。然后从每个集合选择一个元素，判断能否一共选 个两两不矛盾的元素。显然可能有多种选择方案，一般题中只需要求出一种即可。(from OI WIKI) 我想上面说的也比我说的稍微清楚点了，那么他的现实意义是什么呢？比较常见的就是逻辑推导了。 告诉你现在有 A，B，C三个人，且A和B是男生，如果B是男生，那么C是女生。问你这三个人的性别分别是什么，我们很容易可以知道A，B为男， ...

差分约束系统，就是给出一组形如 $x_i-x_j\le d$ 的不等式，求出这组不等式的一组解。这类问题通常转化为图论中的最短路来解。 原理那我们转换一下，假设 $x_i$ 为点 $i$ 的单源最短路长度，$x_j$ 为点 $j$ 的单源最短路长度。那么以上不等式就可以转换成 $dis[i]-dis[j]\le d\to dis[i]\le dis[j]+d$。 那么这个就转变成了 $j\to i$ 一条权值为 $d$ 的边的最短路搜索了。因为如果一条边 $i\to j$ 权值为 $d$ ，那么必然有 $dis[i]\le dis[j]+d$ ，如果不满足这个条件。我们用反证法证明一下这个结论，设一条边 $i\to j$ 权值为 $d$，且满足 $dis[i] > dis[j]+d$，那么在一次单源最短路算法时，必然会导致 $i$ 点被松弛。即发生 123if(dis[i]>dis[j]+d){ dis[i]=dis[j]+d;} 那么我们可以得出结论：$dis[i]$ 一定不会比 $dis[j]+d$ 大，当 $i\to j$ 有一条权值为 ...

前面讲到了spfa，然后有一个判断负环的操作，这个判断负环有更好的思路。 设$cnt[i]$为$s$到$i$的最短路中已经经过的路径条数，如果超过 $n$ 个边，那就说明有 $n-1$ 个点，必产生了负环，如果没有负环绝对是不会找到回路的。 洛谷P3385emm直接给标程吧，就是最朴实无华的 $spfa$ 负环判断。 标程 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778#include<bits/stdc++.h>#define maxn 2005using namespace std;struct eee{ int next; int to; int w;}edge[maxn<<2];int root[maxn],dis[maxn],e_cnt[maxn],in_que[ma ...

勇敢小鸡，不怕困难。时隔多日，又来复习图论算法了，本来想的是搞一下差分约束的，但是发现前置知识是spfa算法，所以就先来学习一下这个。 spfa算法介绍SPFA算法是求解单源最短路径问题的一种算法，由理查德·贝尔曼（Richard Bellman） 和 莱斯特·福特 创立的。有时候这种算法也被称为 Moore-Bellman-Ford 算法，因为 Edward F. Moore 也为这个算法的发展做出了贡献。它的原理是对图进行V-1次松弛操作，得到所有可能的最短路径。其优于dijkstra算法的方面是边的权值可以为负数、实现简单，缺点是时间复杂度过高，高达 O(VE)。但算法可以进行若干种优化，提高了效率。 算法的思路：我们用数组dis记录每个结点的最短路径估计值，用邻接表或邻接矩阵来存储图G。我们采取的方法是动态逼近法：设立一个先进先出的队列用来保存待优化的结点，优化时每次取出队首结点u，并且用u点当前的最短路径估计值对离开u点所指向的结点v进行松弛操作，如果v点的最短路径估计值有所调整，且v点不在当前的队列中，就将v点放入队尾。这样不断从队列中取出结点来进行松弛操作，直至队列空 ...

今天学习一下新的字符串算法——manacher算法。 manacher简介 最长回文子串（英语：Longest palindromic substring）是计算机科学中的问题，在一个字符串中查找一个最长的连续的回文的子串，例如“banana”最长回文子串是“anana”。最长回文子串并不一定是唯一的，比如在“abracadabra”中，没有超过3个字符的回文子串，但是有两个回文字符串长度都是3：“ada”和“aca”。在一些应用中，我们求出全部的极大回文子串（不被其他回文串包含的回文子串）。 Manacher于1975年发现了一种线性时间算法[1]，可以在列出给定字符串中从任意位置开始的所有回文子串。并且，Apostolico, Breslauer & Galil [2]发现，同样的算法也可以在任意位置查找全部极大回文子串，并且时间复杂度是线性的。因此，他们提供了一种时间复杂度为线性的最长回文子串解法。另外，Jeuring (1994)[3], Gusfield (1997)[4]发现了基于后缀树的算法。也存在已知的高效并行算法。(from wiki) manacher ...

图论也挺难的，所以我选择复习一下字符串那些算法。 字符串算法第一个很重要的就是匹配了，也就是 $KMP$ 算法，这里的话主要就是计算模式串的 $Next$ 数组。那一位的 $Next$ 数组的值相当于这一位之前的字符串的最大相同前后缀长度。 比如 $baabaa$ 那么它的 $Next$ 数组分别是 $-1\ 0\ 0\ 0\ 1\ 2$ 。 为什么最开始的那个是 $-1$ 呢，因为说了，当前的next所看的字符串是不包括当前字符的，所以第一个的next值所看的字符串其实是一个空串。并且我们可以想象一下，如果第一位它就不匹配，我要跳到哪？答案是模式串指针不跳，匹配串指针要跳。但是一般情况下失配是完全相反的，只有匹配的情况下j会往后跳，所以我们会把第一位失配和匹配的情况归为一类，或者是说特判一下第一位失配的情况，就让它跳到-1，如果跳到-1那么 $i++,j++$ 就好了。 那么接下来我们做一道模板匹配题。 练习为了防止被说水博客，这里就放三题好了。 洛谷P3375标板 $KMP$，只不过就是说，最后要那你输出一下模式串从开头到 $i$ 子串串的最长公共前后缀，这个跟 $Next$ ...

很烦啊，最近复习图论，贼艰难，很多题目基本多多少少都要用树形dp。而我专注于搞图论和数据结构，dp完全就是略知一二，逃避没有用，不会就去学，碰到困难就去面对。 树上dp其实跟普通的dp差不多，甚至会比普通的dp写起来简单，但是前提是要理解。 例题洛谷P1352这个真的是典中典了，我看几乎所有的技术博客都会拿这个当作树形dp的入门题，那我也不例外。 题目分析某大学有 $n$ 个职员，编号为 $1\ldots n$。 他们之间有从属关系，也就是说他们的关系就像一棵以校长为根的树，父结点就是子结点的直接上司。 现在有个周年庆宴会，宴会每邀请来一个职员都会增加一定的快乐指数 $r_i$，但是呢，如果某个职员的直接上司来参加舞会了，那么这个职员就无论如何也不肯来参加舞会了。 所以，请你编程计算，邀请哪些职员可以使快乐指数最大，求最大的快乐指数。 其实我觉得这个跟有依赖的背包题有异曲同工之妙，不通的是，他们不是依赖，而是互斥，选了一个人之后则不能选另一个人。而依赖背包则是选了一个则必须选另外一个，当然另外一个没有这个限制，否则两个物品直接合并一个物品啦。 这里很明显就是 $n$ 个人 $n- ...

洛谷P1948题解。 题目描述多年以后，笨笨长大了，成为了电话线布置师。由于地震使得某市的电话线全部损坏，笨笨是负责接到震中市的负责人。该市周围分布着$N(1<=N<=1000)$根据$1……n$顺序编号的废弃的电话线杆，任意两根线杆之间没有电话线连接，一共有$p(1<=p<=10000)$对电话杆可以拉电话线。其他的由于地震使得无法连接。 第i对电线杆的两个端点分别是$a_i,b_i$，它们的距离为$l_i(1<=l_i<=1000000)$。数据中每对$(a_i,b_i)$只出现一次。编号为1的电话杆已经接入了全国的电话网络，整个市的电话线全都连到了编号N的电话线杆上。也就是说，笨笨的任务仅仅是找一条将1号和N号电线杆连起来的路径，其余的电话杆并不一定要连入电话网络。 电信公司决定支援灾区免费为此市连接k对由笨笨指定的电话线杆，对于此外的那些电话线，需要为它们付费，总费用决定于其中最长的电话线的长度(每根电话线仅连接一对电话线杆)。如果需要连接的电话线杆不超过k对，那么支出为0. 请 ...

今天来复盘一下上次省赛考到的题目，异常地折磨人。 先说一下这题比赛的情况吧，基本上呢，银奖中等偏上的队伍都是做出来了的。 那我们就看看这题吧。 题目简介 什么思路在题目名字这里就一目了然了，那自然是最短路径。 而当我一眼扫过去看到这个数据量的时候瞬间惊呆。$1≤n≤100000，1≤m≤200000$，不仅如此，还有 $q$ 次询问最短路径，$q≤200000$ 当时一看，这玩你妈。给一个点都勉强能过了，这有这么多点，如果按照常规思路，一次单源最短路径复杂度 $nlog_2n$ 然后 $q$ 次询问，总复杂度就是 $qnlog_2n$ 全部以最大值带进去妥妥的超时。所以当时比赛的时候看到这个题目是直接放弃了的，而且英文不好的我留下了悔恨的眼泪。 题目分析但是它还有一个条件，那就是，直接相连的两个点当中，其中一个点的编号一定是另一个点的二进制前缀，这就说明了一点，$2$ 它一定不会跟 $3,6,12……$ 等点连接起来的，因为它们的前缀是 $11_{2}$，而 $2_{10}$ 是 $10_{2}$ 开头的，那么这样的话我们就可以构造一棵 $tire$ 树。像这样子。 可以很明 ...

最近来复习一遍图论的板子——LCA。 概念最近公共祖先（英语：lowest common ancestor）是指在一个树或者有向无环图中同时拥有v和w作为后代的最深的节点。在这里，我们定义一个节点也是其自己的后代，因此如果v是w的后代，那么w就是v和w的最近公共祖先。(fron wiki) 算法设计我们先来看看应该怎么解决此类问题。 一般思路在一个树上，我们定义离根节点最远的与a,b相同的祖先为最近公共祖先(LCA)。我们需要怎么做呢，首先肯定是 dfs 跑一遍，把所有的点的层次遍历出来，时间复杂度为 $O(N)$。一般情况下 $LCA$ 问题会有多次询问，询问次数一般为 $q<10^5$ ，那么就意味着我们不能在线性时间内去计算 $LCA$，如果采取最朴素的方法：选定2个点，若深度不一样则先转为深度一样，深度较深的点不停求它的父亲节点直到深度一样，然后用如下代码去求解。 1234567int LCA(int a,int b){ while(a!=b){ a=pre[a]; b=pre[b]; } r ...