首页 > 编程语言 >2024/2/2 算法笔记

2024/2/2 算法笔记

时间：2024-02-02 12:23:12浏览次数：33  
标签：int ne void add 笔记 查询 2024 算法 ans

1. KMP

情景：给出一个母串和一个字串，求字串在母串中出现的所有位置。

我们定义子串s有一个border串，它是一个非s串的子串t，满足t既是s的前缀也是s的后缀

记住思想：退而求其次。

int ne[1000005];
void solve(){
    string s,t;//母串  匹配串
    cin>>s>>t;
    int n1 = s.length();
    int n2 = t.length();
    s = "?"+s;
    t = "?"+t;
    for(int i=2,j=0;i<=n2;i++){
        while(j&&t[i]!=t[j+1]) j = ne[j];
        if(t[i]==t[j+1]) j++;
        ne[i]=j;
    }
    for(int i=1,j=0;i<=n1;i++){
        while(j&&s[i]!=t[j+1])j=ne[j];
        if(s[i]==t[j+1])j++;
        if(j==n2) cout<<i-n2+1<<endl; //输出字串在母串中出现的位置
    }
    for(int i=1;i<=n2;i++) cout<<ne[i]<<" ";//输出s2的所有border串的长度
}

kmp的应用

  1. [P3435 POI2006] OKR-Periods of Words - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

    观察题面对周期的定义我们可以知道它和前后缀关系很紧密。

    母串S的一个前缀X，A=X+X能够令S为A的子串。所以我们知道这就是前后缀相同的另一种描述方法，很容易想到kmp对吧

    然后我们看要求是需要它这个X的长度尽量长，隐形要求就是令这个前缀尽量短。

    但是kmp是找的是S的每一个idx的最长匹配前缀，但是我们在找最长前缀的时候不是有一系列的ne[]（这个ne是越来越小的，是一种退而求其次的思想）嘛，所以我们的做法是：

    对于每一个idx，我们一直对他求ne，知道ne[j]为0的前一个ne[j]不就是最短匹配长度了嘛，另外，我们找到后，可以直接令ne[idx]=j，也就是记忆化的思想，后面找再退到这个位置，不就可以直接得到最短匹配了吗，也是一种优化方法。最后令ans+=i-j然后进入下一个idx，遍历完整个字符串就好了。

int ne[1000005];
void solve(){
    int n1;
    cin>>n1;
    string t;
    cin>>t;
    t = "?"+t;
    
    for(int i=2,j=0;i<=n1;i++){
        while(j&&t[i]!=t[j+1]) j = ne[j];
        if(t[i]==t[j+1]) j++;
        ne[i]=j;
    }
    //以上部分是求kmp做法中求ne数组的部分，和模板是一毛一样的。
    LL ans = 0;
    for(int i=2,j=2;i<=n1;i++,j=i){
        while(ne[j]) j = ne[j];//求最短匹配长度
        if(ne[i]) ne[i] = j;//修改ne[i]的值，当后面ne到这个i(指值)的时候，直接得出结果
        ans+=i-j;
    }
    cout<<ans<<endl;
}

2. 最短路

dijkstra方法： 结合链式向前星食用

可以有环 但是只能处理正权边

一开始将所有距离都设置为一个很大的值比如0x3f

P4779 【模板】单源最短路径（标准版） - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

void dijkstra(int x){
    // int a=1;
    // debug(a)
    memset(dist,0x3f,sizeof dist);
    memset(vis,0,sizeof vis);
    dist[x] = 0;
    priority_queue<PII,std::vector<PII>,greater<PII>>heap;
    heap.push({0,x});
    while(!heap.empty()){
        PII t = heap.top();
        heap.pop();
        int ver = t.ss,distance = t.ff;
        if(vis[ver]) continue;   //这个点已经访问过了
        vis[ver] = 1;   
        for(int i=h[ver];i;i = ne[i]){
            int j = e[i];
            if(dist[j] > distance+w[i]){   //关键部分
                dist[j] = distance + w[i];    //用短的路径覆盖长的路径
                if(!vis[j]){
                    heap.push({dist[j],j});
                }
            }
        }
    }

    for(int i =1;i<=n;i++){
        if(i==x) cout<<"0 ";
        else if(dist[i] == 0x3f3f3f3f) cout<<INT_MAX<<" ";
        else cout<<dist[i]<<" ";
    }
}

3. 树状数组

树状数组的作用：对一个区间的数修改及查询，内容有：单点修改，单点查询，区间修改，区间查询

本质上是利用位运算降低时间复杂度到nlogn

add和sum函数是固定的，查询和插入的方法是改变的。

//单点修改：
add(i,k) //i是位置  k是值
//区间修改：i,j
add(i,k);
add(j+1,-k);
//单点查询：k
sum(k);
//区间查询：i,j
sum(j)-sum(i-1);

int n,m;
int a[500005];
//lowbit(x) = x&-x

