Codeforces Round #835 (Div. 4) 题解 A-G

news/2024/4/23 11:45:21/

A 题目链接:https://codeforces.com/contest/1760/problem/A

 

input:

9
5 2 6
14 3 4
20 2 1
1 2 3
11 19 12
10 8 20
6 20 3
4 1 3
19 8 4

output:

5
4
2
2
12
10
6
3
8

题意:

给三个数,输出中间值。

思路:

sort 取第二个即可。

代码如下:

#include<bits/stdc++.h>
#define endl "\n"
using namespace std;
typedef long long ll;
const int mod=1e9+7;
const int N=2e5+10;int t,n;
int a[10];
int main()
{ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);cin>>t;while(t--){cin>>a[1]>>a[2]>>a[3];sort(a+1,a+4);cout<<a[2]<<endl;}return 0;
}

B 题目链接:https://codeforces.com/contest/1760/problem/B

input:

5
1
a
4
down
10
codeforces
3
bcf
5
zzzzz

output:

1
23
19
6
26

题意:

给一个小写字母字符串,输出其中最大的字母的数值( A ~ Z 对应 1 ~ 26 )。

思路:

开一个maxn变量,遍历字符串找最大值即可。

代码如下:

#include<bits/stdc++.h>
#define endl "\n"
using namespace std;
typedef long long ll;
const int mod=1e9+7;
const int N=2e5+10;int t,n;
int main()
{ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);cin>>t;while(t--){cin>>n;string s;cin>>s;int ans=0;for(int i=0;i<n;i++){ans=max(ans,s[i]-96);}cout<<ans<<endl;}return 0;
}

C 题目链接:https://codeforces.com/contest/1760/problem/C

input:

5
4
4 7 3 5
2
1 2
5
1 2 3 4 5
3
4 9 4
4
4 4 4 4

output:

-3 2 -4 -2 
-1 1 
-4 -3 -2 -1 1 
-5 5 -5 
0 0 0 0 

题意:

给一个长度为 n 的数组 a ,对于每一个数,输出其与最大值的差,对于最大值本身,输出其与第二大值的差。

思路:

遍历一次找最大值,再遍历找与其的差值,最小的差值即为最大值本身要输出的数。最后遍历输出即可。

代码如下:

#include<bits/stdc++.h>
#define endl "\n"
using namespace std;
typedef long long ll;
const int mod=1e9+7;
const int N=2e5+10;int t,n;
int a[N];
int main()
{ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);cin>>t;while(t--){cin>>n;int maxn=0;int k=0;for(int i=1;i<=n;i++){cin>>a[i];if(a[i]>maxn){maxn=a[i];k=i;}}int minn=0x3f3f3f3f;for(int i=1;i<=n;i++){if(i==k)continue;else{minn=min(minn,a[k]-a[i]);}}for(int i=1;i<=n;i++){if(i==k){cout<<minn<<" ";}else{cout<<a[i]-a[k]<<" ";}}cout<<endl;}return 0;
}

D 题目链接:https://codeforces.com/contest/1760/problem/D

input:

6
7
3 2 2 1 2 2 3
11
1 1 1 2 3 3 4 5 6 6 6
7
1 2 3 4 3 2 1
7
9 7 4 6 9 9 10
1
1000000000
8
9 4 4 5 9 4 9 10

output:

YES
YES
NO
YES
YES
NO

题意:

给 n 个数的数组 a ,如果存在图中 “ 凹陷 ” 现象,输出 NO,否则输出 YES 。

思路:

如果记录到相邻两数存在上升现象时,每次记录较大值,此后如果记录到有数小于记录值,输出NO,遍历结束后若合法,输出YES

代码如下:

#include<bits/stdc++.h>
#define endl "\n"
using namespace std;
typedef long long ll;
const int mod=1e9+7;
const int N=2e5+10;int t,n;
int a[N];
int main()
{ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);cin>>t;while(t--){cin>>n;for(int i=1;i<=n;i++){cin>>a[i];}bool f=0,flag=1;int k=0;for(int i=1;i<n;i++){if(a[i]<a[i+1]){f=1;k=a[i+1];continue;}if(f==1){if(a[i+1]<k){flag=0;break;}}}if(flag)cout<<"YES"<<endl;elsecout<<"NO"<<endl;}return 0;
}

E 题目链接:https://codeforces.com/contest/1760/problem/E

input:

5
4
1 0 1 0
6
0 1 0 0 1 0
2
0 0
8
1 0 1 1 0 0 0 1
3
1 1 1

output:

3
7
1
13
2

题意:

给一个由 n 个 0,1组成的数组 a ,该数组的 inversions 指 下标大小关系与自身大小关系相反的元素对的数量。问最多可以操作一次,使某一位元素自相反。问修改(或不修改)得到的最大值是多少

思路:

贪心,只存在三种情况

1.不修改

2.修改从左往右第一个0

3.修改从右往左第一个1

