2016-03-24 22:07:19 cadongllas 阅读数 700
  • 30天c++leetcode算法训练

    作为要准备踏入码农行业的人来说,怎么能不去刷刷LeetCode呢?LeetCode收录了许多互联网公司、IT企业的笔试题目,被称为刷题神器。同样的,不少非计算机专业的科班出身的学员朋友,做的编程还是挺多的,在编程过程中或多或少觉得自己的“野路子”实在太多,有时不仅写得煎熬,而且书写很多时候都非常不规范。因此,学习、借鉴、模仿高手的代码套路,不仅仅有助于提升职业技能,更进一步的也能增加自己求职的底气和心气。Leetcode是面向职场就业的,而非追求高度思维技巧的ACM竞赛,特别是LeetCode的基础题目并不多,目前大概有358道,而且其题型都非常简单明了,并不需要的复杂的理解,一般都在50行左右就可以解决。这有助于广大的求职朋友建立自信,提升技能。本门课程分类精选了30道题目,从vs code刷题环境搭建起手,手把手的进行了课程引导,以期能帮助广大求职人员,积累知识,提升技能,不过有些题是加锁的,好像有付费才能使用,能做的题应该有150多道吧,这也是完全足够了。   另外,如果你写了上百行代码,就肯定说明你想太多了或太复杂,虽然都能用很短的代码就能解决,但并不意味着LeetCode的题目非常简单,实际上LeetCode基本上涉及到了所有常规的算法类型。   关于LeetCode的刷题时间:个人认为大概是要一个月左右,如果你是大神的话,也许大概能在两到三个星期间刷 完,不过做为新手,除了埋头做题,更重要的是去讨论区看看别人的代码或思路。一道一道刷题虽然速度慢了点,不过会学到了许多。为了帮助广大学员朋友切实提升程序开发技巧,积累学习信心,克服畏难情绪,丁宋涛和夏曹俊老师共同精心设计了本门课程。希望通过本门课程可以分享知识,掌握技能。

    3571 人正在学习 去看看 夏曹俊

给队友写的,顺便自己总结一下

本文总结了基础的acm所能用到的数据结构

省略了栈,队列,并查集等基础知识


RMQ

优点:编写复杂度低,不容易错。倍增的思想非常好

缺点:不支持修改操作,用处小

初级题目见课件

进阶题目推荐 HDU5289

树状数组

一个看起来很简单但是实际上用处十分大的数据结构,编写难度小于线段树,但是很多情况可以替代线段树,性价比十分高

更好的是,在同样的做法下,线段树往往比树状数组慢

初级入门本文不在赘述

进阶题目推荐:poj 3468 (本来是线段树的题目,但是最快的程序都是树状数组)

线段树

超级无敌的题目,当时高一学线段树走了许多弯路,因为线段树有太多种的写法,每看一个标程就会多一种写法,就会更加迷茫,所以推荐的做法是:找一个最好的标称学会写线段树,然后就不再看其他写法,能省很多时间

初级经典题目:poj 2777

进阶题目: poj 3468 (本题AC后可以初步理解标记的作用)

终极题目:poj 1177 (初学者不建议尝试,特别浪费时间)

因为线段树写法太多,本文贴出自己的写法,以供指导

<span style="font-size:14px;">#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#define intt long long
#define rep(i, j, k) for(int i = j; i <= k; i++)

using namespace std;

int m, a[100009];
intt n, l[2000009], r[2000009], add[2000009], sum[2000009];

void build (int x, intt L, intt R)
{
	l[x] = L, r[x] = R;
	if (L == R)
	{
		sum[x] = a[L];
		add[x] = 0;
		return;
	}
	intt mid = (L + R) >> 1;
	build (2 * x, L, mid);
	build (2 * x + 1,mid + 1, R);
	sum[x] = sum[2 * x] + sum[2 * x + 1];
	add[x] = 0;
	return;
}

intt ask (int x, intt L, intt R)
{
	if (L > r[x] || R < l[x])
		return 0;
	if (L <= l[x] && r[x] <= R)
		return sum[x] + add[x] * (r[x] - l[x] + 1);
	add[2 * x] += add[x];
	add[2 * x + 1] += add[x];
	add[x] = 0;
	sum[x] = sum[2 * x] + add[2 * x] * ( r[2 * x] - l[2 * x] + 1) + sum[2 * x + 1] + add[2 * x + 1] * (r[2 * x + 1] - l[2 * x + 1] + 1);
	return ask (2 * x, L, R) + ask (2 * x + 1, L, R);
}

void Add (int x, intt L, intt R, intt num)
{
	if (L > r[x] || R < l[x])
		return;
	if (L <= l[x] && r[x] <= R)
	{
		add[x] += num;
		return;
	}
	add[2 * x] += add[x];
	add[2 * x + 1] += add[x];
	add[x] = 0;
	Add (2 * x, L, R, num);
	Add (2 * x + 1, L, R, num);
	sum[x] = sum[2 * x] + add[2 * x] * ( r[2 * x] - l[2 * x] + 1) + sum[2 * x + 1] + add[2 * x + 1] * (r[2 * x + 1] - l[2 * x + 1] + 1);
	return;
}

