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

Codeforces Round 881 Div.3

文章目录

    • 贪心:A. Sasha and Array Coloring
    • 结论:B. Long Long
    • 性质:C. Sum in Binary Tree
    • dfs求叶子数量:D. Apple Tree
    • 二分与前缀和:E. Tracking Segments

贪心:A. Sasha and Array Coloring

Problem - A - Codeforces
image.png

将数组中的每个数染色,同一颜色的数字中,将最大值与最小值相减得到分数,问:所有的染色方案中,总分最高是多少
显然,同一颜色的数字除了最大和最小,其他的数没有用,要使总分最高,同一颜色的数字要最少,最少为两个
将数组的最大与最小相减得到分数,再将次大与次小相减…

#include <iostream>
#include <algorithm>
using namespace std;const int N = 55;
int a[N], T;int main()
{cin >> T;while ( T -- ){int n, sum = 0;cin >> n;for (int i = 0; i < n; ++ i ) cin >> a[i];sort(a, a + n);int l = 0, r = n - 1;while (l < r){sum += (a[r] - a[l]);l ++ , r -- ;}cout << sum << endl;}return 0;
}

结论:B. Long Long

image.png

sum一定是所有数绝对值之和
结论:最少操作次数等于连续负数子段个数,所有统计连续非负的子段数量即可

#include <iostream>
#include <cmath>
using namespace std;typedef long long LL;
const int N = 2e5 + 10;
int a[N], T;int main()
{cin >> T;while ( T -- ){LL n, sum = 0, cnt = 0;cin >> n;for (int i = 0; i < n; ++ i) {cin >> a[i];sum += abs(a[i]);}for (int i = 0; i < n;){if (a[i] < 0){cnt ++ ;while (i < n && a[i] <= 0) i ++ ;}else i ++ ;}cout << sum << ' ' << cnt << endl;}return 0;
}

debug:ans要开LL,wa了4发,非负子段中可以出现0,所以a[i] < 0是不行的


性质:C. Sum in Binary Tree

Problem - C - Codeforces
[外链图片转存中…(img-XlnHbBnn-1692359176162)]

一颗完全二叉树,根节点编号为1号,问根节点到n号节点的编号之和
手写堆时,学过:孩子的编号 / 2为父亲的编号,父亲的编号 * 2,或* 2 + 1能得到左右孩子的编号
若从1开始走到n,路径是无法一次确定的。从n走到1,路径能一次确定。所以将n不断/2,就能走到根节点,过程中维护sum即可

#include <iostream>
using namespace std;typedef long long LL;int main()
{int T;cin >> T;while ( T -- ){LL sum = 0, n;cin >> n;while (n){sum += n;n /= 2;}cout << sum << endl;}return 0;
}

dfs求叶子数量:D. Apple Tree

Problem - D - Codeforces
image.png

对于所有节点1~n,求以每个节点为根节点时,子树中叶子节点的数量leaf[i]
答案为leaf[x] * leaf[y]

用dfs求叶子节点的数量,有两个坑:树要建无向边,一开始我自以为是有向边,方向从根节点向下,但通过用例就能看出这是无向边
其次,无向树较难实现在线求叶子节点数量,一开始我写的是有向树,用dfs在线求叶子节点数量很好实现。但是无向树想要在线求,有一个问题,dfs会向根节点遍历,虽然能特判根节点不是叶子,但是dfs会遍历到不属于当前子树的叶子
解决方法是:用根节点开始dfs,用leaf数组保存每颗子树的叶子节点,从其他节点开始地离线求法依然是错的,只能从根节点开始求

#include <iostream>
#include <cstring>
using namespace std;typedef long long LL;
const int N = 2e5 + 10, M = 4e5 + 10;
int h[N], e[M], ne[M], idx;
int T, n, Q;
int leaf[N];void add(int x, int y)
{e[idx] = y, ne[idx] = h[x], h[x] = idx ++ ;
}int dfs(int x, int fa)
{bool flag = true;int cnt = 0;for (int i = h[x]; i != -1; i = ne[i]){int y = e[i];if (y != fa) flag = false, leaf[x] += dfs(y, x);}if (flag) leaf[x] = 1; return leaf[x];
}int main()
{cin >> T;while ( T -- ){memset(h, -1, sizeof h);memset(leaf, 0, sizeof leaf);idx = 0;cin >> n;int x, y;for (int i = 0; i < n - 1; ++ i ){cin >> x >> y;add(x, y), add(y, x);}cin >> Q;dfs(1, -1);while ( Q -- ){cin >> x >> y;cout << (LL)leaf[x] * leaf[y] << endl;}}return 0;
}

二分与前缀和:E. Tracking Segments

Problem - E - Codeforces
image.png