void add(int x,int num)
{
	for(;x<=n;x+=x&-x)
		a[x]+=num; 
}
int sum(int x)  //从下标1到 下标x的 和
{
	int ans=0;
	for(;x>0;x-=x&-x)
		ans+=a[x];
	return ans;
}


int main()
{
	cin>>n>>m;
	for(int i=1;i<=n;i++) 
	{
		int k;
		cin>>k;
		add(i,k);
	}
//	for(int i=1;i<=n;i++) cout<<a[i]<<" "; 测试代码
//	cout<<endl;
	while(m--)
	{
		int cho,x,y;
		cin>>cho>>x>>y;
		if(cho==1) add(x,y);
		else cout<<sum(y)-sum(x-1)<<endl;
	}
	return 0;
}

int n,m;
int a[500005],b[500005];

void add(int x,int num)
{
	for(;x<=n;x+=x&-x) b[x]+=num;
}

int sum(int x)
{
	int ans=0;
	for(;x>0;x-=x&-x) ans+=b[x];
	return ans;
}

int main()
{
	cin>>n>>m;
	for(int i=1;i<=n;i++) 
	{
		cin>>a[i];
//		b[i]=a[i]-a[i-1];
		add(i,a[i]-a[i-1]);
	}
	while(m--)
	{
		int cho,x,y,k;
		cin>>cho;
		if(cho==1) 
		{
			cin>>x>>y>>k;
			add(x,k);
			add(y+1,-k);
		}
		else 
		{
			int k;cin>>k;
//			int tmp=sum(k)-sum(k-1);
			cout<<sum(k)<<endl;
		}
	}
	return 0;
}

注意，单点修改+区间查询 和 区间查询+单点修改 所使用的是不一样的树状数组

前者使用的是前缀和的思想，修改的时候直接修改对应的值，查询的时候使用大范围减小范围得到一个区间的和

后者使用的是差分的思想，修改的时候使用区间修改的思想，查询到时候用前缀和的思想，因为sum就是前缀和的思想

但是为什么不直接用前缀和和差分呢？

因为它有最多n次查询，差分后查询每次还是需要至少n的复杂度的，这样会导致总复杂度为n2

一个方法就是如果是多次修改，最后一次查询，直接使用裸差分，

如果是多次的修改穿插查询，那么用树状数组吧。

另：区间修改+区间查询还是可以用树状数组的。

#include<iostream>
#include<cstdio>
#define MAXN 1000010
using namespace std;
int n,q,op,l,r,x;
int a[MAXN];
int c1[MAXN],c2[MAXN];
int lowbit(int x)
{
	return x&-x;
}
void update(int x,int k)
{
	int t=x;
	for(;x<=n;x+=lowbit(x))
	{
		c1[x]+=k;
		c2[x]+=k*(t-1);
	}
}
int query(int x)
{
	int ans=0,t=x;
	for(;x>=1;x-=lowbit(x))
		ans+=c1[x]*t-c2[x];
	return ans;
}
int main()
{
	scanf("%d%d",&n,&q);
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&a[i]);
		update(i,a[i]-a[i-1]);
	}
	for(int i=1;i<=q;i++)
	{
		scanf("%d%d%d",&op,&l,&r);
		if(op==1)
		{
			scanf("%d",&x);
			update(l,x);
			update(r+1,-x);
		}
		else
			printf("%d\n",query(r)-query(l-1));
	}
	return 0;
 }

另：有一个网上摘抄的树状数组解决逆序对的问题，但是还没有考证