三种情况比较最大值即可

inversions计算方式也很简单,就是每一个0前面所有1的总和

代码如下:

#include<bits/stdc++.h>
#define endl "\n"
using namespace std;
typedef long long ll;
const int mod=1e9+7;
const int N=2e5+10;ll t,n;
int a[N];
int main()
{ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);cin>>t;while(t--){cin>>n;ll cnt1=0,cnt0=0;bool f=0;ll pos1=n+1,pos0=0;ll ans=0;for(int i=1;i<=n;i++){cin>>a[i];if(a[i]==1){cnt1++;pos1=i;}else{cnt0++;if(f==0){f=1;pos0=i;}ans+=cnt1;}}ans=max(ans,ans+max(cnt0-1-pos0+1,cnt1-1-n+pos1));cout<<ans<<endl;}return 0;
}

F 题目链接:https://codeforces.com/contest/1760/problem/F

input:

6
2 5 4
1 2
2 20 10
100 10
3 100 3
7 2 6
4 20 3
4 5 6 7
4 100000000000 2022
8217734 927368 26389746 627896974
2 20 4
5 1

output:

2
Infinity
Impossible
1
12
0

题意:

有 n 种工作,每种工作做完可以获得 ai 元,每天只能完成一种工作。每做完一种工作, k 天内不能再做,给定 c 和 d ,意为在 d 天内获得 c 元,问能够接受最大的 k 约束是多少,输出 k 的值。如果不能约束,输出 “ Impossible ”  如果任意约束都能完成目标 ,输出 “ Infinity ”

思路:

贪心处理。先按价值从大到小排序,在限制条件下,我们一定是优先选最大的,限制解除后继续选最大的

首先看一下两种特殊情况处理

1. 如果说在不加限制的条件下,也就是每次选择价值最大的工作,完成 d 天,依然无法达成目标,那么可以输出 Impossible

2.如果说限制无限大,也就是说每种工作只能做一次,且总时间不超过 d 天的情况下,依然可以达成目标,那么可以输出 Infinity

3.正常情况下,直接二分答案k即可。对于一个限制 k ,我们的工作模式是 k + 1天的循环,取模每次做价值最大的工作即可(也有可能不工作),然后check判断当前 k 能不能达成目标

注意对价值序列进行前缀和化出力,能降一维复杂度

代码如下:

#include<bits/stdc++.h>
#define endl "\n"
using namespace std;
typedef long long ll;
const int mod=1e9+7;
const int N=2e5+10;ll t,n,c,d;
ll a[N],s[N];
inline bool cmp(ll a,ll b)
{return a>b;
}inline bool check(ll k)
{k++;ll time=d/k;ll m=d%k;if(time*s[min(k,n)]+s[min(m,n)]<c)return false;elsereturn true; 
}int main()
{ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);cin>>t;while(t--){cin>>n>>c>>d;for(int i=1;i<=n;i++){cin>>a[i];}sort(a+1,a+n+1,cmp);for(int i=1;i<=n;i++){s[i]=s[i-1]+a[i];}if(a[1]*d<c){cout<<"Impossible"<<endl;continue;}if(s[min(d,n)]>=c){cout<<"Infinity"<<endl;continue;}ll l=0,r=d,mid=0;while(l<r){mid=(l+r+1)>>1;if(check(mid)){l=mid;}else{r=mid-1;}}cout<<l<<endl;}return 0;
}

G 题目链接:https://codeforces.com/contest/1760/problem/G

input:

3
5 1 4
1 3 1
2 3 2
4 3 3
3 5 1
2 1 2
1 2 2
6 2 3
1 2 1
2 3 1
3 4 1
4 5 3
5 6 5

output:

YES
NO
YES

题意:

有一个 n 个点的树,每条边都有权值 w ,现在给定起点 a ,终点 b ,一开始 x = 0 ,每次由一个点到另一个点时 ,x与这条边的权值异或 ,问能否在到达 b 的时候 ,x = 0(有一次机会,可以从任意点跳到除点 b 外的任意点,不经过异或)

思路:

从点 a 开始 dfs ,每次进行异或,将当前异或值存入 set。

然后从点 b 开始 dfs ,每次进行异或,如果当前值能在 set 中 找到,那么输出YES

否则输出NO

代码如下:

#include<bits/stdc++.h>
#define endl "\n"
using namespace std;
typedef long long ll;
const int mod=1e9+7;
const int N=2e5+10;struct node{ll f,w;
};
int t,n=0,a,b;
bool flag;vector<node> vec[N];
set<ll> st;void dfs_a(int from,int to,ll sum)
{if(to==b){return;}st.insert(sum);for(auto &x:vec[to]){if(x.f==from)continue;dfs_a(to,x.f,sum^x.w);}
}void dfs_b(int from,int to,ll sum)
{if(flag){return;}if(st.count(sum)&&to!=b){flag=1;return;}for(auto &x:vec[to]){if(x.f==from)continue;dfs_b(to,x.f,sum^x.w);}
}int main()
{ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);cin>>t;while(t--){st.clear();for(int i=1;i<=n;i++){vec[i].clear();}cin>>n>>a>>b;int u,v;ll w;for(int i=1;i<n;i++){cin>>u>>v>>w;vec[u].push_back({v,w});vec[v].push_back({u,w});}flag=0;dfs_a(0,a,0);dfs_b(0,b,0);if(flag)cout<<"YES"<<endl;elsecout<<"NO"<<endl;	}return 0;
}


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