int main()
{
	while (scanf ("%lld%d", &n, &m) == 2 && n != 0)
	{
		rep (i, 1, n)
			scanf ("%d", &a[i]);
		build (1, 1, n);
		while (m--)
		{
			getchar ();
			char ch;
			scanf ("%c", &ch);
			if (ch == 'Q')
			{
				intt x, y;
				scanf ("%lld%lld", &x, &y);
				printf ("%lld\n", ask (1, x, y));
			}
			else
			{
				intt x, y, z;
				scanf ("%lld%lld%lld", &x, &y, &z);
				Add (1, x, y, z);
			}
		}
	}
	return 0;
}</span>

平衡树

平衡树的写法有很多,种类也很多,最有名的当然是红黑树一类的,但是实际竞赛中从来不会考这些东西,因为这么多中的平衡树的作用差不多,只有常数的差别,比如SBT非常难写,以此换取了常数上的优化,然后,很多时候只要保证复杂度,常数并不需要太过纠结,本人最喜欢的就是splay,因为splay功能非常强大,虽然常数十分大,但是大多数时候是足够使用的,所以建议初学者先掌握splay ,而treap之类的可以暂且不管,高中时在学习各种平衡树上浪费了大量时间,希望后来的人吸取我的教训


字符串数据结构

Trie

传说中的字母树,写法不难。巴蜀的课件中有详解

AC自动机

也不难理解,训练指南中已经讲的非常好了

后缀数组

本人曾经会过现在忘了。。这个确实麻烦。。留个坑吧。。


本文仅仅是学习的提纲而已,具体学习还要看个人,本人认为最好的方法就是先看巴蜀的课件和刘汝佳的算法竞赛入门经典训练指南入门,然后找对应的poj入门习题做,然后加大题量以达到十分熟悉的水平。

总体来说,初级的数据结构就这么多,个人认为线段树是最重要的,一定要深入理解,多做练习。

2018-04-10 10:57:32 zzti_xiaowei 阅读数 689
  • 30天c++leetcode算法训练

    作为要准备踏入码农行业的人来说,怎么能不去刷刷LeetCode呢?LeetCode收录了许多互联网公司、IT企业的笔试题目,被称为刷题神器。同样的,不少非计算机专业的科班出身的学员朋友,做的编程还是挺多的,在编程过程中或多或少觉得自己的“野路子”实在太多,有时不仅写得煎熬,而且书写很多时候都非常不规范。因此,学习、借鉴、模仿高手的代码套路,不仅仅有助于提升职业技能,更进一步的也能增加自己求职的底气和心气。Leetcode是面向职场就业的,而非追求高度思维技巧的ACM竞赛,特别是LeetCode的基础题目并不多,目前大概有358道,而且其题型都非常简单明了,并不需要的复杂的理解,一般都在50行左右就可以解决。这有助于广大的求职朋友建立自信,提升技能。本门课程分类精选了30道题目,从vs code刷题环境搭建起手,手把手的进行了课程引导,以期能帮助广大求职人员,积累知识,提升技能,不过有些题是加锁的,好像有付费才能使用,能做的题应该有150多道吧,这也是完全足够了。   另外,如果你写了上百行代码,就肯定说明你想太多了或太复杂,虽然都能用很短的代码就能解决,但并不意味着LeetCode的题目非常简单,实际上LeetCode基本上涉及到了所有常规的算法类型。   关于LeetCode的刷题时间:个人认为大概是要一个月左右,如果你是大神的话,也许大概能在两到三个星期间刷 完,不过做为新手,除了埋头做题,更重要的是去讨论区看看别人的代码或思路。一道一道刷题虽然速度慢了点,不过会学到了许多。为了帮助广大学员朋友切实提升程序开发技巧,积累学习信心,克服畏难情绪,丁宋涛和夏曹俊老师共同精心设计了本门课程。希望通过本门课程可以分享知识,掌握技能。

    3571 人正在学习 去看看 夏曹俊
  • 并查集
  • KMP算法
  • 树状数组
  • 线段树
  • 莫队算法

1、并查集

描述: 一种用来管理元素分组情况的数据结构。并查集可以高效的进行如下操作:

  • 查询元素a和元素b是否属于同一个数组。
  • 合并元素a和元素b所在的组。

代码:

// 并查集
int par[Max_n];  //父亲
int rank[Max_n]; //树的高度

void init(int n){ //初始化n个元素
    for(int i=0;i<n;i++){
        par[i]=i;
        rank[i]=0;
    }
}

int find(int x){ //查询树的根(路径压缩)
    if(par[x]==x)return x;
    return par[x]=find(par[x]);
}

int find(int x){ //非递归写法
    int p,t;
    p=x;
    while(x!=par[x])x=par[x];
    while(p!=x){
        t=par[p];
        par[p]=x;
        p=t;
    }
    return x;
}

void unite(int x,int y){ //合并x和y所属的集合(按秩归并)
    x=find(x);
    y=find(y);
    if(x==y)return;
    if(rank[x]<rank[y])par[x]=y;
    else par[y]=x;
    if(rank[x]==rank[y])rank[x]++;
}

**复杂度:**加入优化后效率非常高,对n个元素的元素进行一次操作的复杂度是O(α(n)),比O(logn)还要快。

2、KMP算法

