NOIP 2018 day1 题解

　　今年noip的题和去年绝对是比较坑的题了，但是打好的话就算是普通水准也能350分以上吧。

t1：

NOIP 2018 day1 题解

很显然这是一个简单的dp即可。

#include<iostream>

#include<cstdio>

#include<cstring>

#include<cmath>

#include<string>

#include<algorithm>

#include<ctime>

#include<iomanip>

#include<vector>

#include<map>

#include<queue>

#include<stack>

using namespace std;

inline long long read()

{

    long long x=,f=;char ch=getchar();

    while(ch<''||ch>''){if(ch=='-')f=-;ch=getchar();}

    while(ch>=''&&ch<=''){x=x*+ch-'';ch=getchar();}

    return x*f;

}

const long long maxn=;

long long n;

long long a[maxn],now=,ans=;

int main()

{

    //freopen("road.in","r",stdin);

    //freopen("road.out","w",stdout);

    n=read();

    for(long long i=;i<=n;i++)a[i]=read();

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

    {

        if(a[i]>now){ans+=a[i]-now;now=a[i];}

        else now=a[i];

    }

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

    return ;

}

t2：

NOIP 2018 day1 题解

很显然，这是个完全背包，考试的时候沙比没看出来打了搜索。

#include<iostream>

#include<cstdio>

#include<cstring>

#include<cmath>

#include<string>

#include<algorithm>

#include<ctime>

#include<iomanip>

#include<vector>

#include<map>

#include<queue>

#include<stack>

using namespace std;

inline int read()

{

    int x=,f=;char ch=getchar();

    while(ch<''||ch>''){if(ch=='-')f=-;ch=getchar();}

    while(ch>=''&&ch<=''){x=x*+ch-'';ch=getchar();}

    return x*f;

}

const int maxn=;

int t,n;

int a[maxn],f[],ans=;

int main()

{

    //freopen("1.in","r",stdin);

    //freopen("money.out","w",stdout);

    t=read();

    for(int u=;u<=t;u++)

    {

        memset(f,,sizeof(f));

        n=read();f[]=;ans=;

        for(int i=;i<=n;i++)a[i]=read();

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

            for(int j=a[i];j<=;j++)

                    f[j]+=f[j-a[i]];

        for(int i=;i<=n;i++)if(f[a[i]]==)ans++;

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

    }

    return ;

}

NOIP 2018 day1 题解

暴力55分代码如下：

#include<bits/stdc++.h>

#include<iomanip>

#include<cstdio>

#include<cstring>

#include<string>

#include<cmath>

#include<ctime>

#include<queue>

#include<deque>

#include<bitset>

#include<set>

#include<vector>

#include<algorithm>

#include<stack>

#include<map>

#include<iomanip>

using namespace std;

inline long long read()

{

    long long x=,f=;char ch=getchar();

    while(ch<''||ch>''){if(ch=='-')f=-;ch=getchar();}

    while(ch>=''&&ch<=''){x=x*+ch-'';ch=getchar();}

    return x*f;

}

inline void put(long long x)

{

    if(x==){putchar('');putchar('\n');return;}

    if(x<)putchar('-'),x=-x;

    long long num=;char ch[];

    while(x)ch[++num]=x%+'',x/=;

    while(num)putchar(ch[num--]);

    putchar('\n');return;

}

const long long maxn=;

long long n,m,flag=,flag1=;

long long lin[maxn<<],nex[maxn<<],ver[maxn<<],e[maxn<<],len=;

long long ru[maxn],s,ans=,q[maxn<<],h=,t=,vis[maxn<<];

long long d[maxn],cnt=,u;

void add(long long x,long long y,long long z)

{

    ver[++len]=y;

    nex[len]=lin[x];

    lin[x]=len;

    e[len]=z;

}

//赛道修建 55分做法

long long check1(long long x)

{

    t=;h=;

    long long tot=,num=;

    q[++t]=s;

    memset(vis,,sizeof(vis));

    vis[s]=;

    //cout<<x<<endl;

    while(h++<t)

    {

        long long te=q[h];

        for(long long i=lin[te];i;i=nex[i])

        {

            long long tn=ver[i];

            if(vis[tn]==)continue;

            q[++t]=tn;

            num+=e[i];

            vis[tn]=;

            if(num>=x)tot++,num=;

        }

    }

    if(tot>=m)return ;

    else return ;

}

