Codeforces Round 731 (Div 3)(A - F)
Codeforces Round 731 (Div. 3)(A - F)
Dashboard - Codeforces Round 731 (Div. 3) - Codeforces
A. Shortest Path with Obstacle(思维)
思路:显然要计算 A → B 之间的曼哈顿距离 , 要绕开 F 当且仅当 AB形成的直线平行于坐标轴且 F 在 AB之间 , 绕开贡献加2即可。
#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define IOS std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
#define int long long
const int N = 2e6 + 10;
const int mod = 1e9 + 7;
typedef pair<int,int>PII;int t;int x_1 , y_1 , x_2 , y_2 , x_3 , y_3 , res;signed main(){IOScin >> t;while(t --){res = 0;cin >> x_1 >> y_1;cin >> x_2 >> y_2;cin >> x_3 >> y_3;bool tag = 0;if(x_1 == x_2 && x_2 == x_3 && y_3 > min(y_1 , y_2) && y_3 < max(y_1 , y_2)) tag = 1;if(y_1 == y_2 && y_2 == y_3 && x_3 > min(x_1 , x_2) && x_3 < max(x_1 , x_2)) tag = 1;res += abs(x_1 - x_2) + abs(y_1 - y_2);if(tag) res += 2;cout << res << "\n";}return 0;
}
//freopen("文件名.in","r",stdin);
//freopen("文件名.out","w",stdout);
B. Alphabetical Strings(双指针)
思路:维护头尾两个指针 , 不断往中间找加入的字母 , 找不到跳出 , 判断指针是否相遇即可。
#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define IOS std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
#define int long long
const int N = 2e6 + 10;
const int mod = 1e9 + 7;
typedef pair<int,int>PII;int t , l , r , n;
string s;signed main(){IOScin >> t;while(t --){cin >> s;r = s.size();l = 1;n = r;s = '#' + s;while(l <= r){if(s[r] == (char)('a' - 1 + n)) r -= 1 , n -= 1;else if(s[l] == (char)('a' - 1 + n)) l += 1 , n -= 1;else break;}if(l > r) cout << "YES\n";else cout << "NO\n";}return 0;
}
//freopen("文件名.in","r",stdin);
//freopen("文件名.out","w",stdout);
C. Pair Programming(栈 + 贪心)
思路:需要保证在原数列中的相对位置不变 , 不难想出合并后的操作序列就是一个出栈序列 ,维护两个栈 , 贪心的选 , 有 0 选 0 , 没 0 去检查这两个数是否能处理即可。
#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define IOS std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
#define int long long
const int N = 2e6 + 10;
const int mod = 1e9 + 7;
typedef pair<int,int>PII;int n , k , x , y , t;
int a[N] , b[N] , ans[N]; signed main(){IOScin >> t;while(t --){cin >> k >> x >> y;stack<int>st1 , st2;for(int i = 1 ; i <= x; i ++) cin >> a[i];for(int i = x ; i >= 1 ; i --) st1.push(a[i]);for(int i = 1 ; i <= y; i ++) cin >> b[i];for(int i = y ; i >= 1 ; i --) st2.push(b[i]);for(int i = 1 ; i <= x + y ; i ++){if(st1.size() && st1.top() == 0){ans[i] = 0;st1.pop();k += 1;}else if(st2.size() && st2.top() == 0){ans[i] = 0;st2.pop();k += 1;}else{if(st1.size() && k >= st1.top()){ans[i] = st1.top(); st1.pop();}else if(st2.size() && k >= st2.top()){ans[i] = st2.top();st2.pop();}else break;}}if(st1.size() || st2.size()) cout << "-1\n";else{for(int i = 1 ; i <= x + y ; i ++) cout << ans[i] << " ";cout << '\n';}}return 0;
}
//freopen("文件名.in","r",stdin);
//freopen("文件名.out","w",stdout);
D. Co-growing Sequence(位运算)
思路:对于 b 数组 , 我们从前往后处理 , 贪心的让每一位最小就能保证字典序最小。那么怎么让每一位最小呢。对于题中所限制的条件(growing)
x a n d y = x x ~and~y = x x and y=x
即需要 x 为 1 的位 y 当前位 必须是 1
对于 b 数组 , 我们可以考虑 b 是通过异或操作为 a 数组补位来达到题目要求的条件。
b 数组的首位显然贪心的放 0 。 对于其后每一位 ,贪心的考虑当前的 b 最小即可 , 即当且仅当前一个数当前位为 1 , 后一个数当前位为 0 时,需要通过异或操作放 1 补位 , 计算贡献即可。
#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define IOS std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
#define int long long
const int N = 2e6 + 10;
const int mod = 1e9 + 7;
typedef pair<int,int>PII;int n , t , a[N] , b[N];signed main(){IOScin >> t;while(t --){cin >> n;for(int i = 1 ; i <= n ; i ++) cin >> a[i];b[1] = 0;for(int i = 2 ; i <= n ; i ++){a[i - 1] ^= b[i - 1];b[i] = 0;for(int j = 0 ; j <= 30 ; j ++){int x = (a[i - 1] >> j & 1);int y = (a[i] >> j & 1);if(x && !y) b[i] += (1 << j);}}for(int i = 1 ; i <= n ; i ++) cout << b[i] << " ";cout << "\n";}return 0;
}
//freopen("文件名.in","r",stdin);
//freopen("文件名.out","w",stdout);
E. Air Conditioners(思维)
思路:很好的一道思维题 , 对于每一个位置 , 我们分别考虑其前边的空调和其后边的空调对其的影响。以前边空调举例 , 由于一个点前面的空调对当前点的影响是 温度 + 距离 ,这个总和是不变的, 我们不妨把前面的空调都等价到一号坐标点 ,这样距离都固定了 , 我们只需要维护一个最小温度即可 。 对于后边空调的影响反向处理一遍即可。
#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define IOS std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
#define int long long
const int N = 2e6 + 10;
const int mod = 1e9 + 7;
typedef pair<int,int>PII;int t , n , k;
int ans[N] , pos[N] , val[N];signed main(){IOScin >> t;while(t --){cin >> n >> k;for(int i = 1 ; i <= n ; i ++){ans[i] = 9e18;val[i] = 0;}for(int i = 1 ; i <= k ; i ++) cin >> pos[i];for(int i = 1 ; i <= k ; i ++) cin >> val[pos[i]];int minn = 9e18;for(int i = 1 ; i <= n ; i ++){if(val[i]) minn = min(minn , val[i] - (i - 1));ans[i] = min(ans[i] , minn + (i - 1));}minn = 9e18;for(int i = n ; i >= 1 ; i --){if(val[i]) minn = min(minn , val[i] - (n - i));ans[i] = min(ans[i] , minn + (n - i));}for(int i = 1 ; i <= n ; i ++) cout << ans[i] << " ";cout << "\n";}return 0;
}
//freopen("文件名.in","r",stdin);
//freopen("文件名.out","w",stdout);
F. Array Stabilization (GCD version)(st表维护区间gcd)
思路:假如原数组是 a 数组 , 我们模拟一下这个过程
a1 | a2 | a3 | a4 |
---|---|---|---|
gcd(a1 , a2) | gcd(a2 , a3) | gcd(a3 , a4) | gcd(a4 , a1) |
gcd(a1 , a2 , a3) | gcd(a2 , a3 , a4) | gcd(a3 , a4 , a2) | gcd(a3 , a4 , a1) |
gcd(a1 , a2 , a3 , a4) | gcd(a2 , a3 , a4 , a1) | gcd(a3 , a4 , a2 , a1) | gcd(a3 , a4 , a1 , a2) |
不难发现最多 n - 1 次是一定能让所有的数字相等的 , 而且这个次数满足二分性 , 考虑二分 , 那么问题就转化成了如何处理区间gcd的问题 , 考虑st表处理即可 。 对于环 , 我们把数组变成二倍长度断环为链。复杂度
O ( n l o g n ) O(nlogn) O(nlogn)
#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define IOS std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
#define int long long
const int N = 2e6 + 10;
const int mod = 1e9 + 7;
typedef pair<int,int>PII;int t , n;int a[N] , st[N][21];int get(int x , int y){int l = x , r = x + y - 1 , len = y;int now = log2(len);return __gcd(st[l][now] , st[r - (1 << now) + 1][now]);
}bool judge(int x){for(int i = 1 ; i < n ; i ++) if(get(i , x + 1) != get(i + 1 , x + 1)) return 0;return 1;
}signed main(){IOScin >> t;while(t --){cin >> n;for(int i = 1 ; i <= n ; i ++) cin >> a[i];for(int i = n + 1 ; i <= 2 * n ; i ++) a[i] = a[i - n];for(int i = 1 ; i <= 2 * n ; i ++) st[i][0] = a[i];for(int j = 1 ; j <= 20 ; j ++){for(int i = 1 ; i + (1 << j) - 1 <= 2 * n ; i ++){st[i][j] = __gcd(st[i][j - 1] , st[i + (1 << (j - 1))][j - 1]);}}int l = 0 , r = n ;while(l < r){int mid = (l + r) >> 1;if(judge(mid)) r = mid;else l = mid + 1;}cout << l << "\n";}return 0;
}
//freopen("文件名.in","r",stdin);
//freopen("文件名.out","w",stdout);
相关文章:
Codeforces Round 731 (Div 3)(A - F)
Codeforces Round 731 (Div. 3)(A - F) Dashboard - Codeforces Round 731 (Div. 3) - Codeforces A. Shortest Path with Obstacle(思维) 思路:显然要计算 A → B 之间的曼哈顿距离 , 要绕开 F 当且仅当 AB形成的直线平行于坐…...
Python的sort()与sorted()函数详解
目录 sort()函数 sorted()函数 key参数 区别 sort()函数 sort()方法:该方法用于原地对列表进行排序,即直接在原始列表上进行排序操作,并不返回一个新的列表。 my_l…...