每次做二分题脑子都转不过来,要将边界问题考虑得很清楚
首先,分析题意:一个元素全为0的数组,给定m个区间与q个操作,每次操作将某个元素置为1,问第几次操作时,m个区间中至少有一个区间的1的数量大于0的数量
可以看出这题具有二段性,由于每次操作都是将0置为1,所以整个数组中1的数量随着操作次数增加。假设答案为ans,进行ans次操作后,有一个区间的1数量大于0数量。那么在之后的操作中,1的数量只增不减。所以对于第 [ a n s , m ] [ans, m] [ans,m]次操作,至少有1个区间的1数量大于0数量
而在进行第 [ 1 , a n s − 1 ] [1, ans-1] [1,ans1]次操作时,所有区间1的数量一定小于0的数量,操作次数呈现两段性

根据操作次数 [ 1 , q ] [1, q] [1,q]的两段性,我们可以二分出两段区间的分界点,即最终答案ans
每次check时,进行mid次操作,遍历所有区间,只要有区间的1数量大于0数量,check就返回true。说明mid落在了右半段区间,r = mid。若check为false,说明mid落在左半区间,l = mid + 1

什么情况下会无解?进行了q次操作后,依然没有一个区间的1数量大于0数量,此时无解。那么无解时,会二分到哪个答案?因为操作次数的范围为 [ 1 , q ] [1, q] [1,q],所以无解时操作次数为 q + 1 q + 1 q+1
因此二分的区间需要设置为 [ 1 , q + 1 ] [1, q + 1] [1,q+1],当最后的结果为 q + 1 q + 1 q+1时,无解

用前缀和求区间中1的数量

#include <iostream>
#include <cstring>
using namespace std;const int N = 1e5 + 10;
int n, m;
int a[N], T, Q, L[N], R[N], change[N];bool check(int mid)
{for (int i = 1; i <= m; ++ i) {int ones = a[R[i]] - a[L[i] - 1];if (2 * ones > R[i] - L[i] + 1) return true;}return false;
}int main()
{cin >> T;while ( T -- ){cin >> n >> m;for (int i = 1; i <= m; ++ i ) cin >> L[i] >> R[i];cin >> Q;for (int i = 1; i <= Q; ++ i ) cin >> change[i]; int l = 0, r = Q + 1;while (l < r){int mid = l + r >> 1;memset(a, 0, sizeof a);for (int i = 1; i <= mid; ++ i ) a[change[i]] = 1;for (int i = 1; i <= n; ++ i ) a[i] += a[i - 1];if (check(mid)) r = mid;else l = mid + 1;}if (r == Q + 1) puts("-1");else cout << r << endl;}return 0;
}

debug:check要建立所有的区间,所以for循环中,i <= m,我写成了i <= mid,WA两发
i <= mid应该是枚举操作时的条件


剩下两题有些难,20号之后回来补

相关文章:

Codeforces Round 881 Div.3

文章目录 贪心&#xff1a;A. Sasha and Array Coloring结论&#xff1a;B. Long Long性质&#xff1a;C. Sum in Binary Treedfs求叶子数量&#xff1a;D. Apple Tree二分与前缀和&#xff1a;E. Tracking Segments 贪心&#xff1a;A. Sasha and Array Coloring Problem - A…...

Kubernetes(K8s)从入门到精通系列之十六:linux服务器安装minikube的详细步骤

Kubernetes K8s从入门到精通系列之十六:linux服务器安装minikube的详细步骤 一、安装Docker二、创建启动minikube用户三、下载minikube四、安装minikube五、将minikube命令添加到环境变量六、启动minikube七、查看pods,自动安装kubectl八、重命名minikube kubectl --为kubect…...

JDBC配置文件抽取-spring11

改成context,到这里我们context命名空间就引入完毕&#xff0c;加载我们外部properties配置文件&#xff1a; 用它&#xff1a;第一个属性&#xff0c;第二个类型 在未加载路径下&#xff1a; 现在我已经把spring加载到配置文件里了。 现在我需要在这个位置引入proper…...

el-form组件相关的一些基础使用

el-checkbox 01.description 多选单选框 02.场景举例 需要对每一条数据展示她的某些状态是否存在 03.代码展示 <el-checkbox v-model"query.isAutoAccptncsign" true-label1 false-label0 :disabled"ifReview?true:false">自动发起承兑应答</…...

全新 – Amazon EC2 M1 Mac 实例

去年&#xff0c;在 re: Invent 2021 大会期间&#xff0c;我写了一篇博客文章&#xff0c;宣布推出 EC2 M1 Mac 实例的预览版。我知道你们当中许多人请求访问预览版&#xff0c;我们尽了最大努力&#xff0c;却无法让所有人满意。不过&#xff0c;大家现在已经无需等待了。我很…...

java # Servlet

