题解

NOIP2018

D1T1:road(铺设道路)

居然出原题! 我 抄 我 自 己

直接上代码,没什么好说的

#include<iostream>
#include<cstdio>
using namespace std;
int n,x,y,ans;
int main(){
    scanf("%d",&n);
    for (int i=1;i<=n;i++){
        scanf("%d",&x);
        ans+=y>x?0:x-y,y=x;
    }
    printf("%d",ans);
    return 0;
}

D1T2:money(货币系统)

很多人没有想到背包的算法

同样是水题,直接上代码

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int a[25001],n,t;
bool v[25001];
int main(){
    scanf("%d",&t);
    while (t--){
        memset(v,0,sizeof(v));v[0]=true;
        scanf("%d",&n);
        for (int i=1;i<=n;i++) scanf("%d",&a[i]);
        sort(a+1,a+n+1);
        int maxn=a[n],num=0;
        for (int i=1;i<=n;i++)
            if (v[a[i]]) num++;
            else 
                for (int j=a[i];j<=maxn;j++)
                    if (v[j-a[i]]) v[j]=true;
        printf("%d\n",n-num);
    }
    return 0;
}

D1T3:track(赛道修建)

核心思想二分加树型DP(STL真香

简化这道题,可以理解为能够从一颗树中找到m条长度大于等于c的链时,c的最大值

那么不难想到用二分

DP维护两个值,一个是在以i为根节点的子树中能够选取的最多的长度大于等于c的链的数量,记为f[i]

另一个是在以i为根节点的子树中删除掉之前取用的的链的情况下,以i为一个端点的最长链的长度,记为g[i]

那么f[i]=sum{f[j]}(j是i的子节点),同时存储所有的f[j]+w(i,j),对于其中的每一个元素,如果该元素>=c,则f[i]++,否则找到另一个未被取用的元素,使得这两个元素之和>=c,并f[i]++,最后剩余的最大的未被取用的元素就作为g[i]的值。

最后f[1]表示在这棵树中能取得的最多的链的数量。

代码如下(似乎不开02会被卡到80分

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<set>
using namespace std;
#define N 50001
#define M 100001
int hd[N],nx[M],e[M],w[M];
int f[N],g[N],q[N];
int n,m,num=0;
void dfs(int x,int y,int c){
    multiset<int> h;
    vector<int> q;
    f[x]=g[x]=0;
    for (int i=hd[x];i;i=nx[i])
        if (e[i]!=y){
            dfs(e[i],x,c);
            f[x]+=f[e[i]];
            if (g[e[i]]+w[i]>=c) f[x]++;
            else{
                q.push_back(g[e[i]]+w[i]);
                h.insert(g[e[i]]+w[i]);    
            }
        }
    sort(q.begin(),q.end());
    vector<int>::iterator i;
    multiset<int>::iterator j;
    for (i=q.begin();i!=q.end();i++)
        if (h.count(*i)){
            h.erase(h.find(*i));
            j=h.lower_bound(c-*i);
            if (j==h.end()) g[x]=*i;
            else{
                f[x]++;
                h.erase(j);
            }
        }
}
bool check(int c){
    dfs(1,1,c);
    return (f[1]>=m);
}
int main(){
    int x,y,z,l=2146483647,r=0,ans=0;
    memset(hd,0,sizeof(hd)); 
    scanf("%d%d",&n,&m);
    for (int i=1;i<n;i++){
        scanf("%d%d%d",&x,&y,&z);
        nx[++num]=hd[x],hd[x]=num,e[num]=y,w[num]=z;
        nx[++num]=hd[y],hd[y]=num,e[num]=x,w[num]=z;
        if (z<l) l=z;
        r+=z*2;
    }
    while (l<r){
        int mid=(l+r)>>1;
        if (check(mid)) l=mid+1,ans=mid;
        else r=mid,ans=mid-1;
    }
    printf("%d\n",ans);
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注