void solve1()//一条链

{

    for(long long i=;i<=n;i++)if(ru[i]==){s=i;break;}

    //cout<<s<<endl;

    //cout<<m<<endl;

    //cout<<ans<<endl;

    long long l=,r=ans;

    while(l+<r)

    {

        long long mid=(l+r)>>;

        if(check1(mid)==)l=mid;

        else r=mid;

    }

    if(check1(r)==)put(r);

    else put(l);

    return;

}

void dp(long long x)

{

    vis[x]=;

    for(long long i=lin[x];i;i=nex[i])

    {

        long long tn=ver[i];

        if(vis[tn]==)continue;

        dp(tn);

        cnt=max(cnt,d[x]+d[tn]+e[i]);

        d[x]=max(d[x],d[tn]+e[i]);

    }

    return;

}

void bfs()

{

    h=,t=;cnt=;

    memset(vis,,sizeof(vis));

    memset(d,,sizeof(d));

    q[++t]=;vis[]=;

    while(h++<t)

    {

        long long te=q[h];

        for(long long i=lin[te];i;i=nex[i])

        {

            long long tn=ver[i];

            if(vis[tn]==)continue;

            d[tn]=max(d[tn],d[te]+e[i]);//取max更加严谨,尽管更慢

            if(d[tn]>cnt)cnt=d[tn],u=tn;

            q[++t]=tn;vis[tn]=;

        }

    }

    //cout<<u<<endl;

    memset(vis,,sizeof(vis));

    memset(d,,sizeof(d));

    h=,t=;cnt=;

    q[++t]=u;vis[u]=;

    //cout<<u<<endl;

    while(h++<t)

    {

        long long te=q[h];

        for(long long i=lin[te];i;i=nex[i])

        {

            long long tn=ver[i];

            if(vis[tn]==)continue;

            d[tn]=max(d[tn],d[te]+e[i]);//取max更加严谨,尽管更慢

            if(d[tn]>cnt)cnt=d[tn];

            q[++t]=tn;vis[tn]=;

        }

    }

    put(cnt);return;

}

void dfs(int x)

{

    for(int i=lin[x];i;i=nex[i])

    {

        int tn=ver[i];

        if(vis[tn]==)continue;

        vis[tn]=;

        d[tn]=max(d[tn],d[x]+e[i]);

        if(d[tn]>cnt)cnt=d[tn],u=tn;

        dfs(tn);

    }

}

int check2(int x)

{

    cnt=;int j=t+;//双指针

    for(int i=;i<=t;i++)if(q[i]>=x){j=i;break;}

    cnt+=t-j+;j--;

    for(int i=;i<j;i++)if(q[i]+q[j]>=x)j--,cnt++;

    if(cnt>=m)return ;

    return ;

}

void solve2()//菊花图

{

    h=,t=;

    for(int i=lin[];i;i=nex[i])q[++t]=e[i];

    sort(q+,q++t);

    //cout<<ans<<endl;

    //for(int i=1;i<=t;i++)cout<<q[i]<<endl;

    int l=,r=ans;

    while(l+<r)

    {

        int mid=(l+r)>>;

        if(check2(mid)==)l=mid;

        else r=mid;

    }

    if(check2(r)==)put(r);

    else put(l);return;

}

void solve3()

{

    memset(vis,,sizeof(vis));

    memset(d,,sizeof(d));

    dp();put(cnt);//树形dp求树的直径

    //bfs();//两次bfs求树的直径

    //两次dfs求树的直径

    /*memset(vis,0,sizeof(vis));

    memset(d,0,sizeof(d));

    cnt=0;vis[1]=1;dfs(1);

    memset(vis,0,sizeof(vis));

    memset(d,0,sizeof(d));

    cnt=0;vis[u]=1;dfs(u);

    put(cnt);*/

}

int main()

