当前位置：首页 > news >正文

CF1716题解

news 2025/10/27 1:34:51

CF1716A

不难发现，只保留一个1即可，其余的怎么变都可以，所以变成k个后，直接取max在序列中有1的情况下必然可以构造出来

点击查看代码

#include<bits/stdc++.h>
using namespace std;
const int N=55;
int t,n,k,ans;
int a[N];
int main(){scanf("%d",&t);while(t--){scanf("%d%d",&n,&k);ans=0;for(int i=1;i<=n;i++){scanf("%d",&a[i]);if(a[i]==1)  ans=1;}if(ans)  printf("YES\n");else  printf("NO\n");}
}

CF1716B

把前面的1补到后面的0上面是最优的，两边维护一下指针即可

没想到上面的做法，我直接二分过的

点击查看代码

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+5;
int t,n,k,n1,n0;
int a[N],b[N];
vector<int>num1,num0;
bool check(int x){for(int i=1;i<=n;i++)  b[i]=a[i];for(int i=0;i<x;i++){b[num1[i]]=-1;b[num0[i]]=-1;}int cnt=0;for(int i=1;i<=n;i++){if(b[i]==1)  cnt=1;if(cnt==1&&b[i]==0)  return 0;}return 1;
}
int main(){scanf("%d",&t);while(t--){scanf("%d",&n);for(int i=1;i<=n;i++){scanf("%d",&a[i]);}num1.clear(),num0.clear();for(int i=1;i<=n;i++){if(a[i]==1)  num1.push_back(i);}for(int i=n;i>=1;i--){if(a[i]==0)  num0.push_back(i);}n1=num1.size(),n0=num0.size();int l=0,r=min(n1,n0);while(l<r){int mid=(l+r)>>1;if(check(mid))  r=mid;else  l=mid+1;}printf("%d\n",l);}
}

CF1716C

发现改变一个后缀，根本上只能影响当前的位置和之前为值的前后逆序关系

然后可以改变n次，也就是的都能改一次，所以最终不会有逆序对

构造方法，i只需要加上比 \(a_{i-1}-a_i\) 大的数就行

点击查看代码

#include<bits/stdc++.h>
#define pii pair<int,int>
using namespace std;
const int N=2e5+5;
int t,n;
int a[N];
pii b[N];
int main(){scanf("%d",&t);while(t--){scanf("%d",&n);for(int i=1;i<=n;i++){scanf("%d",&a[i]);}int cnt=0;b[++cnt]={0,1};for(int i=2;i<=n;i++){int g=max(a[i-1]-a[i],0);b[++cnt]={g,i};}sort(b+1,b+cnt+1);for(int i=1;i<=n;i++){printf("%d ",b[i].second);}printf("\n");}
}

CF1716D

首先考虑到对于一个父亲，他的儿子一定要先平均分配才能满足条件

其次考虑到贪心：一条路径肯定是选到叶子结点最优

然后考虑平均分后还有 \(k%son_u\) 个路径没有分配，他们需要贪心的分给儿子中大的即可

点击查看代码

#include<bits/stdc++.h>
#define int long long
#define pii pair<int,int>
#define se second
using namespace std;
const int N=2e5+5;
int t,n,k,ans;
int p[N],s[N],son[N],dp[N];
vector<int>b[N];
void dfs1(int u){dp[u]=s[u];for(int v:b[u]){dfs1(v);dp[u]=max(dp[u],dp[v]+s[u]);}
}
void dfs2(int u,int c){ans+=s[u]*c;if(!son[u])  return;priority_queue<pii>q;int g=c%son[u];for(int v:b[u]){q.push({dp[v],v});}for(int i=1;i<=g;i++){dfs2(q.top().se,c/son[u]+1);q.pop();}while(!q.empty()){dfs2(q.top().se,c/son[u]);q.pop();}
}
signed main(){scanf("%lld",&t);while(t--){scanf("%lld%lld",&n,&k);for(int i=1;i<=n;i++)  son[i]=dp[i]=0,b[i].clear();for(int i=2;i<=n;i++){scanf("%lld",&p[i]);b[p[i]].push_back(i);son[p[i]]++;}for(int i=1;i<=n;i++){scanf("%lld",&s[i]);}ans=0;dfs1(1);dfs2(1,k);printf("%lld\n",ans);}
}