Codeforces Global Round 16题解

时间:2024-08-10 00:03:20

E. Buds Re-hanging

对于这个题该开始还是没想法的,但这显然是个思维题,还是要多多动手推样例,实践一下。

简化题意:给定一个有根树,规定某个点为树干,当且仅当这个点不是根,且这个点至少有一个儿子,这个点的所有儿子都是叶子节点。每次可以将一个树干及其子树分离出来,然后将这个点与树上其他点相连。问:进行若干次操作之后,整个树的最少的叶子结点的个数?

首先我思考的是:我们这个树干从原来的父亲节点摘下来后要放到哪里,可以发现如果练到一个非叶子节点上的话,总的叶子数量是不会减少的,甚至有可能增多(因为原本树干的父亲可能成为新的叶子)。所以最优的情况一定是将这个树干连到一个叶子节点上。可以发现对于任意一个树的结构我们都可以从叶子节点往上,依次将他们拆离,也就是每次都将当前所有的树干摘离,那么最后只有两种结果,根节点不能被拆离,只剩下根节点一个点,根节点也能被摘离,整棵树都能被拆离。那么对于当前一个点x而言,我们要如何操作,才能使得整个的叶子节点最少。对于x的所有儿子y,我们期望的最优结果就是所有儿子都能够摘离除去,放到其中一个儿子身上,类似一个链的形状。这样的话,叶子节点最少。考虑这样我们需要儿子的那些信息,如何统计答案?首先需要儿子能不能被完全摘离,还有儿子内部经过调整之后的最少的叶子节点。起初令\(ans[x]=\sum ans[y]\),之后,若有一个儿子能够完全被摘离,那\(ans[x]--\),因为我们可以将y这个儿子及其子树全部摘离,放到另一个子树上,减少一个叶子结点。但有一种情况比较特殊,就是当全部的儿子都能被摘离时,我们要将\(ans[x]++\),因为我们至少留一个儿子放上面。那么考虑x是否能被摘离,若x的全部儿子都能被摘离,则x不能被摘离,否则x就能被摘离。直接树形DP即可。

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10;
int n,f[N];
vector<int>son[N];
inline bool dfs(int x,int fa)//bool表示能不能被摘离.
{
int children=0,cnt=0;//cnt表示能被摘离的儿子的个数。
for(auto y:son[x])
{
if(y==fa) continue;
children++;
if(dfs(y,x)) cnt++;
f[x]+=f[y];
}
f[x]-=cnt;
if(cnt==children) f[x]++;
if(children==0) {f[x]=1;return 0;}
return (cnt==children)?0:1;
}
int main()
{
// freopen("1.in","r",stdin);
int T;cin>>T;
while(T--)
{
cin>>n;
for(int i=1;i<=n;++i) son[i].clear();
for(int i=1;i<n;++i)
{
int x,y;cin>>x>>y;
son[x].push_back(y);
son[y].push_back(x);
}
memset(f,0,sizeof(f));
dfs(1,0);
cout<<f[1]<<endl;
}
return 0;
}

F. Points Movement

简化题意:给定你一些点和区间,点可以左右移动,当一个点处于某个线段中时成这个区间被访问过,问最少移动的次数使得所有的区间被访问过?

首先可以发现一些小的结论,若某个区间完全包含另一个区间的话,则那个大的区间就不必考虑了,因为若访问过小的区间,则大的区间也一定被访问了。其次,对于初始位置而言,若某个点在某个区间内的话,则这个区间也不用被考虑。这样的话,我们将不必考虑的区间都剔除,考虑剩下的区间和点构成什么了?我们将区间按左端点排序,可以发现右端点一定也是有序的,若出现有序,则一定会出现大包小的情况,在第一步就被我们剔除掉了。剩下的点和区间一定是相间分布的,即点,区间,点,区间...这样分布的,其次我们考虑某个区间被访问时一定只是其端点被访问,且访问的点一定是向左,向右离他最近的点,也就是说点的移动不会跨过另一个点,否则我们移动另一个点一定更优。

考虑以下这个区间我们有多少种情况:

Codeforces Global Round 16题解

首先这三个区间我们一定是用A和B移动去访问他们,那这里就有以下方案:

1.A去\(L_3\)

2.A去\(L_2\),B去\(R_3\)

3.A去\(L_1\),B去\(R_2\)

4.B去\(R_1\)

发现这里的方案数为O(K)k是区间的数量。但考虑到如果某两个区间的中间夹的点数只有一个。那么这个点可能先往左边跑,之后再往右边跑,这个怎么解决,所以我们需要知道点的位置。由于每个点左右跑的话一定会回到原位置,所以我们可以分开统计答案,每个点可以到某个区间端点不动了,也可以到区间端点再返回原位置,所以我们记录f[i][0/1]表示第i个点之前所有的区间都访问过,且这个点不返回位,返回原位,的最少的移动步数。注意这里点左右跑的话可能有两个选择,可以先向左边跑,再向右边跑,也可以先向右边跑,再向做边跑。注意转移状态的时候别漏就行。

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=2e5+10;
int n,m;
ll f[N][2],a[N],L[N],R[N];
struct segment{int l,r;};
vector<segment>v;
inline bool cmp(segment x,segment y)
{
return (x.l!=y.l)?(x.l<y.l):(x.r>y.r);
}
int main()
{
//freopen("1.in","r",stdin);
int T;cin>>T;
while(T--)
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;++i) scanf("%lld",&a[i]);
sort(a+1,a+n+1);v.clear();
for(int i=1;i<=m;++i)
{
int l,r;scanf("%d%d",&l,&r);
int id=lower_bound(a+1,a+n+1,l)-a;
if(id==n+1||a[id]>r)
{
v.push_back((segment){l,r});
}
}
sort(v.begin(),v.end(),cmp);
for(int i=0;i<v.size();++i)
{
if(i!=0&&v[i].r<=v[i-1].r)
{
v.erase(v.begin()+i-1);
i-=2;
}
}
for(int i=1;i<=n+1;++i) f[i][0]=f[i][1]=1e18;
f[0][0]=f[0][1]=0;
a[0]=-1e18;a[n+1]=1e18;
int now=0;//now表示当前处理到的区间。
for(int i=1;i<=n+1;++i)
{
int cnl=0,cnr=0;//L表示左边点到达的终点,R表示右边点到达的终点。
L[++cnl]=a[i-1];
while(now<v.size()&&v[now].r<a[i])
{
L[++cnl]=v[now].l;
R[++cnr]=v[now].r;
++now;
}
R[++cnr]=a[i];
for(int j=1;j<=cnl;++j)
{
f[i][0]=min(f[i][0],f[i-1][1]+L[j]-a[i-1]+a[i]-R[j]);
f[i][1]=min(f[i][1],f[i-1][1]+L[j]-a[i-1]+(a[i]-R[j])*2);
f[i][0]=min(f[i][0],f[i-1][0]+(L[j]-a[i-1])*2+a[i]-R[j]);
f[i][1]=min(f[i][1],f[i-1][0]+(L[j]-a[i-1])*2+(a[i]-R[j])*2);
}
}
printf("%lld\n",min(f[n+1][1],f[n+1][0]));
}
return 0;
}