描述: KMP算法是一种改进的字符串匹配算法,是利用匹配失败后的信息,尽量减少模式串与主串的匹配次数以达到快速匹配的目的,时间复杂度O(m+n)。

  • pmt数组记录的是字符串前缀集合和后缀集合的最长匹配。为了编程的方便,不直接使用pmt数组,而pmt数组向后偏移一位得到next数组。即next数组 记录的是主串字符与模式串字符失配时,主串应与模式串的第next[j]个字符再进行比较。

代码:

next是C++中的保留字,使用next数组,会CE!

char s[Max_n],t[Max_n];
int next[Max_n];
int slen,tlen;

void getNext(){ //next数组
    int i=0,j=-1;
    next[0]=-1;
    while(i<tlen){
        if(j==-1||t[i]==t[j]){
            i++;j++;
            next[i]=j;
        }
        else j=next[j];
    }
}

void getNext2(){ //优化的next数组
    int i=0,j=-1;
    next[0]=-1;
    while(i<tlen){
        if(j==-1||t[i]==t[j]){
            i++;j++;
            if(t[i]==t[j])next[i]=next[j];
            else next[i]=j;
        }
        else j=next[j];
    }
}

int kmp_index(){ //返回模式串T在主串S中首次出现的位置
    int i=0,j=0;
    getNext();
    while(i<slen&&j<tlen){
        if(j==-1||s[i]==t[j]){
            i++;j++;
        }
        else j=next[j];
    }
    if(j==tlen)return i-j;
    else return -1;
}

int kmp_count(){ //返回模式串在主串S中出现的次数
    int i=0,j=0,k=0;
    getNext();
    while(i<slen){
        if(j==-1||s[i]==t[j]){
            i++;j++;
        }
        else j=next[j];
        if(j==tlen){
            k++;
            j=next[j];
        }
    }
    return k;
}

// KMP求最小循环节、循环周期

定理:假设S的长度为len,则S存在最小循环节,循环节的长度L为len-next[len],子串为S[0…len-next[len]-1]。
(1)如果len可以被len - next[len]整除,则表明字符串S可以完全由循环节循环组成,循环周期T=len/L。
(2)如果不能,说明还需要再添加几个字母才能补全。需要补的个数是循环个数L-len%L=L-(len-L)%L=L-next[len]%L。
 
简单理解:
对于字符串abcd abcd abcd,由长度为4的字符串abcd重复3次得到,那么必然有原字符串的前八位等于后八位。
也就是说,对于某个字符串S,由长度为L的字符串s重复R次得到,当R≥2时必有S[0..len-L-1]=S[L..len-1](下标从0开始)
那么对于KMP算法来说,就有next[len]=len-L。此时L肯定已经是最小的。
(因为next的值是前缀和后缀相等的最大长度,即len-L是最大的,那么在len已经确定的情况下,L是最小的)。

next数组和优化后的next2数组:
在这里插入图片描述

3、树状数组

描述: 树状数组用来维护数组的前缀和,从而可以快速求得某一个区间的和,并支持对元素的值进行修改。但是树状数组并非只有这一种功能,变形后它还能衍生出两个功能,本文我们就来分别讨论下树状数组这三大功能。

永远要记住,基本的树状数组维护的是数组的前缀和,所有的区间求值都可以转化成用 sum[m]-sum[n-1] 来解,这点无论是在改点还是接下来要说的改段中都非常重要!

1.改点求段(单点修改 区间查询)

这也是树状数组的基本应用。我们可以来看一下这道题 敌兵布阵
代码:

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long ll;
const int Max_n=1e5+10;

int t,n,k=0;
int c[Max_n];

int lowbit(int k){
    return k&-k;
}

void update(int k,int val){
    while(k<=n){
        c[k]+=val;
        k+=lowbit(k);
    }
}

int sum(int k){
    int ans=0;
    while(k>0){
        ans+=c[k];
        k-=lowbit(k);
    }
    return ans;
}

int main()
{
    scanf("%d",&t);
    while(t--){
        scanf("%d",&n);
        int a,b;
        char s[10];
        memset(c,0,sizeof(c));
        for(int i=1;i<=n;i++){
            scanf("%d",&a);
            update(i,a);
        }
        printf("Case %d:\n",++k);
        while(~scanf("%s",s)&&s[0]!='E'){
            if(s[0]=='Q'){
                scanf("%d%d",&a,&b);
                printf("%d\n",sum(b)-sum(a-1));
            }
            else if(s[0]=='A'){
                scanf("%d%d",&a,&b);
                update(a,b);
            }
            else {
                scanf("%d%d",&a,&b);
                update(a,-b);
            }
        }
    }
    return 0;
}

2.改段求点(区间修改 单点查询)

改段求点和改点求段恰好相反,比如有一个数组 a = [x, 0, 0, 0, 0, 0, 0, 0, 0, 0],每次的修改都是一段,比如让 a[1]~a[5] 中每个元素都加上10,让 a[6]~a[9] 中每个元素都减去2,求任意的元素的值。

看例题: Color the ball

跟改点求段不同,这里要转变一个思想。在改点求段中,c[i]表示Ci节点所管辖的子节点的元素和,而在改段求点中,c[i]表示Ci所管辖子节点的批量统一增量。

还是看这个经典的图:
这里写图片描述
比方说,C8管辖A1A8这8个节点,如果A1A8每个都染色一次,因为前面说了c[i]表示i所管辖子节点的统一增量,那么也就是 c[8]+=1,A5~A7都染色两次,也就是 c[6] +=2, c[7] +=2 。如果要求A1被染色的次数,C8是能管辖到A1的,也就是说c[8]的值和A1被染色的次数有关,仔细想想,也就是把能管辖到A1的父节点的c值累积起来即可。两个过程正好和改点求段相反。

