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

news/2024/4/23 13:25:40/

在这里插入图片描述

文章目录

    • A Medium Number
      • 题意
      • 思路
      • 代码
    • B Atilla's Favorite Problem
      • 题意
      • 思路
      • 代码
    • C Advantage
      • 题意
      • 思路
      • 代码
    • D Challenging Valleys
      • 题意
      • 思路
      • 代码
    • E Binary Inversions
      • 题意
      • 思路
      • 代码
    • F Quests
      • 题意
      • 思路
      • 代码
    • G SlavicG's Favorite Problem
      • 题意
      • 思路
      • 代码

A Medium Number

题意

三个数,输出中位数。

思路

排序

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

代码

int n, m;
int a[N];void solve() {n = 3;for (int i = 0; i < 3; i++) cin >> a[i];sort(a, a + 3);cout << a[1] << endl;
}

B Atilla’s Favorite Problem

题意

找到最大字符,对应如下输出:‘a’ -> 1;‘b’ -> 2;…;‘z’ -> 26;

思路

维护最大值

input

5
1
a
4
down
10
codeforces
3
bcf
5
zzzzz

output

1
23
19
6
26

代码

int n, m;
int a[N];void solve() {int n; cin >> n;string s; cin >> s;int mx = -1;for (auto c: s) {mx = max(mx, (int)(c - 'a') + 1);}cout << mx << endl;
}

C Advantage

题意

输出每个数 - 除自己之外的最大值。

思路

维护最大和次大,排序。

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

代码

int n, m;
int a[N], b[N];void solve() {int n; cin >> n;int x = -1, mx = -1;rep (i, 1, n) cin >> a[i], b[i] = a[i], x = max(x, a[i]);sort(b + 1, b + 1 + n);mx = b[n - 1];rep (i, 1, n) if(a[i] == x) cout << x - mx << ' '; else cout << a[i] - x << ' '; cout << endl;
}

D Challenging Valleys

题意

问是否仅存在一个子数组,满足:

  • a l = a l + 1 = . . . = a r a_l=a_{l+1}=...=a_r al=al+1=...=ar
  • l = 0 l=0 l=0 或者 a l − 1 > a l a_{l-1}>a_l al1>al
  • r = n − 1 r=n-1 r=n1 或者 a r + 1 > a r a_{r+1}>a_r ar+1>ar

思路

如上条件,即一个 V 字型的尖尖,或者 _/ 的平段,或者 \_ 的平段。

统计这三种的个数,看是否最终为 1 即可。

便于统计,我们记数组 1 − n 1-n 1n,初始化 a [ 0 ] = a [ n + 1 ] = I N F a[0] = a[n + 1] = INF a[0]=a[n+1]=INF

双指针,左端点固定,去移动右端点,直到这一段相等结束(条件1),判断上述 V 字型条件(条件2,3)即可。

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

代码

int n, m;
int a[N];
void solve() {cin >> n;rep (i, 1, n) cin >> a[i];int cnt = 0;a[0] = a[n + 1] = mod;int l = 1;for (int i = 2; i <= n + 1; i++) {while (i <= n && a[i] == a[l]) i++;if (a[l] < a[l - 1] && a[i - 1] < a[i]) cnt++;l = i;}if (cnt == 1 || n == 1) cout << "YES" << endl;else cout << "NO" << endl;
}

E Binary Inversions

题意

给你01字符串,问至多一次,反转一个字符(0-1,1-0),使得逆序对最大,输出最大个数。

思路

三种情况:

  • 0次操作:

    • 直接统计逆序数即可,维护后缀0的数量,一次遍历,累加上位1的0的贡献。
  • 1次操作:

    • 从前往后第一个0改1
    • 从后往前第一个1改0

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

代码

有点烂,不想改了,思路够清晰。