用python实现基本数据结构【04/4】
说明 如果需要用到这些知识却没有掌握,则会让人感到沮丧,也可能导致面试被拒。无论是花几天时间“突击”,还是利用零碎的时间持续学习,在数据结构上下点功夫都是值得的。那么Python 中有哪些数据结构呢?列表、字典、集…...
“必抓!”算法
一个程序员一生中可能会邂逅各种各样的算法,但总有那么几种,是作为一个程序员一定会遇见且大概率需要掌握的算法。今天就来聊聊这些十分重要的“必抓!”算法吧~ 你可以从以下几个方面进行创作(仅供参考) 一ÿ…...

【监控系统】Promethus整合Alertmanager监控告警邮件通知
【监控系统】Promethus整合Alertmanager监控告警邮件通知 Alertmanager是一种开源软件,用于管理和报警监视警报。它与Prometheus紧密集成,后者是一种流行的开源监视和警报系统。Alertmanager从多个源接收警报和通知,并根据一组配置规则来决定…...

【韩顺平】Linux基础
目录 1.网络连接三种方式 1.1 桥接模式:虚拟系统可以和外部系统通讯,但是容易造成IP冲突【1-225】 1.2 NAT模式:网络地址转换模式。虚拟系统可以和外部系统通讯,不造成IP冲突。 1.3 主机模式:独立的系统。 2.虚拟机…...

