目錄
-
- D.Keeping on track
- E*A Question of Ingestion
題目連結
D.Keeping on track
題意：給出一棵有n（n≤10 000）條邊的樹，存在且僅存在一個critical結點，使得删除該critical結點後，不連通的結點對最多。
①求出删除該critical結點後不連通的結點對的數量n1。
②在删除critical結點後加一條最優的邊，使得恢複連通的結點對最多，同時求出加上該最優邊後依舊不連通的結點對的數量n2。
比賽時寫的并查集+帶判斷的暴力删點[Accept]思路：
暴力枚舉與最大度數相差range以内的點為删點，對剩下的點用帶權并查集求不連通的節點對數量。結果取所有枚舉的max
！非正解，range試了幾次，取100時TLE，取1時WA，取10時AC
#include<iostream>
#include<stdio.h>
#include<string.h>
#include<map>
#include<algorithm>
#include<queue>
#include<math.h>
#include<vector>
using namespace std;
#define Inf 0x7fffffff
typedef long long ll;
const int N=11000;
int l[N],r[N],n,all,n1,n2,du[N],fa[N];
int siz[N],st[N],cnt,n1_,n2_;
int find(int u){
if(fa[u]!=u)fa[u]=find(fa[u]);
return fa[u];
}
int main(){
cin>>n;
for(int i=1;i<=n;i++){
scanf("%d%d",&l[i],&r[i]);
du[l[i]]++;
du[r[i]]++;
}
int id=0;
for(int i=1;i<=n;i++)if(du[i]>du[id])id=i;
all=n*(n-1)/2;
for(int k=0;k<=n;k++){
if(du[id]-du[k]<=10){
n1=n2=0;
for(int i=0;i<=n;i++)fa[i]=i,siz[i]=1;
cnt=0;
}else continue;
for(int i=1;i<=n;i++){
if(l[i]!=k&&r[i]!=k){
int fx=find(l[i]),fy=find(r[i]);
if(fx!=fy){
siz[fy]+=siz[fx];
fa[fx]=fy;
}
}
}
int sum=0;
for(int i=0;i<=n;i++){
if(i==k)continue;
if(fa[i]==i){
st[++cnt]=siz[i];
sum+=siz[i]*(siz[i]-1)/2;
}
}
n1=all-sum;
sort(st+1,st+1+cnt);
sum-=st[cnt]*(st[cnt]-1)/2+st[cnt-1]*(st[cnt-1]-1)/2;
sum+=(st[cnt]+st[cnt-1])*(st[cnt]+st[cnt-1]-1)/2;
n2=all-sum;
if(n1>n1_){n1_=n1;n2_=n2;}
}
cout<<n1_<<" "<<n2_;
}
正解思路：因為是n+1個點n條邊的連通圖，是以任取一點為根把圖轉化為樹，dfs求出每個節點的每個子節點的size，目前點到根那一邊的連通分量大小為n+1-∑size[all_son]。求出最大n1，再使删除目前點後的兩個最大連通分量連通，計算n2。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<map>
#include<set>
#include<algorithm>
#include<cmath>
#include<string.h>
#include<queue>
#include<vector>
using namespace std;
typedef long long ll;
const int N=11000;
int n,fa[N],siz[N],n1,n2,id,son[N],cnt;
vector<int>v[N];
void dfs(int k){
if(k&&v[k].size()==1)return;
for(auto &i:v[k]){
if(i==fa[k])continue;
fa[i]=k;
dfs(i);
siz[k]+=siz[i];
}
}
int main(){
cin>>n;
siz[0]=1;
for(int i=1;i<=n;i++){
int x,y;
scanf("%d%d",&x,&y);
v[x].push_back(y);
v[y].push_back(x);
siz[i]=1;
}
dfs(0);
for(int i=0;i<=n;i++){
int now=0;
now+=(n+1-siz[i])*(n-siz[i])/2;
for(auto &j:v[i])
if(j!=fa[i])now+=siz[j]*(siz[j]-1)/2;
if((n)*(n-1)/2-now>n1){
n1=n*(n-1)/2-now;
id=i;
}
}
son[++cnt]=n+1-siz[id];
for(auto &j:v[id])
if(j!=fa[id])son[++cnt]=siz[j];
sort(son+1,son+1+cnt);
n2=n1-son[cnt]*son[cnt-1];
cout<<n1<<" "<<n2;
}
E*A Question of Ingestion
題意：n天，每天有一個食物量。一開始有一個最大胃口表示你最開始能吃多少食物。如果你昨天吃了，那麼今天的胃口為昨天的2/3。如果你前天吃了、昨天沒吃，那麼你的胃口可以恢複到前天的情況。如果你有連續兩天沒吃了，那麼你就可以恢複到最大胃口了。問怎樣安排使一共吃到的食物最多
思路：先根據題意，每x天的飯量取值隻能為m*[(2/3) ^ x],x取值為0,1,2…n,是以我們可以先把每天飯量的可能取值求出來，存進數組e裡。
然後定義dp[i][j]表示第i天，飯量為e[j]時，吃掉的食物總量。
先把初始值設為-1，表示未指派。然後讓dp[i][0]全等于0，表示一直不吃的情況。
然後分類讨論：
今天吃完後的分值為dp[i][j]+min(e[j],a)，記為aftereat
· 今天吃，明天也吃：dp[i+1][j+1]=max(dp[i+1][j+1],aftereat)
· 今天吃，明天不吃，後天吃：dp[i+2][j]=max(dp[i+2][j],aftereat)
· 今天吃，明天不吃，後天也不吃，大後天吃：dp[i+3][0]=max(dp[i+3][0],aftereat)
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=107;
int n,m,dp[N][N],e[N];
int main(){
cin>>n>>m;
memset(dp,-1,sizeof(dp));
for(int i=1;i<=n;i++)dp[i][0]=0;
e[0]=m;
for(int i=1;i<=n;i++)e[i]=e[i-1]*2/3;
for(int i=1;i<=n;i++){
int a;
scanf("%d",&a);
for(int j=0;j<=n;j++){
if(dp[i][j]<0) continue;
int aftereat=dp[i][j]+min(e[j],a);
dp[i+1][j+1]=max(dp[i+1][j+1],aftereat);
dp[i+2][j]=max(dp[i+2][j],aftereat);
dp[i+3][0]=max(dp[i+3][0],aftereat);
}
}
int ans=0;
for(int j=0;j<=n;j++) ans=max(ans,dp[n+1][j]);
cout<<ans;
return 0;
}