代码:

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long ll;
const int Max_n=1e5+10;

int n;
int c[Max_n];

int lowbit(int k){
    return k&-k;
}

void update(int k,int val){
    while(k>0){
        c[k]+=val;
        k-=lowbit(k);
    }
}

int query(int k){
    int ans=0;
    while(k<=n){
        ans+=c[k];
        k+=lowbit(k);
    }
    return ans;
}

int main()
{
    while(~scanf("%d",&n)&n){
        memset(c,0,sizeof(c));
        int a,b;
        for(int i=0;i<n;i++){
            scanf("%d%d",&a,&b);
            update(a-1,-1);update(b,1);
        }
        printf("%d",query(1));
        for(int i=2;i<=n;i++)
            printf(" %d",query(i));
        putchar('\n');
    }

    return 0;
}

3.改段求段(区间修改 区间查询)

改段求段也有道经典的模板题:A Simple Problem with Integers

我们还是从简单的例子入手,比如有数组a[10]={1,2,3…9}。

假设我们将 a[1]~a[4] 这段增加5,对于我们要求的区间和来说,要么是 [1,2] 这种属于所改段的子区间,要么是 [1,8] 这种属于所改段的父区间(前面说了,所有的区间求值都可以用sum[m]-sum[n-1]来解,所以我们只考虑前缀和),我们分别讨论。

1)如果所求是类似 [1,8] 这种,我们可以很开心地发现,我们将区间增量(4*5)全部加在 a[4] 这个元素上,对结果并没有什么影响!于是变成了一般的改点求段

2)如果所求是类似 [1,2] 这种,我们可以用类似改段求点中染色的思想进行处理。譬如 [1,4] 成段加5,如果我们要计算 [1,2] 的和。我们将 [1,3] 进行“染色”(节点4加上了4*5的权重),因为 [1,3] 在树状数组的划分中可以分为两个区间,[1,2] 和 [3,3],所以我们用类似改段求点对这两块区域进行“染色”,染上的次数为5。我们要求的是 [1,2] 的区间和,我们只需找 2 被染色的次数,因为 [1,n] 进行染色。如果m(1<=m<=n)被染色,那么m的左边肯定都被染色了。求出被染色的次数,然后乘上区间宽度,就是整段的和了。

这样我们分别对两种情况进行了处理,更重要的是,这两种情况互不影响!于是我们简单地把两个结果相加就ok了,而这两个过程,分别正是改点求段和改段求点!

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long ll;
const int Max_n=1e5+10;

int N,Q;
ll b[Max_n],c[Max_n];

int lowbit(int k){
    return k&-k;
}

void update_backward(int k,int val){ 
    while(k<=N){
        b[k]+=val;
        k+=lowbit(k);
    }
}

void update_forward(int k,int val){ 
    while(k>0){
        c[k]+=val;
        k-=lowbit(k);
    }
}

void update(int k,int val){
    update_backward(k,k*val);
    update_forward(k-1,val);
}

ll query_forward(int k){
    ll ans=0;
    while(k>0){
        ans+=b[k];
        k-=lowbit(k);
    }
    return ans;
}

ll query_backward(int k){
    ll ans=0;
    while(k<=N){
        ans+=c[k];
        k+=lowbit(k);
    }
    return ans;
}

ll query(int k){
    return query_forward(k)+k*query_backward(k);
}

int main()
{
    scanf("%d%d",&N,&Q);
    int x,y,z;
    char s[10];
    memset(b,0,sizeof(b));
    memset(c,0,sizeof(c));
    N+=1;  //下标2~n+1
    for(int i=2;i<=N;i++){
        scanf("%d",&x);
        update_backward(i,x);
    }
    for(int i=0;i<Q;i++){
        scanf("%s",s);
        if(s[0]=='Q'){
            scanf("%d%d",&x,&y);
            x++;y++;
            printf("%lld\n",query(y)-query(x-1));
        }
        else {
            scanf("%d%d%d",&x,&y,&z);
            x++;y++;
            update(y,z);
            update(x-1,-z);
        }
    }
    return 0;
}

注意: 一般的用数组来解的题,都是不用a[0]的,也就是元素是从a[1]~a[n]。而本题中的改段求段中的元素是从 a[2]~a[n+1],因为 update()更新区间[1,x](x为任意值)时,左端点为0向后更新update_backward会造成死循环!

// 支持本小节树状数组原创作者:韩子迟,十分感谢~~

4、线段树

描述: 是一种树状结构来存储一个连续区间的信息的数据结构。线段树是平衡二叉树,所有操作都是logn级别,每个节点对应一个区间。关键的一点:需要维护哪些区间的附件信息,怎样维护这个信息。

代码风格:

  1. 数组要开节点数Max_n的4倍,详见证明,lson和rson分别代表当前节点的左右儿子。
  2. 函数传参时,同时传递当前儿子的节点rt和对应的区间[l,r]。
  3. pushUP(int rt) 把当前结点的信息更新给父结点。
    pushDown(int rt) 把当前结点的信息更新给儿子结点。
  4. 线段树维护的区间范围是[1,x],根节点从1开始(1,2,3…)!!!

