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

CF1716题解

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);}
}

CF1746F

昨天讲随机化的时候讲了,就是考虑到所有数都是 k 的倍数,那么我们将去区间中的数*它的权值的加和,也是k的倍数

形式化的:

如果 \(cnt_i\) 是 k 的倍数

那么 \(\prod cnt_{a_i}*w_i\) 是 k 的倍数

但是因为我们弱化了题目的限制,很可能错误,所以随机化多随几次,每一个权值映射到另一个权值上即可

http://www.hskmm.com/?act=detail&tid=17220

相关文章:

  • 使用vosk模型进行语音识别
  • AI Agent如何重塑人力资源管理?易路iBuilder平台实战案例深度解析
  • docker-compose + macvlan + Elasticsearch - 9.1.4 + Kibana - 9.1.4
  • WinForm 计时器 Timer 学习笔记
  • RocketMQ入门:基本概念、安装、本地部署与集群部署 - 详解
  • 【LeetCode】122. 买卖股票的最佳时机 II
  • VSCode 使用技巧笔记
  • 【LeetCode】55. 跳跃游戏
  • Ansible + Docker 部署 Apache Kafka 3.9 集群
  • 【LeetCode】45. 跳跃游戏 II
  • 深入了解一波JVM内存模型
  • 什么是UDFScript用户自定义脚本
  • 【LeetCode】121. 买卖股票的最佳时机
  • CCPC2024-Zhengzhou G Same Sum(线段树)
  • Openwrt-DDNS 配置详解
  • 实用指南:Metal - 2. 3D 模型深度解析
  • 【2025.9.16】关于举办PostgreSQL数据库管理人才研修与评测班的通知
  • Java锁相关问题
  • CDN中使用边缘函数实现自定义编程
  • 第一次课程中的所有动手动脑的问题以及课后实验性的问题
  • 敏捷开发的几个阶段
  • 隐藏在众目睽睽之下:从PEB中解除恶意DLL的链接
  • 设计模式六大原则 - 实践
  • 运营商 API 安全最佳实践、案例与方案推荐(2025)|千万级接口的全链路实战
  • HyperWorks许可与多用户支持
  • react 中 keys 的作用是什么?
  • 破局与进化:火山引擎Data Agent从落地实践到架构未来
  • 五项能力斩获满分!天翼云云WAF获IDC权威认可!
  • 什么样的代码可以称得上是好代码? - 浪矢
  • 微软Teams Channel Agent上线:中国卖家AI赋能品牌出海新机遇与实战策略(2025前瞻) - 详解