Codeforces Round #835(div4) A~G题解

news/2024/4/23 13:43:24/

前言

也是好久没有打div4了,上一次还是半年前的第二场cf比赛,记得当时过了3题,非常开心。这一次过了5个题,D题调试时间太久,导致F题最后没时间调试了。总之还不错。
Codeforces Round #835(div4)补题链接

A. Medium Number 签到

题意:给你三个数,求中位数。
Acwing周赛原题,写个数组,排序一下,然后输出中间即可。

#include<bits/stdc++.h>
using namespace std;
int main()
{int T;cin>>T;while(T--){int a[3];cin>>a[0]>>a[1]>>a[2];sort(a,a+3);cout<<a[1]<<endl;}return 0;
}

B Atilla’s Favorite Problem 签到

题意:给你一个字符串,找到ASCII码最大的字符。输出字母表中的位置。
思路:直接暴力扫一遍,更新最大值即可,记得下标需要+1。
代码:

#include<bits/stdc++.h>
using namespace std;
int main()
{int T;cin>>T;while(T--){int n;cin>>n;string s;cin>>s;int ans=0;for(int i=0;i<n;i++){ans=max(ans,s[i]-'a'+1);}cout<<ans<<endl;}return 0;
}

C. Advantage 签到

题意:给定一串序列,求出每个序列与除他以外最大的值得差值。
思路:求出最大值和次大值。对于不等于最大值的,直接用它减去最大值,反之,减去次大值。
最大值和次大值可以维护,我就直接备份了一个数组,然后直接排序求了。
代码:

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int a[N],b[N];
int main()
{int T;cin>>T;while(T--){int n;cin>>n;for(int i=0;i<n;i++){cin>>a[i];b[i]=a[i];}sort(b,b+n);for(int i=0;i<n;i++){if(a[i]!=b[n-1]) cout<<a[i]-b[n-1]<<" ";else cout<<a[i]-b[n-2]<<" ";}cout<<endl;}return 0;
}

D. Challenging Valleys 思维

题意:如果一段序列只存在一段“谷”,那么输出“Yes”,否则输出“No”。所谓“谷”,要么首段上升,要么尾端下降,或者先下降,在上升。
思路:因为只能有一个“谷”出现,我们发现,如果序列上升了,那么就必须一直上升,否则就会存在多个“谷”。(因为你上升了然后又下降,只有两种情况,一种一直下降到最后,那么就会有首端和尾端两个谷,不满足题意,如果你上升下降后面又上升,那么就有首段一个谷,下降上升又一个谷,两个谷,不满足题意)
代码:

