目录
-
- 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;
}