jvruo

【蒟蒻题解】国庆NOIP模拟赛(一)
超级久没有码BLOG了,超级想念当时搭BLOG的感觉……可是现在我已经是一株高三的苍老蒟蒻了,所以更新速度会慢很...
扫描右侧二维码阅读全文
02
2018/10

【蒟蒻题解】国庆NOIP模拟赛(一)

超级久没有码BLOG了,超级想念当时搭BLOG的感觉……可是现在我已经是一株高三的苍老蒟蒻了,所以更新速度会慢很多,望谅解。下面就让我们一起走进国庆的第一场模拟赛吧!

A 最长距离

问题描述:
windy有一块矩形土地,被分为 NM 块 11 的小格子。 有的格子含有障碍物。 如果从格子A可以走到格子B,那么两个格子的距离就为两个格子中心的欧几里德距离。
如果从格子A不可以走到格子B,就没有距离。 如果格子X和格子Y有公共边,并且X和Y均不含有障碍物,就可以从X走到Y。
如果windy可以移走T块障碍物,求所有格子间的最大距离。 保证移走T块障碍物以后,至少有一个格子不含有障碍物。
输入格式
输入第一行包含三个整数,N M T。 接下来有N行,每行一个长度为M的字符串,’0’表示空格子,’1’表示该格子含有障碍物。
【数据规模】
20%的数据,满足 1≤N,M≤30 ; 0≤T≤0 。
40%的数据,满足 1≤N,M≤30 ; 0≤T≤2 。
100%的数据,满足 1≤N,M≤30 ; 0≤T≤30 。
输出格式
输出包含一个浮点数,保留6位小数。
样例输入
【样例输入1】
3 3 0
001
001
110
【样例输入2】
4 3 0
001
001
011
000
【样例输入3】
3 3 1
001
001
001
样例输出
【样例输出1】
1.414214
【样例输出2】
3.605551
【样例输出3】
2.828427

这题比赛的时候搞了我快两个小时……还是没看出这题表面上叫做最长距离,实际上是一道最短路的题目QwQ什么你也没看出,没关系,我来慢慢告诉你。

我们观察发现,题目最开始给我们的是一个网格图,有的格子是1,表示有障碍物,有的格子是0,表示没有障碍物,就像下面这幅图一样:

1.png

现在我们就可以让个相邻节点建边了。由于规定走到的节点一定要为0,所以我们让任意一条边,如果走到节点值为0的点,那么边权就为0;如果走到节点值为1的点,那么边权就为1,就像下面这幅图一样:

2.png

OK,那我们再把某一点值为0的点,设为起点,从该点出发跑单源最短路径,跑出来的结果是什么?没错!就是这个点到达任一点的最小代价!那思路就很显然了!我们枚举起点,然后跑SFPA,找到所有与他在代价小于等于T的条件下联通的点,求出其中最大的欧几里德距离就是我们要的答案了!总的复杂度为O((NM)^2)。

特别需要注意的是,可能会出现刚开始给你的图一个为0的格子都没有,这个时候就要特判一下下,让最左上角也就是(1,1)的点变为0,然后T--,相当于先开辟一个点。

下面附上代码:

#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<cstring>
using namespace std;
struct node
{
    int x,y,num,next;
}f[11000];
int a[1100][1100],last[11000],g[11000],vis[11000];
int list[1100000],head,tail;
char s[1100];
int i,j,k,m,n,o,p,jl,num,t,x,y;
double js,ma;
int ins(int u,int v,int k)
{
    num++;
    f[num].x=u;f[num].y=v;f[num].num=k;
    f[num].next=last[u];last[u]=num;
    return 0;
}
int main()
{
    scanf("%d%d%d",&n,&m,&t);
    for(int i=1;i<=n;i++)
    {
        scanf("%s",s+1);
        for(int j=1;j<=n;j++)
        {
            a[i][j]=s[j]-'0';
            if(a[i][j]==0)jl++;
        }
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            if(i>1)ins((i-1)*m+j,(i-2)*m+j,a[i-1][j]);
            if(j>1)ins((i-1)*m+j,(i-1)*m+j-1,a[i][j-1]);

            if(i+1<=n)ins((i-1)*m+j,i*m+j,a[i+1][j]);
            if(j+1<=m)ins((i-1)*m+j,(i-1)*m+j+1,a[i][j+1]);
        }
    }
    if(jl==0)
    {
        a[1][1]=0;
        t--;
    }
    ma=0;
    for(int i=1;i<=n;i++)
    for(int j=1;j<=m;j++)
    {
        if(a[i][j]==0)
        {
            memset(g,63,sizeof(g));
            memset(vis,0,sizeof(vis));
            g[(i-1)*m+j]=0;head=1;tail=2;
            list[head]=(i-1)*m+j;vis[list[head]]=1;

            while(head<tail)
            {
                x=list[head];
                for(int k=last[x];k;k=f[k].next)
                {
                    y=f[k].y;
                    if(g[x]+f[k].num<g[y])
                    {
                        g[y]=g[x]+f[k].num;
                        if(vis[y]==0)
                        {
                            vis[y]=1;
                            list[++tail]=y;
                        }
                    }
                }
                vis[x]=0;
                head++;
            }

            for(int ii=1;ii<=n;ii++)
            for(int jj=1;jj<=m;jj++)
            {
                o=(ii-1)*m+jj;
                if(g[o]<=t)
                {
                    js=sqrt((i-ii)*(i-ii)+(j-jj)*(j-jj));
                    if(js>ma)ma=js;
                }
            }
        }

    }
    printf("%0.6lf",ma);
    return 0; 
} 