好奇一下各个大模型对华为mate60系列的看法
目前华为Mate60系列手机已上市并获抢购,个人觉得很不错,很好奇各个AI大模型对此事的看法,于是对chatGPT、文心一言、讯飞星火进行了一下粗浅的测试。 题目一(看看三个模型的综合分析能力) “目前华为Mate60系列手机已…...

UMA 2 - Unity Multipurpose Avatar☀️五.如何使用别人的Recipe和创建自己的服饰Recipe
文章目录 🟥 使用别人的Recipe1️⃣ 导入UMA资源效果展示2️⃣ 更新Library3️⃣ 试一下吧🟧 创建自己的服饰Recipe1️⃣ 创建自己的服饰Recipe2️⃣ 选择应用到的Base Recipe3️⃣ 指定显示名 / 佩戴位置 / 隐藏部位4️⃣ 给该服饰Recipe指定Slot / Overlay🚩 赋予Slot�…...
代码随想录训练营第五十六天| 583. 两个字符串的删除操作 、72. 编辑距离
583. 两个字符串的删除操作 题目链接/文章讲解/视频讲解:代码随想录 1.代码展示 //583.两个字符串的删除操作 int minDistance(string word1, string word2) {//step1 构建dp数组,dp[i][j]的含义是要使以i-1为结尾的word1和以j-1为结尾的word2//删除其元…...
hive解决了什么问题
hive出现的原因 Hive 出现的原因主要有以下几个: 传统数据仓库无法处理大规模数据:传统的数据仓库通常采用关系型数据库作为底层存储,这种数据库在处理大规模数据时效率较低。MapReduce 难以使用:MapReduce 是一种分布式计算框架…...

