Doraemon's Blog

A*算法在求一个点到目标点的最短距离时，可以加快速度，如果使用dijstla是nlogn的时复，但是A*更快，当节点足够多，边足够大时，可能不能求起点到所有点的最短距离，空间不够或者时复顶不住，这个时候A*或许能做，A使用了一个启发式函数f()，其含义是节点到终点的估计距离，这个距离可以是曼哈顿距离，可以是实际到终点的最短距离等等，只要满足*估计距离小于等于实际距离即可，只要满足了这个，那么用f(u)+dis(u)当作优先队列的排序规则，每次取出最小值，这个点的最短距离就确定了，证明我找不到，画个图可以想一下是有道理的 ACWing.178.第K短路 我看到这道题，不会A之前，我只能想到Knlogn的时复，跑K次dijstla…太菜了，其实更好的是使用BFS，给每一个状态加上一个距离，使用优先队列，每次取出距离最小的点，其实就是dijstla，只不过少了dis数组，这样子做如果不加优化空间和时间都顶不住，所以开一个cnt[]数组记录每一个点被更新了几次，如果一个点已经被更新K次了，之后这个点就没必要再入队了，加上这个优化后，时复和空间复杂度最坏就是Knlogn，但是这道题还是过不去 ...

最美子字符串的数目美丽的字符串定义为该字符串至多一个字母出现奇数次，给定一个字符串求该字符串包含多少个美丽的子串。（该字符串由前十个小写英文字母组成） 由于只会由前10个字母组成，所以可以把所有的字符当作一个二进制位，0表示该字符出现了偶数次，1代表字符出现了奇数次，那么现在好的状态就变成了0和2^i^，我们从前往后遍历字符串，求一个前缀异或状态，两个前缀异或起来即可得到一段区间的状态，那么问题就转化为了所有的位置前面有多少个状态和当前状态异或后是一个好的状态，如此我们就可以开一个数组cnt[i]记录从起始位置到当前位置i状态出现的次数，ans+=cnt[good^state]即是答案，good是一个好的状态，state是当前状态。 12345678910111213141516171819202122class Solution {public: long long wonderfulSubstrings(string word) { long long res=0; int cnt[1025]; memset(cnt,0,sizeof cnt); ...

AC自动机以trie为基础，结合了kmp的next数组思想而创造出来的一种数据结构，用来解决多模式串匹配问题 问题背景P3808 【模板】AC自动机（简单版） 给定n个模式串（$n<=1e6$），一个主串s（$s<=1e6$），问主串中包含多少个这些之中的模式串？ AC自动机传统做法，利用KMP，O(n)遍历每一个模式串，O(n)匹配是否包含此模式串，复杂度O(n2) 利用AC自动机，先把所有的模式串插入到trie中，接下来预处理一个fail数组，fail[i]表示i节点失配后该去找哪个节点（类似next数组），fail数组的真正含义是当前正在匹配的模式串的后缀和其他所有模式串的前缀可以匹配最大长度的那个模式串，有点绕。 这张图中的6号节点的fail指针指向7号节点，因为6号节点的后缀s和7号节点的前缀s相同，且匹配长度最大，所以fail[6]=7。 1234567891011121314151617181920queue<int> q;void build(){ //这里把根节点的儿子节点入队，因为如果只把根节点入队的话会导致根节点失配指 ...

Bellman-ford 用途： 判负环 计算含有负权边的最短路径 重边不会影响答案，因为Bellman-ford会遍历所有的边 算法流程先存边，Bellman-ford的存边十分随意，什么储存方式都可以，只有一个要求，就是每次都要遍历到所有的边！ 既然如此就用一个结构体去存，一个for循环就可以遍历到所有的边了。 123struct node{ int u,v,w}e[MAXN]; 算法十分简单，每次只要让所有的边进行一次更新即可，如果不存在负环，那么一个点最多被n-1个点更新(除了自己)，所以外层循环遍历n-1次，内层循环遍历每一条边 123456for(int i=1;i<n;i++){ for(int j=1;j<=m;j++){ int u=e[j].u,v=e[j].v,w=e[j].w; dis[v]=min(dis[v],dis[u]+w); }} 如果存在负环，那么经过上面的松弛操作后，一定还有点还可以被松弛，负环可以把环上点能到的所有点的权值都松弛到无限小，遍历所有点，检查 ...

数位DP 解决的是求一段区间中满足一定条件的数的数量，形式固定 数位DP模板123456789101112131415161718192021int num[100],dp[100][...];int dfs(int pos,int ...,bool limit) { if(pos==0) return ; if(!limit && dp[pos][...]!=-1) return dp[pos][...]; int up=limit?num[pos]:9; int sum=0; for(int i=0; i<=up; i++) { if(...) sum+=dfs(pos-1,...,limit && (i==up)); } if(!limit) dp[pos][...]=sum; return sum;}//ps 如果有前导0就可以加一个 lead,一开始传1，然后后面就传lead&&(i==0)就可以了int work(int x) { int len=0; while( ...

半平面交用于求几个凸包围成的面积 一条直线可以将平面分为两部分，我们取左半部分，右半部分舍弃，那么所有的直线围成的左半部分的面积的交集就是半平面交。 算法流程首先把所有线首先按照角度从小到大排序，角度相同就按照线从左到右排序，排序后用一个双端队列来维护，每次新进来一条边，判断这条边是否在队列的队尾两条边的交点左边，如果是，就把队尾元素pop出去，如此往复，队头也是如此，所有边遍历完后还要用队头去维护队尾，用队尾去维护队头 线点123456struct point{ double x,y;}pt[MAXN];struct line{ point a,b;}L[MAXN]; 函数思想很简单，但是实现很复杂，一点点错误满盘皆输，这8个函数非常有用 1234567891011121314151617181920212223242526272829point operator-(point a,point b){ //重载运算符 return {a.x-b.x,a.y-b.y};}double cross(po ...

ACWING 如果一条直线经过了所有线段，那么把这条直线旋转之后，边界就是卡在两个线段的端点处 那么就可以遍历每两个端点，判断这两个端点组成的直线是否穿过了所有的线段，如果是，则存在，不是继续找，找不到就不存在 如何判断一条直线是否经过了所有点呢？挨个判断这条线是否穿过线段 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970#include <bits/stdc++.h>//#pragma G++ optimize(2)//#pragma G++ optimize(3,"Ofast","inline")#define debug freopen("in.txt","r",stdin); freopen("out.txt","w",stdout)# ...

可持久化01字典树 作用：实现区间查询异或最大 时复：插入和查询都是O(logn) 算法流程先开一个内存池，动态开点，每次插入一个数都建一个根节点，从根节点拉出一条链，链上的节点一边连向上一个版本的节点，一边连向新插入的点，再开一个num数组表示每一个节点经过了几次，查询时当高版本的num值大于低版本的num值时表示在这个区间内有对应的值，走到最后直接返回即可 P4735 最大异或和 题意给定有初始值的n个数，m此操作，每次可以选择插入一个数或者查询一个区间内和给定的数异或最大是多少？ 题解 代码12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970#include <bits/stdc++.h>#define ios ios::sync_with_stdio(0); cin.tie(0); cout.tie(0)using namespace std;const i ...

01字典树 01字典树: 解决最大异或问题 和字典树一样，只不过每一个节点的值不再是字符而是01，一个数从高位到低位对应于字典树从根到叶子，一个数二进制有多少位，就应该建几层树，包含根节点的那个编号0 树上的每一个点都有各自的编号，节点有两条边，分别是0和1，开空间时应该多开40倍左右 HDU4825 Xor Sum题目链接 这道题数据有点水，说是不超过2^32^，其实连int都没有爆，应该开33层(包含根节点)，但是实际上32层就可以，代码是开了33层 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667#include <bits/stdc++.h>//#pragma G++ optimize(2)//#pragma G++ optimize(3,"Ofast","inline")#define debug freopen(" ...

11. 盛最多水的容器 题目所求即为最大面积，面积=(较短边*两线段距离)，答案即为max{以每一条线段作为较短边的最大面积}，当较短边确定时，两线段距离越长越好，因此考虑双指针从两端向内进行移动 考虑以下状态： 两指针在两端时，对于较短边而言，以此线段为较短边的最大面积就是线段长度乘以两指针位置之差，因此较短边对应的指针就可以向前或向后移动了。 移动后的状态又是以上状态。 因此每次较短边指针移动 12345678910111213141516class Solution { public: int maxArea(vector<int>& height) { int i = 0, j = height.size() - 1, res = 0; while(i < j) { res = max(res, min(height[i], height[j])*(j-i)); if(height[i] > height[j]) j -- ...