Codeforces Round #722 (Div. 2)
A
题意
给一个数组，每次操作可以任意选一个子序列，如何删除其中严格大于子序列平均值的元素。可以操作无数次，求最多可以删除多少元素。
思路
因为可以任选，所以所有大于数组最小值的元素都可以选择与最小值加入一个子序列，所以答案就是大于最小值的元素个数。
代码
#include<bits/stdc++.h>
using namespace std;
const int MAX=1e3+5;
int a[MAX];
int main()
{
int T;
cin>>T;
while(T--)
{
int n,cnt=0,minn=101;
cin>>n;
for(int i=0;i<n;i++)
{
cin>>a[i];
minn=min(minn,a[i]);
}
for(int i=0;i<n;i++)
if(a[i]>minn)cnt++;
cout<<cnt<<endl;
}
}
B
给一个数组，可以选择一个子序列，要求其中所有元素两两的距离（差的绝对值）不小于子序列中最大的元素。求此子序列可能的最大长度。
思路
显然，负数与0可以任意选，正数最多只能选一个，因为两个正数之间的距离一定小于他们二者的最大值。故先把所有的负数与0选到，再根据已经选择的元素两两距离的最小值，判断能否选一个正数。因为正数最多只能选一个，故因为选择负数与0导致正数不能选择这种情况的结果一定不差于使得子序列合法并且选一个正数的情况。所以可以把负数与0全选。
代码
#include<bits/stdc++.h>
using namespace std;
const int MAX=1e5+5;
typedef long long ll;
ll a[MAX];
int main()
{
int T;
scanf("%d",&T);
while(T--)
{
int n;
scanf("%d",&n);
for(int i=0;i<n;i++)
scanf("%I64d",&a[i]);
sort(a,a+n);
int res=0;
for(int i=0;i<n;i++)
{
if(a[i]>0)break;
res++;
}
ll minn=1e10;
for(int i=1;i<n;i++)
{
if(a[i]>0)
{
if(a[i]<=minn)res++;
break;
}
minn=min(minn,a[i]-a[i-1]);
}
printf("%d\n",max(1,res));
}
}
C
题意
给一棵n个节点的树，每个节点有一个取值范围，可以在此范围内确定该节点的权值。令某边的权值为该边连接的两个节点的权值之差（取绝对值），如何确定权值，使得树的所有边权之和最大。求此最大值。
思路
对于某一个节点，可以抽象成如下情况：
其中该节点的权值未确定，而相邻节点的权值已经确定，分别为X，Y，Z。则有如下图
由此图可以推断，在数轴上
- 当所有相邻节点的值位于当前节点区间外时，则当前节点一定取边界值。
- 当所区间左右两侧均有相邻节点时，则取值任意取都不会影响结果。
- 当区间内部和两侧都有时，则当前节点也一定取边界值。
故得出结论，某节点一定取区间边界值。那么状态与决策就是取左边界还是右边界，然后使用树形DP解决。
代码
#include<bits/stdc++.h>
using namespace std;
const int MAX=1e5+5;
vector<int>T[MAX];
typedef long long ll;
ll l[MAX],r[MAX];
ll dp[MAX][2];
ll dfs(int x,int fa)
{
for(int i=0;i<T[x].size();i++)
{
int y=T[x][i];
if(y==fa)continue;
dfs(y,x);
dp[x][0]+=max(dp[y][1]+abs(l[x]-r[y]),dp[y][0]+abs(l[x]-l[y]));
dp[x][1]+=max(dp[y][1]+abs(r[x]-r[y]),dp[y][0]+abs(r[x]-l[y]));
}
}
int main()
{
int TT;
scanf("%d",&TT);
while(TT--)
{
int n,x,y;
scanf("%d",&n);
for(int i=0;i<=n;i++)
T[i].clear(),dp[i][0]=dp[i][1]=0;
for(int i=1;i<=n;i++)
scanf("%I64d%I64d",&l[i],&r[i]);
for(int i=1;i<n;i++)
{
scanf("%d%d",&x,&y);
T[x].push_back(y);
T[y].push_back(x);
}
dfs(1,-1);
printf("%I64d\n",max(dp[1][0],dp[1][1]));
}
}
D
题意
给数轴上1-2n共2n个点，两点之间可以连线形成一个区间。求使得满足如下条件的连线方法数量。
使得所有区间中任意两个区间，要不相互包含，要不拥有相同的长度。
思路
方案可以分为两类。一类为除了最大区间外，所有区间均被某区间包含，另一类为所有区间长度相等。显然这个问题具有动态规划的特征。
令dp[i]表示有2i个点时的方案数。则有
\[dp[n]=\sum_{i=1}^{n-1}dp[i] \]因为可以取1-2n为一个大区间，中间即为长度为n-1的子问题。同理可以取1-2n与2-2n-1两层区间，中间为长度为n-2的子问题，显然这样的方案是合法的。
但是此时并没有考虑到全部。还有所有区间相等的情况。假设区间长度为x，则所有区间相等且区间可以铺满1-2n的情况为，从1开始，区间起点填满1-x内，这样为一个元素，使得元素长度能铺满1-2n，即
\[2n\mod2x=0 \]故只有x为n的因子时才能铺满。故所有区间长度相等的情况数量为n的因子数量（包括1与n）。
但是如果每次转移都求n的因子数量的话会超时，故预处理枚举因子，将每个因子生成的数的因子数量++。
代码
#include<bits/stdc++.h>
using namespace std;
const int MAX=1e6+6;
int dp[MAX];
int mod=998244353;
int main()
{
int n;
scanf("%d",&n);
int sum=0;
dp[1]=1;
for(int i=2;i<=n;i++)
{
dp[i]+=1;
for(int j=i;j<=n;j+=i)
dp[j]++;
}
for(int i=1;i<=n;i++)
{
dp[i]=(dp[i]+sum)%mod;
sum=(sum+dp[i])%mod;
}
printf("%d\n",dp[n]);
}
E
题意
给均为n个节点的两棵树A，B，以及一张只有n个节点的没有边的图，如果两个节点满足：
- 他们在A树中一个是另一个的祖先。
- 他们在B树中互相不为对方的祖先。
则可以在图中连边。求最终的图的最大完全子图的大小。
思路
因为可能对答案有贡献的节点都在A图的一条链路中，所以可以在A图中DFS时维护，在A图中DFS得到的一个节点集合自然满足条件1，只需要测试是否满足条件2即可。
条件2可以对B树求欧拉序，再用线段树维护解决。
在B树中进行DFS求欧拉序，令s[x]表示节点x初次出现的位置，t[x]表示节点x第二次出现的位置。如果x在答案集合中，则用线段树对区间s[x]-t[x]+1。如果出现某节点s[x]-t[x]的区间和不为0，则证明该节点是某节点的后代，或该节点是某节点的祖先。
思考如何判断某新加入的节点A是答案集合中某节点B的祖先还是后代。如果A是B的后代，那么s[A]-t[A]一定全为1，如果A是B的祖先，那么s[A]与t[A]的位置一定为0。
故可以用区间和是否等于区间长度来判断。
再考虑如果A与B有祖先后代的关系时如何维护答案集合。可以想到，如果一个节点U与另一个节点V不在同一条链上，则其后代也一定不与V在同一条链上，并且越靠近叶子节点，与其他节点在一条链的可能性越低，即后代对答案的贡献一定不差于祖先。那么维护答案集合的方法就很清晰了。
- 如果A是B的祖先，那么直接抛弃A。
- 如果A是B的后代，那么在答案集合中用A替换B。
- 如果二者无关，则将A加入答案集合。
所以在A树中DFS，同时用线段树动态维护答案集合。还需注意维护答案集合状态的细节，被替换的节点需要被恢复，直接用树的父亲关系完成替换祖先等。总体复杂度O(nlogn)。
代码
#include<bits/stdc++.h>
using namespace std;
const int MAX=3e5+5;
struct data
{
int sum;
} tree[MAX<<3];
int add[MAX<<3],s[MAX],t[MAX],f[MAX],timer,n,res;
vector<int>T1[MAX],T2[MAX];
set<int>st;
void pushup(int rt)
{
int ls=rt<<1,rs=rt<<1|1;
tree[rt].sum=tree[ls].sum+tree[rs].sum;
}
void pushdown(int rt,int ln,int rn)
{
if(!add[rt])return;
int ls=rt<<1,rs=rt<<1|1;
add[ls]+=add[rt];
add[rs]+=add[rt];
tree[ls].sum+=add[rt]*ln;
tree[rs].sum+=add[rt]*rn;
add[rt]=0;
}
void build(int l,int r,int rt)
{
if(l==r)
{
tree[rt].sum=0;
return ;
}
add[rt]=0;
int m=(l+r)>>1;
build(l,m,rt<<1);
build(m+1,r,rt<<1|1);
pushup(rt);
}
void update_segment(int L,int R,int C,int l,int r,int rt)
{
if(L<=l&&r<=R)
{
tree[rt].sum+=C*(r-l+1);
add[rt]+=C;
return;
}
int m=(l+r)>>1;
pushdown(rt,m-l+1,r-m);
if(L<=m)
update_segment(L,R,C,l,m,rt<<1);
if(R>m)
update_segment(L,R,C,m+1,r,rt<<1|1);
pushup(rt);
}
int query(int L,int R,int l,int r,int rt)
{
if(L<=l&&r<=R)
{
return tree[rt].sum;
}
int ans=0,m=(l+r)>>1;
pushdown(rt,m-l+1,r-m);
if(L<=m)
ans+=query(L,R,l,m,rt<<1);
if(R>m)
ans+=query(L,R,m+1,r,rt<<1|1);
return ans;
}
void dfs2(int x,int fa)
{
s[x]=++timer;
for(int i=0; i<T2[x].size(); i++)
{
int y=T2[x][i];
if(y==fa)continue;
dfs2(y,x);
}
t[x]=++timer;
}
void dfs1(int x,int fa)
{
int del=-1;
if(x!=1)
{
int Q=query(s[x],t[x],1,2*n,1);
if(!Q)
{
st.insert(x);
res=max(res,int(st.size()));
update_segment(s[x],t[x],1,1,2*n,1);
}
else if(Q==t[x]-s[x]+1)
{
int xx=x;
while(!st.count(xx))xx=f[xx];
st.erase(xx);
del=xx;
update_segment(s[xx],t[xx],-1,1,2*n,1);
update_segment(s[x],t[x],1,1,2*n,1);
st.insert(x);
}
}
for(int i=0; i<T1[x].size(); i++)
{
int y=T1[x][i];
if(y==fa)continue;
dfs1(y,x);
}
if(del!=-1)
{
st.insert(del);
update_segment(s[del],t[del],1,1,2*n,1);
}
update_segment(s[x],t[x],-1,1,2*n,1);
st.erase(x);
}
int main()
{
int T;
scanf("%d",&T);
while(T--)
{
scanf("%d",&n);
for(int i=1; i<=n; i++)
T1[i].clear(),T2[i].clear();
st.clear();
build(1,2*n,1);
res=1;
timer=0;
for(int i=2; i<=n; i++)
{
scanf("%d",&f[i]);
T1[f[i]].push_back(i);
T1[i].push_back(f[i]);
}
for(int i=2; i<=n; i++)
{
scanf("%d",&f[i]);
T2[f[i]].push_back(i);
T2[i].push_back(f[i]);
}
dfs2(1,-1);
dfs1(1,-1);
printf("%d\n",res);
}
}