#include<bits/stdc++.h>
using namespace std;
const int N =2e5+10;
int a[N];
int main(){int T;cin>>T;while(T--){int n;cin>>n;for(int i=0;i<n;i++) cin>>a[i];bool flg=0;//表示是否已经上升过bool ans=0;for(int i=1;i<n;i++){if(a[i]>a[i-1]) flg=1;if(flg&&a[i]<a[i-1]) {ans=1;break;}}if(ans) puts("No");else puts("Yes");}return 0;
}

E. Binary Inversions 思维+贪心

题意:给你一个只含0和1的数组,你有一次机会把一个数反转(0变为1,1变为0),让你求出各种操作后逆序对的最大值。
思路:因为数组比较特殊,只含0和1,那么逆序对数量就等于,每个1后面0的数量之和。这里可以贪心,如果要使逆序对最大,那么我们可以把第一个0改为1,或者把最后一个1改为0,最后计算原本的逆序对,三个取最大值即可。
写一个求解逆序对函数,倒着统计0的个数,如果遇到1,那么这个1的逆序对数就是当前0的数量,总逆序对,求个和就好。记得开long long。
代码:

#include<bits/stdc++.h>
using namespace std;
const int N =2e5+10;
typedef long long LL;
LL a[N],cnt[N];
int n;
LL Reverse_pair(){memset(cnt,0,sizeof cnt);//数组初始化LL res=0,num=0;for(int i=n;i>=1;i--){if(!a[i]) num++;else cnt[i]=num;}for(int i=1;i<=n;i++){res+=cnt[i];}return res;
}
int main(){cin.tie(0);cout.tie(0);ios::sync_with_stdio(false);int T;cin>>T;while(T--){cin>>n;bool flg=0;int f0=0,l1=0;//维护第一个0和最后一个1的下标for(int i=1;i<=n;i++) {cin>>a[i];if(!flg&&!a[i]) {f0=i;flg=1;}if(a[i]) l1=i;}LL b=Reverse_pair();a[f0]=1;//第一个0变为1LL c=Reverse_pair();a[f0]=0;//还原a[l1]=0; //最后一个1变为0LL d=Reverse_pair();cout<<max({b,c,d})<<endl;}return 0;
}

F. Quests 前缀和+二分

题意:给你n个任务,每个任务做完,会给你ai的奖励,任务做完后k天就不能再做这个任务,给你c和d,让你求出能够在d天内,奖励达到c的最大k值。
分析:因为我们需要尽快达到c,所以每次先做奖励最多的任务,所以需要排个序,二分答案,mid为一个周期,一个周期之后就可以在做奖励最多的任务。所以check函数就写当前的奖励是否大于等于c即可。
代码:

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10;
typedef long long LL;
LL a[N],sum[N];
LL n,c,d;
bool check(LL mid){LL res=sum[min(mid+1,n)]*(d/(mid+1))+sum[min(n,d%(mid+1))];return res>=c;
}
int main(){int T;cin>>T;while(T--){cin>>n>>c>>d;for(int i=1;i<=n;i++) cin>>a[i];sort(a+1,a+n+1,greater<int>());memset(sum,0,sizeof sum);for(int i=1;i<=n;i++) sum[i]=sum[i-1]+a[i];LL l=-1,r=d+1;while(l<r){LL mid=(l+r+1)>>1;if(check(mid)) l=mid;else r=mid-1;}if(l==-1) puts("Impossible");else if(l==d+1) puts("Infinity");else cout<<l<<endl;}
}

G. SlavicG’s Favorite Problem 图论+搜索+思维

题意:给你一棵带边权的树,给定起点a和终点b,刚开始的分数是0,每次经过一条边,分数就等于当前分数异或上该边的边权,要求你最后到大b时,分数要为0,你在图中有一次可以传送的机会,你可以传送到任意结点,求是否可以满足要求。
思路:根据异或的性质,两个相同的分数异或,结果为0,所以我们可以从起点搜索一遍,记录下经过每一条边当前的分数。在从终点相同方式搜索一遍,如果遇到了相同的分数,那么我们可以到达一个相同的节点,然后传送到另一个值相等的节点,再走到b即可满足条件,否则,无法满足条件。
代码:多组数据,记得做好中间变量初始化操作。

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10,M=2*N;
int h[N],e[M],ne[M],w[M],idx;
int n,a,b;
bool st[N];
bool flg;
map<int,int> mp;
void add(int a,int b,int c){e[idx]=b;w[idx]=c;ne[idx]=h[a];h[a]=idx++;
}
void init(){//变量初始化idx=0;flg=0;memset(h,-1,sizeof h);memset(e,0,sizeof e);memset(ne,0,sizeof ne);  memset(w,0,sizeof w);memset(st,0,sizeof st);mp.clear();
}
void dfs(int u,int cur){mp[cur]=1;st[u]=true;for(int i=h[u];~i;i=ne[i]){int j=e[i];if(st[j]) continue;if(j==b) continue;dfs(j,cur^w[i]);}
}
void dfs1(int u,int cur){st[u]=true;for(int i=h[u];~i;i=ne[i]){int j=e[i];if(st[j]) continue;dfs1(j,cur^w[i]);if(flg) return;if(mp[cur^w[i]]) flg=1;}
}
int main(){int T;cin>>T;while(T--){cin>>n>>a>>b;init();n--;while(n--){int a,b,c;cin>>a>>b>>c;add(a,b,c);add(b,a,c);}dfs(a,0);memset(st,0,sizeof st);dfs1(b,0);if(flg) puts("YES");else puts("NO");}
}

http://www.ppmy.cn/news/300050.html

相关文章

Codeforces Round #835 (Div. 4) A~F题解

原题地址&#xff1a;Codeforces Round #835 (Div. 4) 题目&#xff1a;A. Medium Number 题意&#xff1a; 没什么好说的&#xff0c;输出中间那个数即可 代码&#xff1a; #include<bits/stdc.h> #include<iostream> #include<algorithm> #include<…

【Codeforces Round #835 (Div. 4)】A——G题解

文章目录 A Medium Number题意思路代码 B Atillas Favorite Problem题意思路代码 C Advantage题意思路代码 D Challenging Valleys题意思路代码 E Binary Inversions题意思路代码 F Quests题意思路代码 G SlavicGs Favorite Problem题意思路代码 A Medium Number 题意 三个数…

微信 iPad 835协议

微信 iPad 协议是指用于在 iPad 设备上使用微信应用的技术协议。一般来说&#xff0c;通过该协议可以将微信账号同步到 iPad 设备上&#xff0c;并且可以在 iPad 上发送和接收微信消息&#xff0c;查看好友列表、聊天记录等功能。微信 iPad 协议是通过私有API实现的。 需要一定…

大厂设计师都在用的9个灵感工具

每一件伟大的设计作品都离不开设计师灵感的爆发。设计师有很多灵感来源&#xff0c;比如精美的摄影图片、酷炫的网站设计、APP的特色功能、友好的用户体验动画&#xff0c;或者一篇文章。 设计师每天都需要收集灵感&#xff0c;把灵感收集当成日常生活。在这篇文章中&#xff…

高通 Msm835平台充电功能的开发与调试

目录 平台充电相关代码&#xff1a; 835平台kernel充电相关代码&#xff1a; 关机充电的系统相关代码&#xff1a; 835平台UEFI 充电相关代码&#xff1a; 835平台电池曲线&#xff1a; 电池曲线大体内容如下: kernel 电池曲线的提交&#xff1a; XBL 关于充电曲线的提…

23年海南大学835上岸考研资料(历年真题)及笔记(耗时1年)

23年&#xff0c;海南大学835软件工程上岸必备资料&#xff08;历年真题&#xff09;及笔记&#xff08;耗时一年&#xff09;&#xff01; 首先挂一下22年考试qun图&#xff0c;qun里给大家每日分享考研英语和数学&#xff0c;专业课等&#xff0c;全程给大家解决考研路上的疑…

【P56】JMeter 响应时间图(Response Time Graph)

文章目录 一、响应时间图&#xff08;Response Time Graph&#xff09;参数说明二、准备工作三、测试计划设计 一、响应时间图&#xff08;Response Time Graph&#xff09;参数说明 可以以图形的方式查看和分析各事务和取样器的响应时间 使用场景&#xff1a;用于评估测试结…

【计算机网络复习之路】运输层(谢希仁第八版)万字详解 主打基础

运输层是OSI七层模型中最重要最关键的一层&#xff0c;是唯一负责总体数据传输和控制的一层。运输层要达到两个主要目的&#xff1a;第一&#xff0c;提供可靠的端到端的通信&#xff08;“端到端的通信” 是应用进程之间的通信&#xff09;&#xff1b;第二&#xff0c;向会话…

代码随想录算法训练营第四十九天|股票问题专题(1)

目录 LeeCode 121. 买卖股票的最佳时机 LeeCode 122.买卖股票的最佳时机II LeeCode 121. 买卖股票的最佳时机 121. 买卖股票的最佳时机 - 力扣&#xff08;LeetCode&#xff09; 动归五部曲&#xff1a; 1.确定dp数组及下标含义: dp[i][0] 表示第i天持有股票所得最多现金;…

详解Java异常和异常面试题(上)

1.异常的体系结构 2.从程序执行过程&#xff0c;看编译时异常和运行时异常 编译时异常&#xff1a;执行javac.exe命名时&#xff0c;可能出现的异常 运行时异常&#xff1a;执行java.exe命名时&#xff0c;出现的异常 1.运行时异常  是指编译器不要求强制处置的异常。一般是…

KL15上电

今天测试了一下单板的上电过程&#xff0c;发现了一个很神奇的现象&#xff1a;如果先是KL15掉电&#xff0c;然后KL30掉电&#xff0c;那么重新上KL30时单板没有任何反应&#xff1b;如果直接KL30掉电&#xff0c;那么重新上KL30时&#xff0c;会先有电流然后掉电。 研究后发…

联想笔记本K4350安装win7系统

【阅读文章申明】 作者只是想把自己实践中的经验分享给大家&#xff0c;如果文章里面有在大神面前显的很低级的知识点。那么大神你可以不看&#xff0c;请不要发一些“浪费流量”“辣鸡”之类嘲讽的话&#xff0c;每一篇文章都是作者自己。截图&#xff0c;编辑&#xff0c;排版…

Mellanox 5 RDMA网卡驱动安装

RDMA网卡驱动安装 1. RDMA驱动安装2. RDMA网卡实验与带宽测试 1. RDMA驱动安装 # 1. get OFED # https://cn.mellanox.com/products/infiniband-drivers/linux/mlnx_ofedtar -xvf xxx.tar.gzcd MLNX_OFED_LINUX-xxxx-x86_64sudo ./mlnxofedinstall --add-kernel-support# afte…

nuc977 添加EC20 4G 网卡

参考了手册和网上的文章。做下记录。 内核版本&#xff1a;linux-3.10 1. Add VID and PID 在/drivers/usb/serial/option.c添加: static const struct usb_device_id option_ids[] { #if 1 //Added by Quectel { USB_DEVICE(0x05C6, 0x9090) }, /* Quectel UC15 */ { USB…

i.MX6/i.MX7 EIM总线驱动-异步通信

i.MX6/i.MX7平台,支持EIM(External Interface Module)总线扩展。在实际项目中,大部分使用该总线和FPGA通信比较多,我们这里以与FPGA为例实现该驱动。 i.MX6是使用较多的一个,我们以i.MX6为例进行分析。我手上的芯片型号是i.MX6D。 我们实现的功能是:使用EIM的16根数据线…

实习笔试准备(3)

1 第三题 1.1 题目描述 给定一个迷宫&#xff0c;找到最快从起点到达重点的路径所需要的步数。 假设迷宫如下&#xff0c;假定左上角坐标为(0, 0)&#xff0c;右下角坐标为(3, 2) 1 0 -1 1 -2 0 -1 -3 2 2 0 0 -2是迷宫的起点&#xff0c;坐标为(0, 1) -3是迷宫的终点&a…

收音机调谐拉线维修

好久没更新博客了&#xff0c;因为实在是太忙啦~刚忙完搬家的事情&#xff0c;今天正好有空&#xff0c;就给大家来点干货。 事情是这样的&#xff0c;笔者手头有一个袖珍机械调谐收音机&#xff0c;型号为德生R1012&#xff0c;FM/MW/SW1-8/TV 12Bands收音机&#xff0c;虽然是…

一台老式收音机——飞乐牌251-1(交流电子管)

飞乐牌251-1收音机 (交流电子管) 它已经在我们家里无声无息地躺了二十多年了&#xff0c;记得我最后一次去拆它是高中毕业那年&#xff0c;之后再也没有去捣鼓过。前几年老妈嫌它占地方&#xff0c;扔前问我要不要收留这个劳什子&#xff0c;我如获至宝。但是我也只是让它换了个…

44、RDA5807收音机实验

文章目录 1、特点2、控制接口3、状态转换4、实验目的5、原理图6、代码实现1、特点 RDA5807 芯片研发而成的新一代数字调频收音机模块,主要应用于 MP3/MP4 媒体播放机,具有比传统模拟制式收音机模块更突出的性能表现,音质更清晰, 噪音极少,功耗更低,集成度高,对炬力、瑞芯…

乐歌升降桌怎么选,哪个型号比较好

随着时代的发展&#xff0c;人们坐在电脑桌前的时间越来越多&#xff0c;常常一天十几个小时一动不动&#xff0c;久而久之就必须要安排一台升降桌来辅助办公&#xff0c;不然颈椎、腰椎等身体部位真的受不了。 乐歌升降桌的型号其实不是很多&#xff0c;选购时尤其要注意的地…