【2016福建省夏令营Day1】数据结构

Problem 1 楼房(build.cpp/c/pas)

【题目描述】

地平线(x轴)上有n个矩(lou)形(fang)，用三个整数h[i],l[i],r[i]来表示第i个矩形：矩形左下角为(l[i],0)，右上角为(r[i],h[i])。地平线高度为0。在轮廓线长度最小的前提下，从左到右输出轮廓线。

下图为样例2。

【输入格式】

第一行一个整数n，表示矩形个数。

以下n行，每行3个整数h[i],l[i],r[i]表示第i个矩形。

【输出格式】

第一行一个整数m，表示节点个数。

以下m行，每行一个坐标表示轮廓线上的节点。从左到右遍历轮廓线并顺序输出节点。第一个和最后一个节点的y坐标必然为0。

【样例输入】

2
3 0 2
4 1 3

【样例输出】

6
0 0
0 3
1 3
1 4
3 4
3 0

【样例输入2】

5
3 -3 0
2 -1 1
4 2 4
2 3 7
3 6 8

【样例输出2】

14
-3 0
-3 3
0 3
0 2
1 2
1 0
2 0
2 4
4 4
4 2
6 2
6 3
8 3
8 0

【数据范围】

对于30%的数据，n<=100

对于另外30%的数据，n<=100000,1<=h[i],l[i],r[i]<=1000

对于100%的数据，1<=n<=100000,1<=h[i]<=10^9,-10^9<=l[i]<r[i]<=10^9

题解

扫描线+堆维护

推荐使用multset和pair 很方便

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cstring>

#include<algorithm>

#include<set>

using namespace std;

pair<int,int> a[],ans[];

multiset<int> q;

int n,cnt,maxh,num;

int main()

{

    int i,j,h,x,y;

    scanf("%d",&n);

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

    {

        scanf("%d%d%d",&h,&x,&y);

        a[++cnt]=make_pair(x,h);

        a[++cnt]=make_pair(y,-h);

    }

    sort(a+,a++cnt);

    q.insert();

    maxh=;

    for(i=;i<=cnt;)

    {

        for(j=i;j<=cnt;j++)

        {

            if(a[i].first<a[j].first) break;

            else

             if(a[j].second>) q.insert(a[j].second);

             else q.erase(q.find(-a[j].second));

        }

        h=*q.rbegin();

        if(h!=maxh)

        {

            ans[++num]=make_pair(a[i].first,maxh);

            ans[++num]=make_pair(a[i].first,h);

            maxh=h;

        }

        i=j;

    }

    printf("%d\n",num);

    for(i=;i<=num;i++) printf("%d %d\n",ans[i].first,ans[i].second);

    return ;

}

Problem 2 单词背诵(word.cpp/c/pas)

【题目描述】

灵梦有n个单词想要背，但她想通过一篇文章中的一段来记住这些单词。

文章由m个单词构成，她想在文章中找出连续的一段，其中包含最多的她想要背的单词（重复的只算一个）。并且在背诵的单词量尽量多的情况下，还要使选出的文章段落尽量短，这样她就可以用尽量短的时间学习尽可能多的单词了。

【输入格式】

第一行一个数n，表示想要背的单词数。

接下来n行每行是一个长度不超过10的字符串，表示一个要背的单词。

接着是一个数m，表示文章中的单词数

然后是m行长度不超过10的字符串，每个表示文章中的一个单词。

【输出格式】

输出文件共2行。第1行为文章中最多包含的要背的单词数，第2行表示在文章中包含最多要背单词的最短的连续段的长度。

【样例输入】

hot

dog

milk

hot

dog

milk

hot

【样例输出】

【数据范围】

对于30%的数据 n<=50，m<=500；

对于60%的数据 n<=300，m<=5000；

对于100%的数据 n<=1000，m<=100000；

题解

哈希+双指针扫描

#include<iostream>

#include<cstdio>

#include<cstdlib>

#include<cstring>

#include<cmath>

#include<algorithm>

#define mod 233327

using namespace std;

int n,m,anscnt,ans,cnt;

char s[],str[][];

struct hh

{

    char v[];

    int next;

};

hh e[];

int last[],hash[],vis[];

bool h[];

void insert(int x)

{

    ++cnt;

    strcpy(e[cnt].v,s);

    e[cnt].next=last[x];

    last[x]=cnt;

}

bool query(int x,int k)

{

    int i;

    for(i=last[x];i;i=e[i].next)

     if(!strcmp(e[i].v,str[k])) return true;

    return false;

}