一、什么是Servlet&#xff1f; Servlet是javaEE规范之一。规范就是接口。JavaWeb三大组件分别是&#xff1a;Servlet程序、Filter过滤器、Listener监听器。Servlet是运行在服务器上的一个Java小程序&#xff0c;它可以接收客户端发送来的请求&#xff0c;并响应数据给客户端。…...

Linux内核的两种安全策略:基于inode的安全与基于文件路径的安全

实现系统安全的策略 在Linux中&#xff0c;一切且为文件&#xff0c;实现系统安全的策略主要可分为两种&#xff1a;基于inode的安全、基于文件路径的安全。 基于inode的安全 为文件引入安全属性&#xff0c;安全属性不属于文件内容&#xff0c;它是文件的元数据&#xff0c…...

有哪些前端开发工具推荐? - 易智编译EaseEditing

在前端开发中&#xff0c;有许多工具可以帮助你更高效地进行开发、调试和优化。以下是一些常用的前端开发工具推荐&#xff1a; 代码编辑器/集成开发环境&#xff08;IDE&#xff09;&#xff1a; Visual Studio Code&#xff1a;功能强大、轻量级的代码编辑器&#xff0c;支…...

【JAVA】抽象类与接口

⭐ 作者&#xff1a;小胡_不糊涂 &#x1f331; 作者主页&#xff1a;小胡_不糊涂的个人主页 &#x1f4c0; 收录专栏&#xff1a;浅谈Java &#x1f496; 持续更文&#xff0c;关注博主少走弯路&#xff0c;谢谢大家支持 &#x1f496; 抽象类与接口 1. 抽象类1.1 抽象类的概念…...

人脸图像处理

1,人脸图像与特征基础 人脸图像的特点 规律性: 人的两只眼睛总是对称分布在人脸的上半部分,鼻子和嘴唇中心点的连线基本与两眼之间的连线垂直,嘴绝对不会超过眼镜的两端点(双眼为d,则双眼到嘴巴的垂直距离一般在0.8-1.25) 唯一性 非侵扰与便利性 可扩展性 人脸图像的应用 身份…...

Docker入门——实战图像分类

一、背景 思考&#xff1a; 在一个项目的部署阶段&#xff0c;往往需要部署到云服务器或者是终端设备上&#xff0c;而环境的搭建往往是最费时间和精力的&#xff0c;特别是需要保证运行环境一致性&#xff0c;有什么办法可以批量部署相同环境呢&#xff1f; Docker本质——…...

【HarmonyOS北向开发】-02 第一个程序测试

飞书原文档链接&#xff1a;Docs...

关于小程序收集用户手机号行为的规范

手机号在日常生活中被广泛使用&#xff0c;是重要的用户个人信息&#xff0c;小程序开发者应在用户明确同意的前提下&#xff0c;依法合规地处理用户的手机号信息。 而部分开发者在处理用户手机号过程中&#xff0c;存在不规范收集行为&#xff0c;影响了用户的正常使用体验&a…...

js判断手指的上滑,下滑,左滑,右滑,事件监听 和 判断鼠标滚轮向上滚动滑轮向下滚动

js判断手指的上滑&#xff0c;下滑&#xff0c;左滑&#xff0c;右滑&#xff0c;事件监听 和 判断鼠标滚轮向上滚动滑轮向下滚动 pc端 判断鼠标滚轮向上滚动滑轮向下滚动 const scrollFunc (e) > { e e || window.event; let wheelDelta e.wheelDelta ? e.wheelDelta…...

ES 一些简单 的查询注意事项

term query 不分词字段 带分数 where namexxx filter 分词字段 不分词字段 不带分数 Terms query 所有类型 带分数 where name in(xxx) Range query where name between xxx and xxx Exists Regexp Match query 分词字段/基础字段 Multi-match query 多个分词字段/基础字段 Boo…...

LeetCode //C - 57. Insert Interval

57. Insert Interval You are given an array of non-overlapping intervals intervals where intervals[i] [ s t a r t i , e n d i start_i, end_i starti​,endi​] represent the start and the end of the i t h i^{th} ith interval and intervals is sorted in asce…...

android手势事件

与手势事件有关的方法 dispatchTouchEvent()&#xff1a;该方法将触摸事件分发给相应的视图或视图组。onInterceptTouchEvent()&#xff1a;该方法用于判断是否需要拦截触摸事件&#xff0c;如果需要拦截&#xff0c;则返回 true&#xff0c;否则返回 false。onTouchEvent()&a…...

[网络安全学习篇01]:windowsxp、windows2003、windows7、windows2008系统部署(千峰网络安全视频笔记)

VM 虚拟机&#xff1a;VMware Workstation 15.5 PRO&#xff08;建议升至最高版本&#xff09; 部署windows-xp系统 一、配置虚拟机硬件并安装系统 1、在VMware文件目录下创建一个空文件夹将其命名位&#xff1a;winxp-1 2、打开VMware软件&#xff0c;点击创建新的虚拟机。…...