相关文章

F. Quests Codeforces Round #835 (Div. 4)(二分答案)

传送门 题意&#xff1a; 有n个任务。如果你在这天完成第i个任务&#xff0c;你将获得ai币。每天只能完成一个任务。并且做完这个任务后k天内都不能再做这个任务(例如&#xff0c;如果k3&#xff0c;你做了任务1&#xff0c;那么后三题都不能做此任务&#xff0c;只能在第五天…

Codeforces Round #835 (Div. 4) C. Advantage

Codeforces Round #835 (Div. 4) C. Advantage Make a copy of the array s s s: call it t t t. Sort t t t in non-decreasing order, so that t 1 t_1 t1​ is the maximum strength and t 2 t_2 t2​ — the second maximum strength. Then for everyone but the be…

个人练习-Leetcode-835. Image Overlap

题目链接&#xff1a;https://leetcode.cn/problems/image-overlap/ 题目大意&#xff1a;给出两个位图矩阵img1[][]和img2[][]&#xff0c;其中元素只有0和1。一次平移是指将一个图像里【所有的1】都向左/右/上/下移动一格。求经过若干次平移后&#xff0c;两个图像能重叠的1…

24考研835软件工程经验贴

大家好&#xff0c;今天给大家介绍一下我在考研这一年之中有关于835软件工程的一些经验和误区。 1.经验之谈 首先&#xff0c;我是一个二战的考生&#xff0c;一战给我带来的经验有几点。第一&#xff0c;数学、专业课这两门越早复习越好&#xff0c;越拖到后面你就会发现来不及…

835:排列

总时间限制: 5000ms 内存限制: 65536kB 描述 题目描述&#xff1a;大家知道&#xff0c;给出正整数n&#xff0c;则1到n这n个数可以构成n&#xff01;种排列&#xff0c;把这些排列按照从小到大的顺序&#xff08;字典顺序&#xff09;列出&#xff0c;如n3时&#xff0c…

海南大学电子信息(085400)原软件工程835

欢迎学弟学妹报考海南大学 你是不是没有资料&#xff1f; 海南大学软件工程835&#xff08;网安和计科&#xff09;&#xff0c;由多名软工学长学姐共同编写&#xff0c;专业课知识框架清晰&#xff0c;包含16-22各年份真题&#xff08;内含答案&#xff09;、总结知识点、专…

Codeforces Round #835 (Div. 4)A~D

Codeforces Round #835 (Div. 4&#xff09; A. Medium Number 感受&#xff1a;太简单了&#xff01;&#xff01;&#xff01;简单简单简单&#xff01; 题意&#xff1a;三个数找中间数 我的思路&#xff1a;sort() 题解&#xff1a;这没啥思路感觉 #include <iost…

Codeforces Round #835 (Div. 4) A~G

原题链接&#xff1a;Codeforces Round #835 (Div. 4) 目录 A. Medium Number B. Atillas Favorite Problem C. Advantage D. Challenging Valleys E. Binary Inversions F. Quests G. SlavicGs Favorite Problem A. Medium Number 题意&#xff1a;输出三个数的中间…

ipad协议835最新版

微信作为中国最流行的社交媒体应用之一&#xff0c;其协议安全性一直备受关注。逆向微信协议可以帮助我们更好地理解微信的工作原理&#xff0c;进而开发出更好的第三方应用或者提高自己的安全意识。本文将介绍微信逆向协议开发的基本流程和注意事项。 ## 什么是微信逆向协议&a…

Codeforces Round #835 (Div. 4)

文章目录 一、A - Medium Number二、B - Atillas Favorite Problem三、C - Advantage四、D - Challenging Valleys五、E - Binary Inversions六、F - Quests七、G - SlavicGs Favorite Problem 一、A - Medium Number 代码: #include <bits/stdc.h> #define ios ios::s…

Codeforces Round #835 (Div. 4) G. SlavicG‘s Favorite Problem

翻译&#xff1a; 给您一个带有&#x1d45b;顶点的加权树。回想一下&#xff0c;树是一个没有任何循环的连通图。加权树是每条边都有一定权重的树。树是无向的&#xff0c;它没有根。 因为树木让你厌烦&#xff0c;所以你决定挑战自己&#xff0c;在给定的树上玩一款游戏。 …

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

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

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;向会话…