int main()

{

    int i,j,len,thash,head,tail,now,tlen;

    scanf("%d",&n);

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

    {

        scanf("\n%s",&s);

        len=strlen(s);thash=;

        for(j=;j<=len-;j++)

          thash=(thash*+s[j])%mod;

        insert(thash);

    }

    scanf("%d",&m);

    for(i=;i<=m;i++)

    {

        scanf("\n%s",&str[i]);

        len=strlen(str[i]);thash=;

        for(j=;j<=len-;j++)

         thash=(thash*+str[i][j])%mod;

        hash[i]=thash;

    }

    for(i=;i<=m;i++)

      if(query(hash[i],i)&&!h[hash[i]])

      {

          anscnt++;

          h[hash[i]]=true;

      }

    printf("%d\n",anscnt);

    if(!anscnt) goto hhh;

    head=;tail=;now=tlen=;

    ans=;

    if(query(hash[],))

    {

        vis[hash[]]=;

        now++;

    }

    while((head<=tail&&tail<m)||now==anscnt)

    {

        if(now==anscnt)

        {

            ans=min(ans,tail-head+);

            thash=hash[head++];

            if(query(thash,head-))

            {

                vis[thash]--;

                if(!vis[thash]) now--;

            }

        }

        else

        {

            thash=hash[++tail];

            if(query(thash,tail))

            {

                if(!vis[thash]) now++;

                vis[thash]++;

            }

        }

    }

    hhh:;

    printf("%d",ans);

    return ;

}

Problem 3 矩阵(matrix.cpp/c/pas)

【题目描述】

给定一个N行M列的非负整数矩阵，求一个最大的正方形子矩阵，该矩阵满足：

矩阵中每一个元素权值都大于0；

在满足上述条件的前提下，矩阵面积最大；

在满足上述条件的前提下，选择元素和最小的。

【输入格式】

第一行两个整数N, M

接下来N行，每行M个整数。

【输出格式】

两个数，用空格隔开，第一个数为满足条件的矩阵的面积，第二个数为该矩阵各元素之和。

【样例输入】

3 7

1 1 1 0 2 1 1

1 1 1 0 1 1 1

【样例输出】

9 9

【数据范围】

对于30%的数据，R,C<=10；

对于60%的数据，R,C<=100；

对于100%的数据，R,C<=1000。

0 <= 输入的其他整数 <= 10^9

题解

一开始预处理前缀和，然后二分正方形边长，枚举正方形的位置即可。

#include<iostream>

#include<cstdio>

#include<cstdlib>

#include<cstring>

#include<cmath>

#include<algorithm>

using namespace std;

int n,m,a[][],ans1;

long long sum[][],sum0[][],ans2=1LL<<;

bool checkzero(int x,int y,int len)

{

    int newx,newy;

    newx=x+len-,newy=y+len-;

    return sum0[newx][newy]-sum0[x-][newy]-sum0[newx][y-]+sum0[x-][y-]==;

}

bool check(int len)

{

    int i,j;

    for(i=;i+len-<=n;i++)

      for(j=;j+len-<=m;j++)

        if(checkzero(i,j,len)) return true;

    return false;

}

int main()

{

    int i,j,nowsum0,l,r,mid,nowi,nowj;

    long long nowsum;

    scanf("%d%d",&n,&m);

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

      for(j=;j<=m;j++)

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

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

    {

        nowsum=0LL;

        nowsum0=;

        for(j=;j<=m;j++)

        {

            nowsum+=a[i][j];

            nowsum0+=a[i][j]==;

            sum[i][j]=sum[i-][j]+nowsum;

            sum0[i][j]=sum0[i-][j]+nowsum0;

        }

    }

    l=;

    r=n<m?n:m;

    while(l<=r)

    {

        mid=(l+r)>>;

        if(check(mid))

        {

           ans1=mid;

           l=mid+;

        }

        else r=mid-;

    }

    printf("%d ",ans1*ans1);

    for(i=;i+ans1-<=n;i++)

      for(j=;j+ans1-<=m;j++)

        if(checkzero(i,j,ans1))

        {

            nowi=i+ans1-;

            nowj=j+ans1-;

            ans2=min(ans2,sum[nowi][nowj]-sum[i-][nowj]-sum[nowi][j-]+sum[i-][j-]);

        }

    printf("%lld",ans2);

    return ;

}

巴特西

【2016福建省夏令营Day1】数据结构

最新文章

热门文章