{

    //freopen("1.in","r",stdin);

    n=read();m=read();

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

    {

        long long x,y,z;

        x=read();y=read();z=read();

        add(x,y,z);add(y,x,z);

        if(x+!=y)flag=;//一条链的情况

        ru[x]++;ru[y]++;

        ans+=z;

        if(x!=)flag1=;

    }

    //cout<<flag1<<endl;

    if(flag==){solve1();return ;}//一条链

    if(flag1==){solve2();return ;}//菊花图

    if(m==){solve3();return ;}//求树的直径的情况，两遍bfs或树形dp

    return ;

}

55分很好写，一个直径一个二分一个双指针扫描。

可是考试的时候打了一个n^n的暴力。菜死了

正解是二分+树形dp+二分（二分的边界很重要要不卡死）

#include<iomanip>

#include<cstdio>

#include<cstring>

#include<string>

#include<cmath>

#include<ctime>

#include<queue>

#include<deque>

#include<bitset>

#include<set>

#include<vector>

#include<algorithm>

#include<stack>

#include<map>

#include<iomanip>

using namespace std;

inline long long read()

{

    long long x=,f=;char ch=getchar();

    while(ch<''||ch>''){if(ch=='-')f=-;ch=getchar();}

    while(ch>=''&&ch<=''){x=x*+ch-'';ch=getchar();}

    return x*f;

}

inline void put(long long x)

{

    if(x==){putchar('');putchar('\n');return;}

    if(x<)putchar('-'),x=-x;

    long long num=;char ch[];

    while(x)ch[++num]=x%+'',x/=;

    while(num)putchar(ch[num--]);

    putchar('\n');return;

}

const long long maxn=;

long long n,m;

long long lin[maxn<<],nex[maxn<<],ver[maxn<<],e[maxn<<],len=;

int ans=,u=,cnt=;

int f[maxn],v[maxn];//f[i]表示以i为根节点所能拼成最多的道路。

int q[maxn<<],t=;

//v[i]表示当前节点还剩下的最长链

void add(long long x,long long y,long long z)

{

    ver[++len]=y;

    nex[len]=lin[x];

    lin[x]=len;

    e[len]=z;

}

//赛道修建100分做法-->>树形dp

int check1(int x,int p)

{

    int sum=;

    for(int i=,j=t;i<j;i++)

    {

        if(i==x)continue;

        if(j==x)j--;

        if(q[i]+q[j]>=p)sum++,j--;

    }

    if(sum>=u)return ;

    return ;

}

void dp(int x,int p,int fa)

{

    for(int i=lin[x];i;i=nex[i])

    {

        int tn=ver[i];

        if(tn==fa)continue;

        dp(tn,p,x);

    }

    t=,u=;;cnt=;

    for(int i=lin[x];i;i=nex[i])

    {

        int tn=ver[i];

        if(tn==fa)continue;

        f[x]+=f[tn];

        if(e[i]+v[tn]>=p){cnt++;continue;}

        q[++t]=e[i]+v[tn];

    }

    sort(q+,q++t);

    for(int i=,j=t;i<j;i++)if(q[i]+q[j]>=p)u++,j--;

    int l=,r=t;//再次二分枚举哪条边不用来更新v[x]

    while(l+<r)

    {

        int mid=(l+r)>>;

        if(check1(mid,p)==)l=mid;

        else r=mid;

    }

    if(check1(r,p)==)v[x]=q[r];

    else v[x]=q[l];

    f[x]+=cnt+u;

}

int check(int x)

{

    memset(f,,sizeof(f));

    memset(v,,sizeof(v));

    dp(,x,);

    if(f[]>=m)return ;

    else return ;

}

void wy()//闻道玉门犹被遮

{

    int l=,r=ans;

    while(l+<r)//二分枚举当前修建的道路长度

    {

        int mid=(l+r)>>;

        if(check(mid)==)l=mid;

        else r=mid;

    }

    if(check(r)==)put(r);

    else put(l);

}

int main()

{

    //freopen("1.in","r",stdin);

    n=read();m=read();

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

    {

        int x,y,z;

        x=read();y=read();z=read();

        add(x,y,z);add(y,x,z);

        ans+=z;

    }

    wy();//应将性命逐轻车

    return ;

}

就这样没了 300分很简单。

秒客网

NOIP 2018 day1 题解

相关文章