Lumion 和 Enscape 应该选择怎样的笔记本电脑?
Lumion 和 Enscape实时渲染对配置要求高,本地配置不够,如何快速解决: 本地普通电脑可一键申请高性能工作站,资产安全保障,供软件中心,各种软件插件一键获取,且即开即用,使用灵活&am…...

ICCV 2023 | MoCoDAD:一种基于人体骨架的运动条件扩散模型,实现高效视频异常检测
论文链接: https://arxiv.org/abs/2307.07205 视频异常检测(Video Anomaly Detection,VAD)扩展自经典的异常检测任务,由于异常情况样本非常少见,因此经典的异常检测通常被定义为一类分类问题(On…...

Mac电脑怎么使用NTFS磁盘管理器 NTFS磁盘详细使用教程
Mac是可以识别NTFS硬盘的,但是macOS系统虽然能够正确识别NTFS硬盘,但只支持读取,不支持写入。换句话说,Mac不支持对NTFS硬盘进行编辑、创建、删除等写入操作,比如将Mac里的文件拖入NTFS硬盘,在NTFS硬盘里新…...

Java设计模式-结构性设计模式(代理设计模式)
简介 为其他对象提供⼀种代理以控制对这个对象的访问,属于结构型模式。客户端并不直接调⽤实际的对象,⽽是通过调⽤代理,来间接的调⽤实际的对象应用场景 各⼤数码专营店,代理⼚商进⾏销售对应的产品,代理商持有真正的…...

线性空间、子空间、基、基坐标、过渡矩阵
线性空间的定义 满足加法和数乘封闭。也就是该空间的所有向量都满足乘一个常数后或者和其它向量相加后仍然在这个空间里。进一步可以理解为该空间中的所有向量满足加法和数乘的组合封闭。即若 V 是一个线性空间,则首先需满足: 注:线性空间里面…...

【MySQL】CRUD (增删改查) 基础
CRUD(增删改查)基础 一. CRUD二. 新增 (Create)1. 单行数据 全列插入2. 多行数据 指定列插入 三. 查询(Retrieve)1. 全列查询2. 指定列查询3. 查询字段为表达式4. 别名5. 去重:DISTINCT6. 排序…...
Socks5代理IP:保障跨境电商的网络安全
在数字化时代,跨境电商已成为全球商业的重要一环。然而,随着其发展壮大,网络安全问题也逐渐浮出水面。为了确保跨境电商的安全和隐私,Socks5代理IP技术成为了一项不可或缺的工具。本文将深入探讨Socks5代理IP在跨境电商中的应用&a…...

macOS通过钥匙串访问找回WiFi密码
如果您忘记了Mac电脑上的WiFi密码,可以通过钥匙串访问来找回它。具体步骤如下: 1.打开Mac电脑的“启动台”,然后在其他文件中找到“钥匙串访问”。 2.运行“钥匙串访问”应用程序,点击左侧的“系统”,然后在右侧找到…...