hdu-1166 敌兵布阵

  • 简单的单点修改,区间查询
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
const int Max_n=5e4+10;

int tree[Max_n<<2];

void pushUp(int rt){
	tree[rt]=tree[rt<<1]+tree[rt<<1|1];
}

void build(int l,int r,int rt){
	if(l==r){
		scanf("%d",&tree[rt]);
		return;
	}
	int m=(l+r)>>1;
	build(lson);build(rson);
	pushUp(rt);
}

void update(int k,int value,int l,int r,int rt){ //单点更新 
	if(l==r){
		tree[rt]+=value;
		return;
	} 
	int m=(l+r)>>1;
	if(k<=m)update(k,value,lson);
	else update(k,value,rson);
	pushUp(rt);
} 

int query(int L,int R,int l,int r,int rt){
	if(r<=R&&l>=L)return tree[rt];
	int ans=0;
	int m=(l+r)>>1;
	if(L<=m)ans+=query(L,R,lson);
	if(R>=m+1)ans+=query(L,R,rson);
	return ans; 
}

int main()
{
	int T,n;
	scanf("%d",&T);
	for(int i=1;i<=T;i++){
		printf("Case %d:\n",i);
		scanf("%d",&n); 
		build(1,n,1);
		char s[110];
		int x,y;
		while(~scanf("%s",s)&&s[0]!='E'){
			scanf("%d%d",&x,&y);
			if(s[0]=='A')update(x,y,1,n,1);
			else if(s[0]=='S')update(x,-y,1,n,1);
			else printf("%d\n",query(x,y,1,n,1));
		}
	}
	return 0;
}

poj 3468 A Simple Problem with Integers

  • 区间修改,区间查询(lazy标记)
  • lazy标记思想:更新到某个区间的时候,先给这个区间打上lazy标记,不去更新子区间。当下一次更新子区间的时候再把该区间的lazy标记更新到子区间。从而避免浪费更新那些不必要的结点的时间。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
using namespace std; 
typedef long long ll;
const int Max_n=1e5+10;

int s[Max_n];
ll sum[Max_n<<2];
int lazy[Max_n<<2];

void pushUp(int rt){
	sum[rt]=sum[rt<<1]+sum[rt<<1|1];
}

void pushDown(int rt,int len){
	if(lazy[rt]){
		lazy[rt<<1]+=lazy[rt];
		lazy[rt<<1|1]+=lazy[rt];
		sum[rt<<1]+=(len-(len>>1))*lazy[rt];
		sum[rt<<1|1]+=(len>>1)*lazy[rt];
		lazy[rt]=0;
	}
}

void build(int l,int r,int rt){
	lazy[rt]=0;
	if(l==r){
		sum[rt]=s[l];
		return;
	}
	int m=(l+r)>>1;
	build(lson);build(rson);
	pushUp(rt);
}

void update(int L,int R,int c,int l,int r,int rt){
	if(l>=L&&r<=R){
		lazy[rt]+=c;
		sum[rt]+=(ll)c*(r-l+1);
		return;
	}
	int m=(l+r)>>1;
	pushDown(rt,r-l+1);
	if(L<=m)update(L,R,c,lson);
	if(R>=m+1)update(L,R,c,rson);
	pushUp(rt);
}

ll query(int L,int R,int l,int r,int rt){
	if(l>=L&&r<=R)return sum[rt];
	pushDown(rt,r-l+1);
	int m=(l+r)>>1;
	ll ans=0;
	if(L<=m)ans+=query(L,R,lson);
	if(R>=m+1)ans+=query(L,R,rson);
	return ans;
}

int main()
{
	int n,t;
	scanf("%d%d",&n,&t);
	for(int i=1;i<=n;i++)scanf("%d",&s[i]);
	build(1,n,1);
	char ch;
	int x,y,z;
	while(t--){
		cout<<t<<'&'<<endl;
		scanf("%c",&ch);
		if(ch=='Q'){
			scanf("%d%d",&x,&y);
			printf("%lld\n",query(x,y,1,n,1));
		} 
		else {
			scanf("%d%d%d",&x,&y,&z);
			update(x,y,z,1,n,1);
		}
	}
	
	return 0;
}

5、莫队算法

描述: 一种优雅的暴力,离线处理一类区间不修改查询类问题的算法。通过预先知道所有的询问,合理的组织每个询问的顺序以此来降低复杂度。
复杂度: O(n*√n)

















































66666666666666666666666666