CANoe自动化工程的搭建

基于XMLCAPL建立自动化工程 1、导入ini文件2、新建 Test Environment3、报告类型4、代码编写 1、导入ini文件 工程的配置的文件&#xff0c;配置DUT相关信息&#xff0c;具体视工程而编写内容。 2、新建 Test Environment 1、新建XML测试用例环境 2、导入XML测试用例文件 …...

第6章:支持向量机

间隔与支持向量 w为法向量&#xff0c;决定的是超平面的方向。b是偏移项&#xff0c;决定了超平面与原点之间的距离。 为什么最大化间隔&#xff0c;得到的就是最优平面呢&#xff1f; 当超平面没有正确划分正负样本时&#xff0c;几何间隔为负数。几何间隔&#xff0c;各个…...

无法与IP建立连接,未能下载VSCode服务器

如题&#xff0c;在远程连接服务器的时候突然遇到了这个提示。 查阅了一圈&#xff0c;发现是VSCode版本自动更新惹的祸&#xff01;&#xff01;&#xff01; 在VSCode的帮助->关于这里发现前几天VSCode自动更新了&#xff0c;我的版本号变成了1.100.3 才导致了远程连接出…...

拉力测试cuda pytorch 把 4070显卡拉满

import torch import timedef stress_test_gpu(matrix_size16384, duration300):"""对GPU进行压力测试&#xff0c;通过持续的矩阵乘法来最大化GPU利用率参数:matrix_size: 矩阵维度大小&#xff0c;增大可提高计算复杂度duration: 测试持续时间&#xff08;秒&…...

3403. 从盒子中找出字典序最大的字符串 I

3403. 从盒子中找出字典序最大的字符串 I 题目链接&#xff1a;3403. 从盒子中找出字典序最大的字符串 I 代码如下&#xff1a; class Solution { public:string answerString(string word, int numFriends) {if (numFriends 1) {return word;}string res;for (int i 0;i &…...

CMake控制VS2022项目文件分组

我们可以通过 CMake 控制源文件的组织结构,使它们在 VS 解决方案资源管理器中以“组”(Filter)的形式进行分类展示。 🎯 目标 通过 CMake 脚本将 .cpp、.h 等源文件分组显示在 Visual Studio 2022 的解决方案资源管理器中。 ✅ 支持的方法汇总(共4种) 方法描述是否推荐…...

docker 部署发现spring.profiles.active 问题

报错&#xff1a; org.springframework.boot.context.config.InvalidConfigDataPropertyException: Property spring.profiles.active imported from location class path resource [application-test.yml] is invalid in a profile specific resource [origin: class path re…...

蓝桥杯 冶炼金属

原题目链接 &#x1f527; 冶炼金属转换率推测题解 &#x1f4dc; 原题描述 小蓝有一个神奇的炉子用于将普通金属 O O O 冶炼成为一种特殊金属 X X X。这个炉子有一个属性叫转换率 V V V&#xff0c;是一个正整数&#xff0c;表示每 V V V 个普通金属 O O O 可以冶炼出 …...

排序算法总结(C++)

目录 一、稳定性二、排序算法选择、冒泡、插入排序归并排序随机快速排序堆排序基数排序计数排序 三、总结 一、稳定性 排序算法的稳定性是指&#xff1a;同样大小的样本 **&#xff08;同样大小的数据&#xff09;**在排序之后不会改变原始的相对次序。 稳定性对基础类型对象…...

TSN交换机正在重构工业网络,PROFINET和EtherCAT会被取代吗?

在工业自动化持续演进的今天&#xff0c;通信网络的角色正变得愈发关键。 2025年6月6日&#xff0c;为期三天的华南国际工业博览会在深圳国际会展中心&#xff08;宝安&#xff09;圆满落幕。作为国内工业通信领域的技术型企业&#xff0c;光路科技&#xff08;Fiberroad&…...

通过 Ansible 在 Windows 2022 上安装 IIS Web 服务器

拓扑结构 这是一个用于通过 Ansible 部署 IIS Web 服务器的实验室拓扑。 前提条件&#xff1a; 在被管理的节点上安装WinRm 准备一张自签名的证书 开放防火墙入站tcp 5985 5986端口 准备自签名证书 PS C:\Users\azureuser> $cert New-SelfSignedCertificate -DnsName &…...

ubuntu系统文件误删(/lib/x86_64-linux-gnu/libc.so.6)修复方案 [成功解决]

报错信息&#xff1a;libc.so.6: cannot open shared object file: No such file or directory&#xff1a; #ls, ln, sudo...命令都不能用 error while loading shared libraries: libc.so.6: cannot open shared object file: No such file or directory重启后报错信息&…...