Debian11之稳定版本Jenkins安装
官方网址 系统要求 机器要求 256 MB 内存,建议大于 512 MB 10 GB 的硬盘空间(用于 Jenkins 和 Docker 镜像)软件要求 Java 8 ( JRE 或者 JDK 都可以) Docker (导航到网站顶部的Get Docker链接以访问适合您平台的Docker下载安装…...
kakfa 3.5 kafka服务端处理消费者客户端拉取数据请求源码
一、服务端接收消费者拉取数据的方法二、遍历请求中需要拉取数据的主题分区集合,分别执行查询数据操作,1、会选择合适的副本读取本地日志数据(2.4版本后支持主题分区多副本下的读写分离) 三、会判断当前请求是主题分区Follower发送的拉取数据请求还是消费…...
OkHttp 中实现断点续传 demo
在 OkHttp 中实现断点续传主要通过以下步骤完成,核心是利用 HTTP 协议的 Range 请求头指定下载范围: 实现原理 Range 请求头:向服务器请求文件的特定字节范围(如 Range: bytes1024-) 本地文件记录:保存已…...

九天毕昇深度学习平台 | 如何安装库?
pip install 库名 -i https://pypi.tuna.tsinghua.edu.cn/simple --user 举个例子: 报错 ModuleNotFoundError: No module named torch 那么我需要安装 torch pip install torch -i https://pypi.tuna.tsinghua.edu.cn/simple --user pip install 库名&#x…...
SpringAI实战:ChatModel智能对话全解
一、引言:Spring AI 与 Chat Model 的核心价值 🚀 在 Java 生态中集成大模型能力,Spring AI 提供了高效的解决方案 🤖。其中 Chat Model 作为核心交互组件,通过标准化接口简化了与大语言模型(LLM࿰…...

spring Security对RBAC及其ABAC的支持使用
RBAC (基于角色的访问控制) RBAC (Role-Based Access Control) 是 Spring Security 中最常用的权限模型,它将权限分配给角色,再将角色分配给用户。 RBAC 核心实现 1. 数据库设计 users roles permissions ------- ------…...
Pydantic + Function Calling的结合
1、Pydantic Pydantic 是一个 Python 库,用于数据验证和设置管理,通过 Python 类型注解强制执行数据类型。它广泛用于 API 开发(如 FastAPI)、配置管理和数据解析,核心功能包括: 数据验证:通过…...

图解JavaScript原型:原型链及其分析 | JavaScript图解
忽略该图的细节(如内存地址值没有用二进制) 以下是对该图进一步的理解和总结 1. JS 对象概念的辨析 对象是什么:保存在堆中一块区域,同时在栈中有一块区域保存其在堆中的地址(也就是我们通常说的该变量指向谁&…...

02.运算符
目录 什么是运算符 算术运算符 1.基本四则运算符 2.增量运算符 3.自增/自减运算符 关系运算符 逻辑运算符 &&:逻辑与 ||:逻辑或 !:逻辑非 短路求值 位运算符 按位与&: 按位或 | 按位取反~ …...

Qt的学习(一)
1.什么是Qt Qt特指用来进行桌面应用开发(电脑上写的程序)涉及到的一套技术Qt无法开发网页前端,也不能开发移动应用。 客户端开发的重要任务:编写和用户交互的界面。一般来说和用户交互的界面,有两种典型风格&…...
文件上传漏洞防御全攻略
要全面防范文件上传漏洞,需构建多层防御体系,结合技术验证、存储隔离与权限控制: 🔒 一、基础防护层 前端校验(仅辅助) 通过JavaScript限制文件后缀名(白名单)和大小,提…...
深度解析云存储:概念、架构与应用实践
在数据爆炸式增长的时代,传统本地存储因容量限制、管理复杂等问题,已难以满足企业和个人的需求。云存储凭借灵活扩展、便捷访问等特性,成为数据存储领域的主流解决方案。从个人照片备份到企业核心数据管理,云存储正重塑数据存储与…...