2019-05-08 22:45:31 qq_43627086 阅读数 87
  • 30天c++leetcode算法训练

    作为要准备踏入码农行业的人来说,怎么能不去刷刷LeetCode呢?LeetCode收录了许多互联网公司、IT企业的笔试题目,被称为刷题神器。同样的,不少非计算机专业的科班出身的学员朋友,做的编程还是挺多的,在编程过程中或多或少觉得自己的“野路子”实在太多,有时不仅写得煎熬,而且书写很多时候都非常不规范。因此,学习、借鉴、模仿高手的代码套路,不仅仅有助于提升职业技能,更进一步的也能增加自己求职的底气和心气。Leetcode是面向职场就业的,而非追求高度思维技巧的ACM竞赛,特别是LeetCode的基础题目并不多,目前大概有358道,而且其题型都非常简单明了,并不需要的复杂的理解,一般都在50行左右就可以解决。这有助于广大的求职朋友建立自信,提升技能。本门课程分类精选了30道题目,从vs code刷题环境搭建起手,手把手的进行了课程引导,以期能帮助广大求职人员,积累知识,提升技能,不过有些题是加锁的,好像有付费才能使用,能做的题应该有150多道吧,这也是完全足够了。   另外,如果你写了上百行代码,就肯定说明你想太多了或太复杂,虽然都能用很短的代码就能解决,但并不意味着LeetCode的题目非常简单,实际上LeetCode基本上涉及到了所有常规的算法类型。   关于LeetCode的刷题时间:个人认为大概是要一个月左右,如果你是大神的话,也许大概能在两到三个星期间刷 完,不过做为新手,除了埋头做题,更重要的是去讨论区看看别人的代码或思路。一道一道刷题虽然速度慢了点,不过会学到了许多。为了帮助广大学员朋友切实提升程序开发技巧,积累学习信心,克服畏难情绪,丁宋涛和夏曹俊老师共同精心设计了本门课程。希望通过本门课程可以分享知识,掌握技能。

    3571 人正在学习 去看看 夏曹俊

数据结构在acm课刚开始的时候已经大体学习过。以下是数据结构的小部分内容。
栈:栈是只能在某一端插入和删除的特殊线性表。
进行删除和插入的一端称栈顶,另一堆称栈底。插入一般称为进栈(PUSH),删除则称为退栈(POP)。 栈也称为后进先出表(LIFO表)。
一个栈可以用定长为N的数组S来表示,用一个栈指针TOP指向栈顶。若TOP=0,表示栈空,TOP=N时栈满。进栈时TOP加1。退栈时TOP减1。当TOP<0时为下溢。栈指针在运算中永远指向栈顶。
队列: 队列是限定在一端进行插入,另一端进行删除特殊线性表。
队列的删除和插入分别称为出队和入队。允许出队的一端称为队头,允许入队的一端称为队尾。 由于总是先入队的元素先出队(先排队的人先买完东西),这种表也称为先进先出(FIFO)表。
队列可以用数组Q[m+1]来存储,数组的上界m即是队列所容许的最大容量。在队列的运算中需设两个指针:
head:队头指针,指向实际队头元素的前一个位置
tail:队尾指针,指向实际队尾元素所在的位置。

2019-05-15 20:38:50 UnKfrozen 阅读数 54
  • 30天c++leetcode算法训练

    作为要准备踏入码农行业的人来说,怎么能不去刷刷LeetCode呢?LeetCode收录了许多互联网公司、IT企业的笔试题目,被称为刷题神器。同样的,不少非计算机专业的科班出身的学员朋友,做的编程还是挺多的,在编程过程中或多或少觉得自己的“野路子”实在太多,有时不仅写得煎熬,而且书写很多时候都非常不规范。因此,学习、借鉴、模仿高手的代码套路,不仅仅有助于提升职业技能,更进一步的也能增加自己求职的底气和心气。Leetcode是面向职场就业的,而非追求高度思维技巧的ACM竞赛,特别是LeetCode的基础题目并不多,目前大概有358道,而且其题型都非常简单明了,并不需要的复杂的理解,一般都在50行左右就可以解决。这有助于广大的求职朋友建立自信,提升技能。本门课程分类精选了30道题目,从vs code刷题环境搭建起手,手把手的进行了课程引导,以期能帮助广大求职人员,积累知识,提升技能,不过有些题是加锁的,好像有付费才能使用,能做的题应该有150多道吧,这也是完全足够了。   另外,如果你写了上百行代码,就肯定说明你想太多了或太复杂,虽然都能用很短的代码就能解决,但并不意味着LeetCode的题目非常简单,实际上LeetCode基本上涉及到了所有常规的算法类型。   关于LeetCode的刷题时间:个人认为大概是要一个月左右,如果你是大神的话,也许大概能在两到三个星期间刷 完,不过做为新手,除了埋头做题,更重要的是去讨论区看看别人的代码或思路。一道一道刷题虽然速度慢了点,不过会学到了许多。为了帮助广大学员朋友切实提升程序开发技巧,积累学习信心,克服畏难情绪,丁宋涛和夏曹俊老师共同精心设计了本门课程。希望通过本门课程可以分享知识,掌握技能。

    3571 人正在学习 去看看 夏曹俊

引例

洛谷P3865
RMQRMQ的中文翻译为:静态区间最值查询.英文我不知道所以不写给你nn个数,mm次查询,查询的内容为区间[l,r]中的最大值.
RMQRMQ有解法蛮多的,st表,线段树,树状数组,划分树都可以做.
stst表的复杂度为预处理O(nlog2n)O(n*\log_2 n)+查询O(m)O(m)
而线段树则需要预处理O(nlog2n)O(n*\log_2 n)+查询O(mlog2n)O(m*\log_2 n)
树状数组没学,不清楚
线段树可以看我之前的博客.

定义

这个算法就是基于DPDP和位运算符,我们用dp[i][j]dp[i][j]表示从第 ii 位开始,到第 i+2j1i + 2^j -1 位的最大值或者最小值。