[树状数组求逆序对 - wdvxdr - 博客园 (cnblogs.com)](https://www.cnblogs.com/wdvxdr/p/7300717.html#:~:text=树状数组就可以很好的做到这一点。 我们可以先开一个大小为a的最大值的数组t，每当读入一个数时，我们可以用桶排序的思想，将t [a [i]]加上1%2C然后我们统计t,~t [a [i]]的和ans，ans - 1（除掉这个数本身）就是在这个数前面有多少个数比它小。)

4. SPFA

这个算法可以处理负边权、负环的情况。

5. floyd

动态规划入门（

n3复杂度处理数量级为100的每个点对其他点的最短距离

也就是：任意点对的最短距离之和

[P2910 USACO08OPEN] Clear And Present Danger S - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

void floyd(){
    for(int k=1;k<=n;k++){
        for(int i=1;i<=n;i++){
            for(int j=1;j<=n;j++){
                mp[i][j] = min(mp[i][j],mp[i][k] + mp[k][j]);
            }
        }
    }
}

利用folyd可以扩展出的问题

1. 求传递闭包

B3611 【模板】传递闭包 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

void floyd(){
    for(int k=1;k<=n;k++){
        for(int i=1;i<=n;i++){
            for(int j=1;j<=n;j++){
                mp[i][j] |= mp[i][k] & mp[k][j];  
            }
        }
    }
}
/*
4
0 0 0 1
1 0 0 0
0 0 0 1
0 1 0 0
   |
   |
   v
1 1 0 1 
1 1 0 1 
1 1 0 1 
1 1 0 1
*/

2. 传送门：复杂度太高怎么办？

[P6464 传智杯 #2 决赛] 传送门 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

详见提交代码和题解。

标签：int,ne,void,add,笔记,查询,2024,算法,ans
From： https://www.cnblogs.com/Akimizuss101/p/18002963

相关文章

  • 2024.1.31题目选讲
    CF1753C首先求出整个数列有多少个0，设为sum0，再求出\(1--sum0\)中有多少个1，设为\(sum1\)显然，我们的目标就是把\(1--sum0\)中全部变成0那么考虑有意义的一步的期望次数，由于线性性，可以全部加起来设左边还有x个1（左边就是\(1--sum0\)）交换到的概率为\(\dfrac{x^2}{n(n+1)/2}\),那么......
  • R语言社区检测算法可视化网络图：ggplot2绘制igraph对象分析物种相对丰度
    原文链接：http://tecdat.cn/?p=23836原文出处：拓端数据部落公众号我们使用R中的igraph包，产生了网络的图形。但是很难将这些图表放到演讲和文章中，因为图表很难根据需要定制。使用igraph中的绘图功能可以得到你想要的结果，但用ggplot对工作更有帮助。所以本文探索了一种在ggplot中创......
  • 【2024.02.02】构图练习（糖水肖像）
    图源糖水日记作者的午饭饭，侵删采用摄影师泰罗所说的描绘法去观察每一张图的构图与线条可以观察到除非是夜景，一般来说感光度都会拉很低，避免噪点光圈值一般都会控制在2附近及以下，为了达到更好的的一个背景虚化效果说实话描绘了几张后感觉背景确实不是那么重要，只要控制好前景部分......
  • 京东广告算法架构体系建设--大规模稀疏场景高性能训练方案演变
    一、前言京东广告训练框架随着广告算法业务发展的特点也在快速迭代升级，回顾近几年大致经历了两次大版本的方案架构演变。第一阶段，随着2016年Tensorflow训练框架的开源，业界开始基于Tensorflow开源框架训练更复杂的模型。模型对特征规模和参数规模需求不断提升，大规模稀疏模型具有更......
  • 拉格朗日插值学习笔记
    拉格朗日插值定义给定一个多项式函数过点\((x_i,y_i)\)，求出这个多项式函数的在\(x=k\)时的取值。公式\[f(k)=\sum_{i=0}^ny_i\prod_{j\not=i}\dfrac{k-x_j}{x_i-x_j}\]时间复杂度\(O(n^2)\)横坐标连续的拉格朗日插值在横坐标连续的情况下，可以做到\(O(n)\)插值。\[\b......
  • 今天回顾-回溯算法-组合40
    注意点&感悟：还是得复习！！多巩固巩固，我可以的！！！！！题目链接：40.组合总和II自己独立写的代码：classSolution:defcombinationSum2(self,candidates:List[int],target:int)->List[List[int]]:res=[]candidates.sort()used=[0]*len(candi......
  • 萌新的多项式学习笔记（板子）
    萌新的多项式学习笔记（板子）详细讲解FFT直接放板子structcp{ doublex,y; cp(doublexx=0,doubleyy=0){x=xx,y=yy;}};intr[maxn];cpoperator+(constcp&a,constcp&b){returncp(a.x+b.x,a.y+b.y);}cpoperator-(constcp&a,constcp&b){returncp(a.x-b.x,a......
  • KubeSphere 社区双周报｜Fluent Bit 升级到 v2.2.2｜2024.01.18-02.01
    KubeSphere社区双周报主要整理展示新增的贡献者名单和证书、新增的讲师证书以及两周内提交过commit的贡献者，并对近期重要的PR进行解析，同时还包含了线上/线下活动和布道推广等一系列社区动态。本次双周报涵盖时间为：2024.01.18-02.01。贡献者名单新晋KubeSpherecontribut......
  • 2024年春节放假调休时间表，提前设置好补班日期提醒
    春节将至，期待已久的春节放假时间表也逐渐浮出水面。根据相关通知，2024年春节放假时间为2月10日（初一）至17日（初八），整整8天的长假，而为了照顾员工，还鼓励各单位为员工安排2月9日（除夕）的带薪休假。值得注意的是，春节调休时间为2月4日和2月18日，这两天将进行调休补班，大家务必准时上岗工作。这......
  • [学习笔记] JavaScript中字符串的Slice()方法
    slice方法是对字符串进行切割/截取的一种方法。string.slice(index1,index2)其中：string为字符串名；index1为数字，意为字符串从第X个字符开始截取，如为1，则从字符串第1个字符开始截取。同时该数可为负数，当设为负数时则是从倒数第X个字符开始截取（但仍旧是向最后一个字符的方......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99