2017 UESTC Training for Data Structures-解题报告

题目链接：http://acm.uestc.edu.cn/#/contest/show/155

这个数据结构训练主要针对线段树，树转数组和并查集。比较适合刚入门数据结构的同学。

注意，因为后面题的代码太长了，200+行起步，所以我只贴一些主要代码（有些题没有代码，我之后会补上）

还未更新完，正在更新中

A - An easy problem A

思路：正如其名，是道大水题。裸的RMQ，数据范围略小，也不需要单点更新，所以有很多姿势能水过去

我随便搓颗线段树就A了,时间复杂度O(Q*log(N))。

代码：这题这么简单，应该不需要代码吧，除非你没学过线段树..........

B - An easy problem B

思路：这题题目虽然叫简单题，可是写起来好复杂ORZ。线段树+懒惰标记,时间复杂度O(m*log(n))，在结点上要维护6个域：

1.区间内的最长的1串的长度 2.区间内的最长的0串的长度

3.区间内以区间左端点开始的最长1串的长度 3.区间内以区间左端点开始的最长0串的长度

5.区间内以区间右端点开始的最长1串的长度 6.区间内以区间右端点开始的最长0串的长度

对于上面6个域，我们分别用

这六个变量记录。

合并区间a,b时（a与b相邻且a在b的左边）时：

len1 ------ 新区间内的最长的1串的长度的来源只有3个，①a.len1 ②b.len1 ③a.r1+b.l1

说白了就是在合并地方可能会产生更长的1串，代码如下

      ans.len1=max(a.r1+b.l1,max(a.len1,b.len1));

l1 --------区间内以区间左端点开始的最长1串的长度来源只有2个，①a.l1 ②当a.l1=区间长度时，a.l1+b.l1

也就是说，只要特判一下，当a区间全为1情况就行了，代码如下

ans.l1=a.l1;

　　　　 if(a.l1==a.len)

　　　　　　 ans.l1+=b.l1;

r1 --------同理，区间内以区间右端点开始的最长1串的长度来源只有2个，①b.r1 ②当br1=区间长度时，b.r1+a.r1

也就是说，只要特判一下，当b区间全为1情况就行了，代码如下

　　　　 ans.r1=b.r1;

　　　　 if(a.r1==b.len)

　　　　　　 ans.r1+=a.r1;

0串的情况和以上完全类似，我就不写了

总的代码如下：

 void meg(Node &ans,Node &a,Node &b)

    {

        ans.len1=max(a.r1+b.l1,max(a.len1,b.len1));

        ans.len0=max(a.r0+b.l0,max(a.len0,b.len0));

        ans.l0=a.l0;

        ans.l1=a.l1;

        ans.r0=b.r0;

        ans.r1=b.r1;

        if(a.l0==a.len)

        {

            ans.l0+=b.l0;

        }

        if(a.l1==a.len)

        {

            ans.l1+=b.l1;

        }

        if(b.r0==b.len)

        {

            ans.r0+=a.r0;

        }

        if(b.r1==b.len)

        {

            ans.r1+=a.r1;

        }

        ans.len=a.len+b.len;

    }

接着就是懒惰标记的问题了：

显然，一个区间如果被异或两次的话，等于没被异或过。

所以累加标记时只要 .lazy^=1;就行了

而使用标记更新当前结点时，只要交换0,1串的所有域就行了

　　　　　void fun()

        {

            swap(len0,len1);

            swap(l0,l1);

            swap(r0,r1);

        }

最后就是查询了，为了减低代码复杂度，我们直接调用合并函数合并所有区间，并用些变量存下合并结结果，最后return ans.len1即可

 int query(int l,int r)

    {

        l+=size;

        r+=size;

        putdown((l)>>1,(r)>>1);

        updata(l);

        updata(l^1);

        updata(r);

        updata(r^1);

        Node ans,lans,rans,temp;

        if(l==r)

            ans=node[l];

        else

        {

            lans=node[l];

            rans=node[r];

            for(; r^l^1; l>>=1,r>>=1 )

            {

                updata(l);

                updata(l^1);

                updata(r);

                updata(r^1);

                if(~l&1)

                {

                    temp=lans;

                    meg(lans,temp,node[l^1]);

                }

                if(r&1)

                {

                    temp=rans;

                    meg(rans,node[r^1],temp);

                }

            }

            meg(ans,lans,rans);

            updata(l);

            updata(r);

        }

        while(l>1)

        {

            l>>=1;

            updata(l);

            updata(l^1);

        }

        return ans.len1;

    }

C - An easy problem C

思路：比起B题，C题就简单多了，主要是考查懒惰标记，时间复杂度O(m*log(n))

难点在与标记的设置和复合

我们在标记上存两个域，一个a,一个b。代表对区间内的每个数x，进行ax+b的操作，用矩阵表示就是