int n, m;
int a[N];void solve() {cin >> n;int res = 0;int zero = 0, one = 0;for (int i = 1; i <= n; i++) cin >> a[i], zero += 1 - a[i], one += a[i];int xx = zero;for (int i = 1; i <= n; i++) if (a[i] == 1) res += xx; else xx -= 1;int idx1 = 1;while (idx1 <= n && a[idx1] == 1) idx1++;if(idx1 <= n && a[idx1] == 0) a[idx1] = 1, zero -= 1, one += 1;int t = zero, res1 = 0;for (int j = 1; j <= n; j++) if (a[j] == 1) res1 += t; else t -= 1;if(idx1 <= n && a[idx1] == 1) a[idx1] = 0, zero += 1, one -= 1;int res2 = 0, idx = n;while (idx >= 1 && a[idx] == 0) idx--;if (idx >= 1 && a[idx] == 1) one -= 1, zero += 1, a[idx] = 0;t = zero;for (int j = 1; j <= n; j++) if (a[j] == 1) res2 += t; else t -= 1;cout << max({res, res1, res2}) << endl;

F Quests

题意

给定 n , c , d n,c,d ncd,表示任务数组大小 n , d n,d nd 天要赚至少 c c c 元。每次工作了任务 i i i,那么接下来 k k k 天,这个任务不可再做。问 k k k 最大能是多少。

思路

最小的最大 :二分答案

贪心的从大到小排序,维护前缀和。贪心的做任务获利高的任务,但每隔 k k k 天才做下一次,所以一个周期做 k + 1 k+1 k+1 个任务( d d d 很大则考虑这种写法,否则直接暴力 d d d 天每次循环加上对应天下做的任务即可)。每次 c h e c k check check 去判断,当前每个任务重做时间隔 k k k 天,且在 d d d 天内,能否获利 c c c 元。

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

代码

  • c h e c k 1 check1 check1: 暴力加,循环节控制当天做的任务 i d id id
  • c h e c k check check d d d 如果很大,则按周期加。
int n, m, c, d;
int a[N], s[N];bool check1(int x) {int res = 0;int now = 1;for (int i = 1; i <= d; i++) {if (now <= n) {res += a[now];now++;} if (i % (x + 1) == 0) {now = 1;}}return res >= c;
}bool check(int x) {x += 1;int pre = 0;if (x > n) pre = s[n];else pre = s[x];int now = 0, res = 0;while (now + x <= d) {res += pre;now += x;if (res >= c) return true;}for (int i = 1; i <= d - now && i <= n; i++) res += a[i];return res >= c;
}void solve() {cin >> n >> c >> d;for (int i = 1; i <= n; i++) cin >> a[i];sort(a + 1, a + 1 + n, [=](int i, int j){ return i > j; });int z = 0; for (int i = 1; i <= min(n, d); i++) z += a[i];if (z >= c) { cout << "Infinity" << endl; return ; }if (d * a[1] < c) { cout << "Impossible" << endl; return ; }for (int i = 1; i <= n; i++) s[i] = s[i - 1] + a[i];int l = 0, r = 2e18;while (l < r) {int mid = (l + (r - l + 1) / 2);if (check(mid)) l = mid;else r = mid - 1;}cout << r << endl;
}

G SlavicG’s Favorite Problem

题意

n n n 个点, n − 1 n-1 n1条边,边权 w i w_i wi。(每走一边,需要异或当前边权)。给定 a , b a,b a,b,问从 a a a 出发,能否走往 b b b 点。条件是仅当走到 b b b 时,当前异或值为 0 0 0。并且,可以允许在路途中进行一次跳跃,即直接跳到任意除 b b b 外的一点。

注意的是,但凡走到了 b b b 就需要截止了(如果不为0,就走不到)。这意味着,从 a a a 开始走,要想去往 b b b 的子树下,仅能使用一次跳跃过去,而不能走过去。

思路

分别以 a , b a,b a,b 为根节点,计算所有点到根节点的一个前缀异或值,记 f a , f b fa,fb fa,fb 数组。(注意,这里 a a a 为根节点的话,不能去往 b b b 的子树)

f a fa fa 数组,将所有可达点( f a [ i ] ! = − 1 fa[i] != -1 fa[i]!=1,包括 a a a 本身【因为如果 f b [ a ] = 0 fb[a]=0 fb[a]=0 是直接可达的】,默认 f a [ a ] = 0 fa[a] = 0 fa[a]=0)统计进 m a p map map 中。

f b fb fb 数组,遍历所有点,判断如果当前点不是 b b b 本身,且 m a p map map 中存在 f b [ i ] fb[i] fb[i] ,那么说明至多一次跳跃,可以让跳跃前异或值等于跳跃后异或值,走完到 b b b 即异或为 0 0 0

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

代码

int h[N], w[M], e[M], ne[M], idx; 
void add(int a, int b, int c = 1) { e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++; 
} 
int n, a, b;
int fa[N], fb[N];
int root;
void dfs(int u, int f, int v) {if(root == a) fa[u] = v;else if(root == b) fb[u] = v;for (int i = h[u]; ~i; i = ne[i]) {int j = e[i];if (j == f) continue; if (root == a && j == b) continue; dfs(j, u, v ^ w[i]);}
}void solve() {memset(fa, -1, sizeof fa);memset(fb, -1, sizeof fb);memset(h, -1, sizeof h);cin >> n >> a >> b;for (int i = 0; i < n - 1;i ++) {int u, v, x; cin >> u >> v >> x;add(u, v, x), add(v, u, x);}root = a; fa[root] = 0;dfs(a, -1, 0);root = b; fb[root] = 0;dfs(b, -1, 0);map<int, int> mp;bool f = false;for (int i = 1; i <= n; i++) {if (i == b) continue; // 删掉也行吧,fa[b] == -1;else if(fa[i] != -1) mp[fa[i]] = 1;}for (int i = 1; i <= n; i++) {if (i == b) continue;else if (mp.count(fb[i])) f = true;}cout << (f ? "YES" : "NO") << endl;
}


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

相关文章

微信 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;选购时尤其要注意的地…

kafka集群报错找不到broker

一、问题描述 某次用户反馈&#xff0c;kafka消费这边消息失败&#xff0c;报错消费者被踢出消费组或broker状态异常无法连接&#xff0c;后实际验证端口确实不通 现场测试验证&#xff0c;报错&#xff1a;报错&#xff1a;Failed to find brokers to send ListGroups……fi…

Git GitLab 使用及规范

Git 基本操作 Git安装配置及基本使用 从官网下载安装包&#xff0c;手动完成安装。打开Git Bash命令行工具&#xff0c;执行命令ssh-keygen -t rsa -C Email-Addresss生成一个密钥对。登录到GitLab&#xff0c;点击右上角你的用户头像&#xff0c;点击Edit Profile settings&…