(寒假开黑gym)2018 ACM-ICPC, Syrian Collegiate Programming Contest（爽题）

时间：2024-01-09 15:49:32

layout: post

title: (寒假开黑gym)2018 ACM-ICPC, Syrian Collegiate Programming Contest（爽题）

author: "luowentaoaa"

catalog: true

tags:

mathjax: true

- codeforces

- DP

- 状态压缩

- LCA

传送门

付队！

C - Greetings! （状态压缩）

题意

给N种信件，你可以任意选择K种信封装信件，问你最少的浪费是多少

不能大的信件装进小信封中

思路

首先如果可以选择的信封数量比N大 那么每一种信件用一个特定的信封肯定不会有浪费

因为数据很小我们考虑状态压缩考虑哪些信件用同一种信封

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

typedef unsigned long long ull;

const ll mod=1e9+7;

const int maxn=(1<<16)+50;

const int inf=1e8;

ll c[maxn];

struct node{

    ll w,h,t;

}my[20];

ll dp[20][maxn];

int main()

{

    int n,k;

    cin>>n>>k;

    memset(dp,127,sizeof(dp));

    for(int i=0;i<n;i++)cin>>my[i].w>>my[i].h>>my[i].t;

    for(int i=0;i<(1<<n);i++){

        ll ww=0,hh=0,sum=0,cnt=0;

        for(int j=0;j<n;j++){

            if(i&(1<<j)){

                sum+=my[j].w*my[j].h*my[j].t;

                ww=max(ww,my[j].w);

                hh=max(hh,my[j].h);

                cnt+=my[j].t;

            }

        }

        dp[1][i]=c[i]=(ww*hh*cnt-sum);

    }

    for(int i=2;i<=k;i++){

        dp[i][0]=0;

        for(int sta=0;sta<(1<<n);sta++){

            for(int t=sta;t;t=(t-1)&sta){

                dp[i][sta]=min(dp[i][sta],dp[i-1][t]+c[sta^t]);

            }

        }

    }

    cout<<dp[k][(1<<n)-1];

    return 0;

}

F - Mountain Scenes (DP)

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

typedef unsigned long long ull;

const ll mod=1e9+7;

const int maxn=5e5+50;

const int inf=1e8;

ll dp[150][25000];

int main()

{

   int n,w,h;

   cin>>n>>w>>h;

   dp[0][0]=1;

   for(int i=1;i<=w;i++){

        for(int j=0;j<=n;j++){

            for(int k=0;k<=h;k++){

                dp[i][j+k]+=dp[i-1][j];

                dp[i][j+k]%=mod;

            }

        }

    }

    ll ans=0;

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

        ans+=dp[w][i];

        ans%=mod;

    }

    if(w*h<=n)ans=(ans-h+mod-1)%mod;

    else ans=(ans-n/w+mod-1)%mod;

    cout<<ans<<endl;

    return 0;

}

I - Tourists (LCA)

思路

很像wls面试我时出的题目

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

typedef unsigned long long ull;

const ll mod=1e9+7;

const int maxn=2e5+50;

const int inf=1e8;

int Next[maxn<<1],To[maxn<<1],Laxt[maxn<<1];

int cnt;

void add(int u,int v){

    Next[++cnt]=Laxt[u];Laxt[u]=cnt;To[cnt]=v;

}

int n;

int fa[maxn][50],dep[maxn];

void dfs(int u,int faa){

    fa[u][0]=faa;

    dep[u]=dep[faa]+1;

    for(int i=Laxt[u];i;i=Next[i]){

        if(To[i]==faa)continue;

        dfs(To[i],u);

    }

}

void init(){

    for(int i=1;i<=20;i++){

        for(int j=1;j<=n;j++){

            int f=fa[j][i-1];

            fa[j][i]=fa[f][i-1];

        }

    }

}

int lca(int p,int q){

    if(dep[p]<dep[q])swap(p,q);

    for(int i=20;i>=0;i--){

        if(dep[fa[p][i]]>=dep[q])p=fa[p][i];

    }

    if(p==q)return q;

    for(int i=20;i>=0;i--){

        if(fa[p][i]!=fa[q][i]){

            p=fa[p][i];q=fa[q][i];

        }

    }

    return fa[p][0];

}

int main()

{

    scanf("%d",&n);

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

        int u,v;

        scanf("%d%d",&u,&v);

        add(u,v);add(v,u);

    }

    dfs(1,0);

    ll ans=0;

    init();

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

        for(int j=2*i;j<=n;j+=i){

            int f=lca(i,j);

            ans+=dep[i]+dep[j]-2*dep[f]+1;

        }

    }

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

    return 0;

}

相关文章