1.当子区间复合一个来自父区间的标记a1,b2时，子区间的a，b的更新操作如下

void change(long long a1,long long b1)

{

　　a=a1*a%p;

　　b=(a1*b+b1)%p;

}

矩阵的表示如下

2.操作1，和操作2都可以看做在区间上复合上一个新标记即可

加法： node[].change(1,C);

乘法： node[].change(C,0);

3.使用标记

我们在区间存下一个域sum,代表区间和。

因为是对区间内的每个数进行a*x+b的操作，所以

所以 sum=(a*sum+b*len)%p;

4.接着就是合并区间的操作了

这没啥好说的，就是sum=a.sum+b.sum

5.这里要注意一下，标记为空时，应该是a=1,b=0

因为x=1*x+0;所以初始化时，和清除标记时都应该是执行下面这个操作

void clc()

{ 　　

　　a=1;

　　b=0；

}

D - Washi与Sonochi的约定

思路：这题比较简单主要是考查点转化模型的脑洞，我门先将所有点按x坐标从小到大排好序，然后问题就变成，在一个位置前面有多少个点的y坐标比他小，

这就变成了经典的求顺/逆序数的问题了。时间复杂度O(n*log(n))

代码：求逆序数的代码可以看下一题

E - 曜酱的心意

思路：这题也是脑洞题，我们先求一个映射F(x)，把a1,a2,a3……an映射成1,2,3,……n，再对bn使用一下这个映射。

这时an变成的从小到大的有序数列。则求bn变成an的最小交换次数就等价于求用冒泡排序对bn排序至少要用多少次交换。

答案是bn的所有数的逆序数之和。所以同上题时间复杂度O(n*log(n))

代码

#include<stdio.h>

#include<string.h>

int a[100005],b[100005],f[100005];

int  c[100010],n;

inline int Lowbit(int x)

{

    return x&(-x);

}

int getsum(int ed)

{

    int sum=0;

    while(ed>0)

    {

        sum+=c[ed];

        ed-=Lowbit(ed);

    }

    return sum;

}

void update(int pos,int num)

{

    while(pos<=n)

    {

        c[pos]+=num;

        pos+=Lowbit(pos);

    }

}

int main()

{

    int i,j,top=0,m,fp,flag,k,x;

    long long sum;

    scanf("%d",&n);

    for(i=1; i<=n; i++)

    {

        scanf("%d",&a[i]);

        f[a[i]]=i;

    }

    for(i=1;i<=n;i++)

    {

        scanf("%d",&b[i]);

        b[i]=f[b[i]];

    }

    sum=0;

    for(i=n;i>=1;i--)

    {

        sum+=getsum(b[i]);///求1到b[i]中有多少个数

        update(b[i],1);///把b[i]位置更新为1.代表这个位置上有一个数

    }

    printf("%lld\n",sum);

    return 0;

}

F - 奇迹的魔法啊，再度出现！

思路：经典的01字典树的题目，时间复杂O(31*(N+M)).

预处理：我们先把所有的ai拆分成31长度的二进制串，并按照从高位到低位的顺序全部插入到颗二叉字典树中。

查询：也把每个要查询的bi拆分成31长度的二进制，然后在字典树上从高位到低位贪心查询即可

代码如下：

#include<stdio.h>

#include<math.h>

#include<set>

using namespace std;

struct tree

{

    tree * next[2];

    tree()

    {

        next[0]=next[1]=NULL;

    }

}head;

void insert(int bit[])

{

    int i;

    tree *p=&head;

    for(i=30;i>=0;i--)

    {

        if(p->next[bit[i]]==NULL)

        {

            p->next[bit[i]]=new tree();

        }

        p=p->next[bit[i]];

    }

}

int find(int bit[])

{

    int i,sum=0;

    tree *p=&head;

    for(i=30;i>=0;i--)

    {

        sum<<=1;

        if(p->next[bit[i]^1]==NULL)

        {

            p=p->next[bit[i]];

        }

        else

        {

            sum++;

            p=p->next[bit[i]^1];

        }

    }

    return sum;

}

int a[40];

void bin(int n)

{

    int i;

    for(i=0;i<31;i++,n>>=1)

        a[i]=n&1;

}

int main()

{

    int t,n,m,i,l,r,x,s1,s2,j,flag;

    scanf("%d",&n);

    while(n--)

    {

        scanf("%d",&x);

        bin(x);

        insert(a);

    }

    scanf("%d",&m);

    while(m--)

    {

        scanf("%d",&x);

        bin(x);

        printf("%d\n",find(a));

    }

    return 0;

}

G - 加帕里公园的friends

思路：线段树，所以复杂度时间复杂度（m*log(n)*log(n)）

巴特西

2017 UESTC Training for Data Structures-解题报告

最新文章

热门文章