(寒假开黑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;
}