B 扑克牌

问题描述:
你有n种牌,第i种牌的数目为ci。另外有一种特殊的牌:joker,它的数目是m。
你可以用每种牌各一张来组成一套牌,也可以用一张joker和除了某一种牌以外的其他牌各一张组成1套牌。
比如,当n=3时,一共有4种合法的套牌:{1,2,3}, {J,2,3}, {1,J,3}, {1,2,J}。
给出n, m和ci,你的任务是组成尽量多的套牌。每张牌最多只能用在一副套牌里(可以有牌不使用)。
输入格式
第一行包含两个整数n, m,即牌的种数和joker的个数。第二行包含n个整数ci,即每种牌的张数。
【样例解释】
输入数据表明:一共有1个1,2个2,3个3,4个joker。最多可以组成三副套牌:{1,J,3}, {J,2,3}, {J,2,3},joker还剩一个,其余牌全部用完。
【数据规模】
50%的数据满足:2 < = n < = 5, 0 < = m < = 10^ 6, 0< = ci < = 200。
100%的数据满足:2 < = n < = 50, 0 < = m, ci < = 500,000,000。
输出格式
输出仅一个整数,即最多组成的套牌数目。
样例输入
3 4
1 2 3
样例输出
3

这是一道比较有意思的题目,下面提供两种思路的解法,分别是从正面和从侧面的做法:

解法一:从正面进行操作:
我们观察一下题目,我们发现这道题其实可以用贪心去做。通过观察我们可以知道每一套牌中,JOKER不是必须的,所以我们会想,能不能把JOKER当成普通牌来看待呢?

当然可以,我们对问题进行一下变形,把JOKER当做一张普通牌来看待,那么问题就变形为了:我们有n+1种牌,每次取数量最多的n张牌进行数量减一的操作,问能操作多少次?

仔细想想,好像也不好做,那就再变形,问题又变形为:我们有n+1种牌,每次取数量最少的那张牌进行数量加一的操作,然后全部牌的数量均减一,问能操作多少次?

这样问题就迎刃而解了!【虽然貌似会超时部分点】

解法二:从侧面进行输出:
我们不一定要从正面进行贪心硬求套牌数目,很明显,这里求解的套牌数符合二分原理,于是考虑对套牌数进行二分答案:

如何判断?嗯很有意思。我们考虑我们当前二分到答案为u套套牌,我们设jl为要消耗的JOKER数量。那么我们只要枚举没一种牌,如果第i种牌的数量为ci,小于u,那么我们jl+=u-ci,相当于用JOKER将缺少的牌都补齐了。

最后我们再对jl进行判断,我们要满足两个条件:
1.用的JOKER数量不能超过总的JOKER数量
2.每套牌最多只能用一张JOKER

那么我们的jl同样只要满足两个条件:
1.jl小于等于JOKER的总数量M
2.jl小于等于我当前二分出来的答案u。因为如果我有u套牌,只用了jl(jl≤u),那么就一定能找到一组解满足每套牌用的JOKER小于等于一张,这应该还是很好理解的吧。所以按照这样的思路直接二分答案就好了!

我打的是二分答案这种解法的,感兴趣的同学可以尝试一下解法一的打法。下面附上代码:

#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;
long long a[5500];
long long i,j,k,m,n,o,p,js,jl,jk,l,r,mid;
long long pd(long long u)
{
    jl=0;
    for(int i=1;i<=n;i++)if(a[i]<u)jl+=u-a[i];

    if(jl<=m && jl<=u)return(true);
    else return(false);

}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)scanf("%lld",&a[i]);
    l=0;r=2147483647;
    while(r-l>1)
    {
        mid=(l+r)/2;
        if(pd(mid))l=mid;
        else r=mid-1;
    }

    if(pd(r))printf("%lld",r);
    else printf("%lld",l);
    return 0;
}

C 这是一道大水题

问题描述:
给你N个数,非递减序列排序,有M次询问,每次询问一个区间[L,R],问这个区间内出现最多的数的次数是多少?
输入格式
输入第一行包含一个数N。
第二行输入N个数。
第三行输入一个整数M。
接下来输入M行,每行两个整数L,R.
N<=100000,M<=100000
输出格式
这个区间内出现最多的数的次数是多少?
样例输入
10
1 2 3 3 4 4 5 5 6 6
5
1 3
4 8
3 8
3 7
1 10
样例输出
1
2
2
2
2

这道题很明显是一道区间的查询问题,我们同样提供两种比较相似的解法:

解法一:ST算法:
我们假如有一个原序列:
1 2 3 3 4 4 5 5 5 5
我们可以把它转化为a序列:
1 1 1 2 1 2 1 2 3 4

那么如果我们要查询[1,10],问题就转化成了查询区间最值,但是这样就会出现一个问题,如果我们要查询[4,9]呢?这时有两个区间被斩断了,所以我们还要为维护一个序列,表示每一段区间有多长。

比如原序列:
4 4 4 4 5 5 6 6 6
我们就维护一个b序列:
4 4 4 4 2 2 3 3 3

这样的话还是上面那个例子,假如我们要查询[3,8],那么我们要查询的序列就是:
原序列:4 4 5 5 6 6
a序列:3 4 1 2 1 2
b序列:4 4 2 2 3 3

那么这个时候我们就可以把原序列分开两部分进行查询:
左部分:4 4
右部分:5 5 6 6

我们先看右部分如何操作,由于右部分都是完整的数字块或者完整的数字块的左部分,所以此时我们只要查询其对应部分的a序列的最大值就好了,蔽日我们现在得到的右部分的原序列:5 5 6 6对应的a序列为1 2 1 2,所以右部分的最大值为2。

接下来考虑如何快速得到左部分长度。由于左部分只含一种数字,所以其对应长度就为其开头点对应的b序列的值减去a序列的值再加一就是对应左部分的长度了,比如这个例子中,左部分长度就为4-3+1=2。

最后再比较左右部分答案取最大值就好了!

然后就很好操作了!【还是挺麻烦的说】

解法二:

既然觉得上面的算法复杂,我们就不如走回我们的老路——线段树,假如我们现在有一个数列,如下图:

3.png

现在我们要查询[4,9],也就是被框起来的区间,我们发现这是由三大部分组成的:

4.png

不完整的数字块3,完整的数字块4,不完整的数字块5。

一头一尾所在的区间可能是不完整的,所以我们单独取出放在最后特判。我们现在要做的,就是用线段树再O(logn)的复杂度下,查询中间这一段完整区间相同数字的长度的最大值!

再比如:我们要查询区间[2,9],这时我们线段树要做的就是查询完整的数字块2,3,4中相同数字长度的最大值,至于一头一尾,最后判断一下有没有中间找出来的最长数字串长度大就好啦。
5.png

最后附上代码:

#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;

struct node
{
    int l,r,max,num;
}tr[440000];

int a[110000],b[110000],c[110000],d[110000];
int i,j,k,m,n,o,p,js,jl,jk,ma,maa,x,y,xx,yy;

int my_min(int x,int y)
{
    if(x<y)return(x);
    else return(y);
}

int my_max(int x,int y)
{
    if(x>y)return(x);
    else return(y);
}
int build(int n,int l,int r)
{
    tr[n].l=l;tr[n].r=r;
    if(l==r)
    {
        tr[n].num=l;
        tr[n].max=b[l];
        return 0;
    }

    int mid=(l+r)/2;
    build(n*2,l,mid);
    build(n*2+1,mid+1,r);

    if(tr[n*2].max>tr[n*2+1].max)
    {
        tr[n].max=tr[n*2].max;
        tr[n].num=tr[n*2].num;
    }
    else
    {
        tr[n].max=tr[n*2+1].max;
        tr[n].num=tr[n*2+1].num;
    }
    return 0;
}
int fa(int u)
{
    int l=1,r=jl,mid;

    while(r-l>1)
    {
        mid=(l+r)/2;
        if(d[mid]>u)r=mid-1;
        else l=mid;
    }

    if(d[r]<=u)return(r);
    else return(r-1);
}

int find(int n,int l,int r)
{
    int mid=(l+r)/2;
    if(l>=xx+1 && r<=yy-1)
    {
        if(tr[n].max>ma)ma=tr[n].max;
        return 0;
    }
    if(xx+1<=mid)find(n*2,l,mid);
    if(yy-1>mid) find(n*2+1,mid+1,r);
    return 0;
}
int main()
{
    scanf("%d",&n);
    jl=0;
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
        if(a[i]>a[i-1])
        {
            jl++;
            c[jl]=a[i];
            d[jl]=i;
        }
        b[jl]++;
    }
    build(1,1,jl);

    scanf("%d",&m);
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d",&x,&y);
        xx=fa(x);
        yy=fa(y);
        ma=0;
        find(1,1,jl);
        if(my_min(d[xx+1],y+1)-x>ma)ma=my_min(d[xx+1],y+1)-x;
        if(y-my_max(d[yy],x)+1>ma)ma=y-my_max(d[yy],x)+1;
        printf("%d\n",ma);
    }
    return 0;
}

结语

这次的题目码量和难度都不会很大,关键是要有想法【我可能是个没什么想法的蒟蒻QwQ】。希望你能从中有所收获吧!最后希望你喜欢这篇BLOG!

0.png

Last modification:October 5th, 2018 at 07:25 pm
If you think my article is useful to you, please feel free to appreciate

Leave a Comment