那么我求dp[i][j]dp[i][j]的时候可以把它分成两部分,第一部分从 iii+2(j1)1i + 2 ^{(j-1)} - 1 ,第二部分从 i+2(j1)i + 2 ^{(j-1)}i+2j1i + 2^j- 1,那么可以得到
dp[i][j]=max(dp[i][j1],dp[i+(1&lt;&lt;(j1))][j1])dp[i][j]=max(dp[i][j-1],dp[i+(1&lt;&lt;(j-1))][j-1])
j=0j=0时,求的是长度为1的区间的最小值,
j=1j=1时,求的是长度为2的区间最小值
j=2j=2时,求的是长度为4的区间最小值
以此类推,故可在O(nlog2n)O(n\log_2 n)的复杂度处理完.
如图所示
1
查询的话,只需要反过来就阔以了.

完整代码

这里mm[i] = mm[i - 1] +((i&(i - 1)) == 0);只有在这里预处理后,才能真正做到查询O(1)O(1).

const int MAXN = 1e5 + 10;

int dp[MAXN][31],a[MAXN],mm[MAXN];

void initRMQ(int n)
{
	mm[0] = -1;
	for (int i = 1; i <= n; i++) {
		mm[i] = mm[i - 1] +((i&(i - 1)) == 0);
		dp[i][0] = a[i];
	}
	for (int j = 1; j <= mm[n]; j++)
		for (int i = 1; i + (1 << j) - 1 <= n; i++)
			dp[i][j] = max(dp[i][j - 1], dp[i + (1 << (j - 1))][j - 1]);
}

int rmq(int x, int y)
{
	int k = mm[y - x + 1];
	return max(dp[x][k], dp[y - (1 << k) + 1][k]);
}

int main()
{
	int n,m;
	cin >> n >> m;//scanf("%d", &n);
	for (int i = 1; i <= n; i++)
		cin >> a[i];

	initRMQ(n);

	while (m--) {
		int x, y;
		cin >> x >> y;
		cout << rmq(x, y) << '\n';
	}
	return 0;
}

二维st表

暂存
https://blog.csdn.net/VictoryCzt/article/details/83684082

约束RMQ

https://www.cnblogs.com/ghostcai/p/9280720.html
https://blog.csdn.net/VictoryCzt/article/details/83348579

练习题目

洛谷P2251
裸的RMQRMQ问题
洛谷P3865
stst表模板题目
洛谷P2048
stst表+前缀和+贪心+堆优化

2019-05-15 17:16:37 UnKfrozen 阅读数 45
  • 30天c++leetcode算法训练

    作为要准备踏入码农行业的人来说,怎么能不去刷刷LeetCode呢?LeetCode收录了许多互联网公司、IT企业的笔试题目,被称为刷题神器。同样的,不少非计算机专业的科班出身的学员朋友,做的编程还是挺多的,在编程过程中或多或少觉得自己的“野路子”实在太多,有时不仅写得煎熬,而且书写很多时候都非常不规范。因此,学习、借鉴、模仿高手的代码套路,不仅仅有助于提升职业技能,更进一步的也能增加自己求职的底气和心气。Leetcode是面向职场就业的,而非追求高度思维技巧的ACM竞赛,特别是LeetCode的基础题目并不多,目前大概有358道,而且其题型都非常简单明了,并不需要的复杂的理解,一般都在50行左右就可以解决。这有助于广大的求职朋友建立自信,提升技能。本门课程分类精选了30道题目,从vs code刷题环境搭建起手,手把手的进行了课程引导,以期能帮助广大求职人员,积累知识,提升技能,不过有些题是加锁的,好像有付费才能使用,能做的题应该有150多道吧,这也是完全足够了。   另外,如果你写了上百行代码,就肯定说明你想太多了或太复杂,虽然都能用很短的代码就能解决,但并不意味着LeetCode的题目非常简单,实际上LeetCode基本上涉及到了所有常规的算法类型。   关于LeetCode的刷题时间:个人认为大概是要一个月左右,如果你是大神的话,也许大概能在两到三个星期间刷 完,不过做为新手,除了埋头做题,更重要的是去讨论区看看别人的代码或思路。一道一道刷题虽然速度慢了点,不过会学到了许多。为了帮助广大学员朋友切实提升程序开发技巧,积累学习信心,克服畏难情绪,丁宋涛和夏曹俊老师共同精心设计了本门课程。希望通过本门课程可以分享知识,掌握技能。

    3571 人正在学习 去看看 夏曹俊

蒟蒻的ACM数据结构-划分树

如题:POJ2014
给定一n个元素的数组,每次查询[l,r]区间内从小到大第k个数.
朴素解法为将数组[l,r]内的数排序,然后选择第k个即可.最坏情况O(m*n).
这个时候,就需要更好的数据结构,划分树/归并树.

定义

1
原数组为{4,2,5,7,1,8,3,6},在每次划分左右子树时的中值,都用红色表明.小于中值的进入左子树,大于中值的进入右子树.
观察我们发现,每一层都是数组n,只不过顺序有了变化.而对于log2(1e9)这个数,也不过20.所以我们定义一个tree[20][n]的数组,用来存树.

//toleft稍后再讲
int tree[20][MAXN], sorted[MAXN], toleft[20][MAXN];

建树

我们定义一个数组toleft[20][MAXN],其指在某数的左边所有进入左子树的数的个数.
toleft数组

第一次划分
[4,2,5,7,1,8,3,6]
[1,2,2,2,3,3,4,4]	看i-th前面有多少个数进入左子树.
第二次划分
[4,2,1,3] [5,7,8,6]
[0,1,2,2] [1,1,1,2]
第三次划分
[2,1][4,3][5,6][7,8]
[0,1][0,1][1,1][1,1]
第四次划分
[1][2][3][4][5][6][7][8]
[0][0][0][0][0][0][0][0]
void built(int l, int r, int dep)
{
	if (l == r)
		return;
	int mid = (l + r) >> 1, same = mid - l + 1;
	for (int i = l; i <= r; i++)		//same值指相同的中值
		if (tree[dep][i] < sorted[mid])
			same--;
	int lpos = l, rpos = mid + 1;
	for (int i = l; i <= r; i++) {		//将[l,r]内的数划分
		if (tree[dep][i] < sorted[mid])
			tree[dep + 1][lpos++] = tree[dep][i];
		else if (tree[dep][i] == sorted[mid] && same > 0) {
			tree[dep + 1][lpos++] = tree[dep][i];
			same--;
		}
		else
			tree[dep + 1][rpos++] = tree[dep][i];
		toleft[dep][i] = toleft[dep][l - 1] + lpos - l;		//记下当前数的toleft值
	}
	built(l, mid, dep + 1);
	built(mid + 1, r, dep + 1);
}

查询

类似于线段树的单点查询
只需要考虑一个不等式
toleft[dep][r] - toleft[dep][l - 1]>=k
如果成立,说明这个数被划进了左子树.那么大区间[L,(L+R)>>1],小区间[l,r]变为[L + toleft[dep][l - 1] - toleft[dep][L - 1],newl + cnt - 1]
如果toleft[dep][r] - toleft[dep][l - 1]<k
那么,这个数就被划进了右子树,那么大区间变为[(L+R)>>1+1,R],小区间变为[newr - (r - l - cnt),r + toleft[dep][R] - toleft[dep][r]].
这样不断递归,当小区间l==r时,便确定了从小到大第k个数是几.

int query(int L, int R, int l, int r, int dep, int k)
{
	if (l == r)
		return tree[dep][l];
	int mid = (L + R) >> 1;
	int cnt = toleft[dep][r] - toleft[dep][l - 1];
	if (cnt >= k) {
		int newl = L + toleft[dep][l - 1] - toleft[dep][L - 1];
		int newr = newl + cnt - 1;
		return query(L, mid, newl, newr, dep + 1, k);
	}
	else {
		int newr = r + toleft[dep][R] - toleft[dep][r];
		int newl = newr - (r - l - cnt);
		return query(mid + 1, R, newl, newr, dep + 1, k - cnt);
	}
}

完整代码

当想查询从大到小第k个数,则将if (tree[dep][i] < sorted[mid])改为if (tree[dep][i] > sorted[mid]),sort(sorted + 1, sorted + n + 1);改为从大到小排序即可

#include<iostream>
#include<cstring>
#include<string>
#include<algorithm>
#include<string.h>
#include<map>
using namespace std;
typedef unsigned long long ull;
const int MAXN = 1e5 + 10;

int tree[20][MAXN], sorted[MAXN], toleft[20][MAXN];

void built(int l, int r, int dep)
{
	if (l == r)
		return;
	int mid = (l + r) >> 1, same = mid - l + 1;
	for (int i = l; i <= r; i++)
		if (tree[dep][i] < sorted[mid])
			same--;
	int lpos = l, rpos = mid + 1;
	for (int i = l; i <= r; i++) {
		if (tree[dep][i] < sorted[mid])
			tree[dep + 1][lpos++] = tree[dep][i];
		else if (tree[dep][i] == sorted[mid] && same > 0) {
			tree[dep + 1][lpos++] = tree[dep][i];
			same--;
		}
		else
			tree[dep + 1][rpos++] = tree[dep][i];
		toleft[dep][i] = toleft[dep][l - 1] + lpos - l;
	}
	built(l, mid, dep + 1);
	built(mid + 1, r, dep + 1);
}

int query(int L, int R, int l, int r, int dep, int k)
{
	if (l == r)
		return tree[dep][l];
	int mid = (L + R) >> 1;
	int cnt = toleft[dep][r] - toleft[dep][l - 1];
	if (cnt >= k) {
		int newl = L + toleft[dep][l - 1] - toleft[dep][L - 1];
		int newr = newl + cnt - 1;
		return query(L, mid, newl, newr, dep + 1, k);
	}
	else {
		int newr = r + toleft[dep][R] - toleft[dep][r];
		int newl = newr - (r - l - cnt);
		return query(mid + 1, R, newl, newr, dep + 1, k - cnt);
	}
}

int main()
{
	int n, m;
	while (cin >> n >> m) {
		memset(tree, 0, sizeof(tree));
		for (int i = 1; i <= n; i++) {
			cin >> tree[0][i];
			sorted[i] = tree[0][i];
		}
		sort(sorted + 1, sorted + n + 1);
		built(1, n, 0);
		int s, t, k;
		while (m--) {
			cin >> s >> t >> k;
			cout << query(1, n, s, t, 0, k) << endl;
		}
	}
	return 0;
}

练习题目

洛谷P2048

ACM-数据结构总览

阅读数 1423

acm数据结构整理

阅读数 8

没有更多推荐了,返回首页