Codeforces Round 910 (Div. 2)（D~F）

1898D - Absolute Beauty 

        题意：给定长度为n的数组a和b，定义b数组的价值为\sum _{i = 1}^{n}|a_{i} - b_{i}|，现可以交换一次b数组中的任意两个元素，求b数组的价值最大值。

        思路：绝对值问题可以放在数轴上去解决。绝对值即为区间长度

观察上述三种情况，发现当且仅当第二种情况，即原本两段区间不重合的条件下，其b数组的价值才会增加，增加的值为他们两段区间相隔的距离乘2。手画一下后发现交换a、b不会对结果造成任何影响，因此本题转换为给定若干区间，求区间间隔最大。只需要记录一下一个区间的最小右端点和区间的最大左端点，然后他们之间的差就是最大区间间隔。

        

// Problem: D. Absolute Beauty
// Contest: Codeforces - Codeforces Round 910 (Div. 2)
// URL: https://codeforces.com/contest/1898/problem/D
// Memory Limit: 256 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
using namespace std;
#define LL long long
#define pb push_back
#define x first
#define y second 
#define endl '\n'
const LL maxn = 4e05+7;
const LL N=2e05+10;
const LL mod=1e09+7;
typedef pair<int,int>pl;
priority_queue<LL , vector<LL>, greater<LL> >t;
priority_queue<LL> q;
LL gcd(LL a, LL b){
	return b > 0 ? gcd(b , a % b) : a;
}

LL lcm(LL a , LL b){
	return a / gcd(a , b) * b;
}
int n , m;
int a[N] , b[N];
void init(int n){
	for(int i = 0 ; i <= n ; i ++){
		a[i] = 0;
	}
}
void solve() 
{
	cin >> n;
	pair<int,int>p[n + 1];
	for(int i = 1 ; i <= n ; i ++){
		cin >> a[i];
	}
	for(int i = 1 ; i <= n ; i ++){
		cin >> b[i];
	}
	LL ans = 0;
	int r_min = 1e9 , l_max = 0;
	for(int i = 1 ; i <= n ; i ++){
		if(a[i] > b[i])
			swap(a[i] , b[i]);
		r_min = min(r_min , b[i]);
		l_max = max(l_max , a[i]);
		ans += abs(b[i] - a[i]);
	}
	if(r_min < l_max){
		ans += 2 * (l_max - r_min);
	}
	cout << ans<<endl;
}            
int main() 
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cout.precision(10);
    int t=1;
	cin>>t;
    while(t--)
    {
    	solve();
    }
    return 0;
}

1898E - Sofia and Strings 

        题意：给定两个字符串S和T，现可以对S进行操作：

1、删除S中某个字母。

2、选中S中[L,R]范围内字符，使其按照字典序大小重新升序排列。

        要求若干次操作后S是否能等于T。

        思路：首先通过预处理将每个字符在S中的位置全部都找出来。对于操作2而言，我们可以每次固定范围为2，那么操作2就转化成了交换相邻字符（若前者字典序大于后者）。接下来我们从前往后逐个匹配T中的字符，对于T当中的每个字符，我们尽可能的去用操作2来实现匹配，因为操作2不会删除字母，这样会为之后的字符匹配提供帮助。对于字符T_{i}而言，假如说找到了S中S_{j} = T_{i} , 那么S中第 j 位以前的，比T_{i}小的字符在之后都是无法被找到的。因此T_{i}所在的位置必须在T_{i}之前，比它字典序大的字符的位置之后。因此每一轮需要记录一下当前字符在S中的最后匹配的位置。

        

// Problem: E. Sofia and Strings
// Contest: Codeforces - Codeforces Round 910 (Div. 2)
// URL: https://codeforces.com/contest/1898/problem/E
// Memory Limit: 256 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
using namespace std;
#define LL long long
#define pb push_back
#define x first
#define y second 
#define endl '\n'
const LL maxn = 4e05+7;
const LL N=1e05+10;
const LL mod=1e09+7;
typedef pair<int,int>pl;
priority_queue<LL , vector<LL>, greater<LL> >t;
priority_queue<LL> q;
LL gcd(LL a, LL b){
	return b > 0 ? gcd(b , a % b) : a;
}

LL lcm(LL a , LL b){
	return a / gcd(a , b) * b;
}
int n , m;
int a[N];
void init(int n){
	for(int i = 0 ; i <= n ; i ++){
		a[i] = 0;
	}
}
void solve() 
{
	cin >> n >> m;
	string s , t;
	cin >> s >> t;
	vector<int>pos[26];
	for(int i = 0 ; i < n ; i ++){
		pos[s[i] - 'a'].pb(i);
	}
	vector<int>max_id(26 , -1);
	for(int i = 0 ; i < m ; i ++){
		int op = t[i] - 'a';
		int maxx = -1;
		for(int i = op ; i < 26 ; i ++){
			maxx = max(maxx , max_id[i]);
		}
		auto it = upper_bound(pos[op].begin() , pos[op].end() , maxx);
		if(it == pos[op].end()){
			cout <<"NO\n";
			return;
		}
		max_id[op] = *it;
	}
	cout <<"YES\n";
}            
int main() 
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cout.precision(10);
    int t=1;
	cin>>t;
    while(t--)
    {
    	solve();
    }
    return 0;
}

1898F - Vova Escapes the Matrix 

        题意：迷宫问题，给定一个迷宫和一个起点，迷宫分为空格子和有遮挡物的格子。若从起点顺着空格子走到边缘则能够走出，接下来迷宫分为三种类型：

1、无法被走出。

2、只有一个出口能走出。

3、有两个及以上出口能走出。

接下来可以选择堵住迷宫的一些格子，但是要求堵住以后的迷宫不改变其类型，求最多能堵住多少格子。

        思路：对于类型1，将迷宫中所有空格子全部堵住即可。对于类型2而言，将迷宫起点到出口最短路留下，其余全部堵住即可。最短路可以跑一边BFS求得。而对于类型3，需要保留两个出口，其余的全部都填满。即两个出口到起点的最短路保留，其余全部填满，但是需要注意的是可能两个出口到起点的最短路有重复点，需要特别处理。

对于起点到任意一点的最短路我们可以直接一遍BFS求得，但是如何求起点到两个出口的最短路，我们可以通过逆向思维，从每个终点出发开始BFS，然后任意一个空格子可以被走过最多两次，这样能保证有两个终点走到该点上。因为是BFS，所以最先走到某个格子的两个终点必然是最短的，然后再记录一下终点到该格子的距离。最终求答案的过程我们可以遍历每一个空格子，然后假设起点到这个格子是两个最短路的重合段，用起点到该格子的距离加上两个终点到该格子的距离就是两个最短路的非重复的格子数。最后用总空格子数减去最小的非重复格子数就是答案。

        

// Problem: F. Vova Escapes the Matrix
// Contest: Codeforces - Codeforces Round 910 (Div. 2)
// URL: https://codeforces.com/contest/1898/problem/F
// Memory Limit: 256 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
using namespace std;
#define LL long long
#define pb push_back
#define x first
#define y second 
#define endl '\n'
const LL maxn = 4e05+7;
const LL N=1e05+10;
const LL mod=1e09+7;
typedef pair<int,int>pl;
priority_queue<LL , vector<LL>, greater<LL> >t;
priority_queue<LL> q;
LL gcd(LL a, LL b){
	return b > 0 ? gcd(b , a % b) : a;
}

LL lcm(LL a , LL b){
	return a / gcd(a , b) * b;
}
int n , m;
int a[N];
void init(int n){
	for(int i = 0 ; i <= n ; i ++){
		a[i] = 0;
	}
}
int tx[4] = {0 , 1 , 0 , -1};
int ty[4] = {1 , 0 , -1 , 0};
struct Node{
	int x , y;
	int stx , sty;
	int d;
};
void solve() 
{
	cin >> n >> m;
	string str[n + 5];
	queue<Node>q;//存放终点
	for(int i = 0 ; i < n ; i ++){
		cin >> str[i];
	}
    int sx = -1, sy = -1;
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            if (str[i][j] == 'V') {
                sx = i, sy = j;
            }
        }
    }
	vector<vector<vector<Node> > >mp(n, vector<vector<Node>>(m));
	auto check = [&] (int x , int y){
		return x >= 0 && x < n && y >= 0 && y < m && str[x][y] != '#';
	};
	auto add = [&](int x , int y){
		if(check(x , y)){
			q.push({x , y , x , y , 0});	
			mp[x][y].pb({x , y , x , y , 0});
		}
	};
	for(int i = 0 ; i < n ; i ++){
		add(i , 0);
		add(i , m - 1);
	}
	for(int i = 0 ; i < m ;i ++){
		add(0 , i);
		add(n - 1 , i);
	}
	while(!q.empty()){
		auto tmp = q.front();
		q.pop();
		for(int i = 0 ; i < 4; i ++){
			int nx = tmp.x + tx[i];
			int ny = tmp.y + ty[i];
			if(check(nx , ny)){
				if(mp[nx][ny].size() == 0 || (mp[nx][ny].size() == 1 && (tmp.stx != mp[nx][ny][0].stx || tmp.sty != mp[nx][ny][0].sty))){
					mp[nx][ny].pb({nx , ny , tmp.stx , tmp.sty , tmp.d + 1});
					q.push({nx , ny , tmp.stx , tmp.sty , tmp.d + 1});
				}
			}
		}
	}
	int ans = 0;
	for(int i = 0 ; i < n ; i ++){
		for(int j = 0 ; j < m ; j ++){
			if(str[i][j] == '.'){
				ans++;//空格子数量
			}
		}
	}
	if(mp[sx][sy].size() == 0){//无终点到达
		cout << ans << endl;
	}
	else if(mp[sx][sy].size() == 1){//只有1个终点能到达
		cout << ans - mp[sx][sy][0].d<<endl;
	}
	else{
		int vis[n][m];
		memset(vis , 0 , sizeof vis);
		queue<array<int,3>>q;
		int mi = 1e9;
		q.push({sx , sy , 0});
		vis[sx][sy] = 1;
		if(mp[sx][sy].size() == 2){
			mi =  mp[sx][sy][0].d + mp[sx][sy][1].d;
		}
		while(!q.empty()){
			auto tmp = q.front();
			q.pop();
			for(int i = 0 ; i < 4 ; i ++){
				int nx = tmp[0] + tx[i];
				int ny = tmp[1] + ty[i];
				if(check(nx , ny) && !vis[nx][ny]){
					if(mp[nx][ny].size() == 2){
						mi = min(mi , mp[nx][ny][0].d + mp[nx][ny][1].d + tmp[2] + 1);
					}
					q.push({nx , ny , tmp[2] + 1});
					vis[nx][ny] = 1;
				}
			}
		}
		cout << ans - mi << endl;
	}
}            
int main() 
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cout.precision(10);
    int t=1;
	cin>>t;
    while(t--)
    {
    	solve();
    }
    return 0;
}

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：/a/166396.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

Appium自动化测试：通过appium的inspector功能无法启动app的原因

Appium自动化测试：通过appium的inspector功能无法启动app的原因

在打开appium-desktop程序&#xff0c;点击inspector功能&#xff0c;填写app的配置信息&#xff0c;启动服务提示如下&#xff1a; 报错信息&#xff1a; An unknown server-side error occurred while processing the command. Original error: Cannot start the cc.knowyo…
阅读更多...
C/C++统计数 2021年12月电子学会青少年软件编程（C/C++）等级考试一级真题答案解析

C/C++统计数 2021年12月电子学会青少年软件编程（C/C++）等级考试一级真题答案解析

目录 C/C统计数 一、题目要求 1、编程实现 2、输入输出 二、算法分析 三、程序编写 四、程序说明 五、运行结果 六、考点分析 C/C统计数 2021年12月 C/C编程等级考试一级编程题 一、题目要求 1、编程实现 给定一个数的序列S&#xff0c;以及一个区间[L, R], 求序列…
阅读更多...
环境配置|GitHub——解决Github无法显示图片以及README无法显示图片

环境配置|GitHub——解决Github无法显示图片以及README无法显示图片

一、问题背景 最近在整理之前写过的实验、项目&#xff0c;打算把这些东西写成blog&#xff0c;并把工程文件整理上传到Github上。但在上传README文件的时候&#xff0c;发现github无法显示README中的图片&#xff0c;如下图所示&#xff1a; 在README中该图片路径为&#xff1…
阅读更多...
【LeetCode刷题日志】232.用栈实现队列

【LeetCode刷题日志】232.用栈实现队列

&#x1f388;个人主页&#xff1a;库库的里昂 &#x1f390;C/C领域新星创作者 &#x1f389;欢迎 &#x1f44d;点赞✍评论⭐收藏✨收录专栏&#xff1a;LeetCode 刷题日志&#x1f91d;希望作者的文章能对你有所帮助&#xff0c;有不足的地方请在评论区留言指正&#xff0c;…
阅读更多...
算法——动态规划（新）

算法——动态规划（新）

什么是动态规划&#xff1f; 动态规划算法的基本思想-求解步骤-基本要素和一些经典的动态规划问题【干货】-CSDN博客 一、三步问题 面试题 08.01. 三步问题 - 力扣&#xff08;LeetCode&#xff09; 思路 我们要知道&#xff0c;走楼梯&#xff0c;前三个阶梯步数已经知道&…
阅读更多...
Git分支详解

Git分支详解

文章目录 一、分支1.1 查看本地分支1.2 创建本地分支1.3 切换分支&#xff08;checkout&#xff09;1.1 合并分支&#xff08;merge&#xff09;1.1 删除分支 二、解决冲突三、实际开发中分支使用原则和流程四、案例&#xff1a;创建并切换到dev01分支&#xff0c;在dev01分支提…
阅读更多...
计算机网络期末复习（知识点）

计算机网络期末复习（知识点）

一、计算机网络体系结构 计算机网络&因特网&#xff1a; 计算机网络定义&#xff1a;将地理位置不同的具有独立功能的多台计算机及其外部设备&#xff0c;通过通信线路连接起来&#xff0c;在网络操作系统&#xff0c;网络关联软件及网络协议的管理和协调下&#xff0c;实…
阅读更多...
软件测试技术之地图导航的测试用例

软件测试技术之地图导航的测试用例

外观测试 屏幕显示不能有花屏、黑点和闪屏&#xff0c;清晰度、亮度、颜色要正常。 检测所有按键都能起到相应作用&#xff0c;是否手感不良。 UI显示状态、颜色、清晰度、效果。 控制&#xff1a;放大&#xff0c;缩小&#xff0c;音量调节功能测试。 交叉路口查询测试&am…
阅读更多...
AIGC实战 - 使用变分自编码器生成面部图像

AIGC实战 - 使用变分自编码器生成面部图像

AIGC实战 - 使用变分自编码器生成面部图像 0. 前言1. 数据集分析2. 训练变分自编码器2.1 变分自编码器架构2.2 变分自编码器分析 3. 生成新的面部图像4. 潜空间算术5. 人脸变换小结系列链接 0. 前言 在自编码器和变分自编码器上&#xff0c;我们都仅使用具有两个维度的潜空间。…
阅读更多...
【算法挨揍日记】day28——413. 等差数列划分、978. 最长湍流子数组

【算法挨揍日记】day28——413. 等差数列划分、978. 最长湍流子数组

413. 等差数列划分 413. 等差数列划分 题目描述&#xff1a; 如果一个数列 至少有三个元素 &#xff0c;并且任意两个相邻元素之差相同&#xff0c;则称该数列为等差数列。 例如&#xff0c;[1,3,5,7,9]、[7,7,7,7] 和 [3,-1,-5,-9] 都是等差数列。 给你一个整数数组 nums…
阅读更多...
性能测试学习——项目环境搭建和Jmete学习二

性能测试学习——项目环境搭建和Jmete学习二

项目环境搭建、Jmeter学习二 环境的部署虚拟机的安装虚拟机中添加项目操作步骤 使用环境的注意事项Jmeter的安装和简单使用Jemter的使用的进阶Jemter元件 Jmeter属性执行顺序和作用域作用域以自定义用户变量和用户参数(前置处理器)为例如何解决用户变量和线程组同级时&#xff…
阅读更多...
Node.js之TCP（net）

Node.js之TCP（net）

Hi I’m Shendi Node.js之TCP&#xff08;net&#xff09; 最近使用Nodejs编写程序&#xff0c;需要用到自己编写的分布式工具&#xff0c;于是需要将Java版的用NodeJs重新写一遍&#xff0c;需要使用到TCP通信&#xff0c;于是在这里记录下Node.js TCP 的使用方法 依赖 需要使…
阅读更多...
c语言-输入输出详解

c语言-输入输出详解

文章目录 格式化输入输出占位符printfscanf 字符串输入输出puts&#xff08;&#xff09;gets&#xff08;&#xff09; 字符输入输出putchar&#xff08;&#xff09;getchar&#xff08;&#xff09; 区别 格式化输入输出 输入输出的库函数的头文件&#xff1a; #include<…
阅读更多...
动态规划专项---最长上升子序列模型

动态规划专项---最长上升子序列模型

文章目录 怪盗基德的滑翔翼登山合唱队形友好城市最大上升子序列和拦截导弹导弹防御系统最长公共上升子序列 一、怪盗基德的滑翔翼OJ链接 本题思路:本题是上升子序列模型中比较简单的模型&#xff0c;分别是从前往后和从后往前走一遍LIS即可。 #include <bits/stdc.h>co…
阅读更多...
Linux——编译器gcc/g++、调试器gdb以及自动化构建工具makefilemake详解

Linux——编译器gcc/g++、调试器gdb以及自动化构建工具makefilemake详解

编译器—gcc/g、调试器—gdb以及自动化构建工具—makefile&&make 文章目录 编译器—gcc/g、调试器—gdb以及自动化构建工具—makefile&&make1. 编译器——gcc/g1.1 生成可执行文件与修改默认可执行文件1.2 程序的翻译过程以及对应的gcc选项1.2.1 预处理 gcc -E…
阅读更多...
边缘计算是如何为元宇宙提供动力的？

边缘计算是如何为元宇宙提供动力的？

构建元宇宙虚拟世界并不简单&#xff0c;也并不便宜&#xff0c;但是还是有许多大型公司正在转移大量资源来开发他们的元宇宙业务&#xff0c;当然大部分企业注意力都围绕着 VR 耳机、AR 眼镜、触觉手套和其他沉浸式虚拟现实体验所需的可穿戴硬件。虽然这种沉浸式的体验是最终结…
阅读更多...
【Django使用】django经验md文档10大模块。第4期：Django数据库增删改查

【Django使用】django经验md文档10大模块。第4期：Django数据库增删改查

Django的主要目的是简便、快速的开发数据库驱动的网站。它强调代码复用&#xff0c;多个组件可以很方便的以"插件"形式服务于整个框架&#xff0c;Django有许多功能强大的第三方插件&#xff0c;你甚至可以很方便的开发出自己的工具包。这使得Django具有很强的可扩展…
阅读更多...
WSL 2 更改默认安装的 Linux 发行版

WSL 2 更改默认安装的 Linux 发行版

目录 什么是 WSL 2&#xff1f;更改默认安装的 Linux 发行版更改发行版的 WSL 版本 什么是 WSL 2&#xff1f; WSL 2 是适用于 Linux 的 Windows 子系统体系结构的一个新版本&#xff0c;它支持适用于 Linux 的 Windows 子系统在 Windows 上运行 ELF64 Linux 二进制文件。 它的…
阅读更多...
nn.KLDivLoss,nn.CrossEntropyLoss,nn.MSELoss,Focal_Loss

nn.KLDivLoss,nn.CrossEntropyLoss,nn.MSELoss,Focal_Loss

KL loss&#xff1a;https://blog.csdn.net/qq_50001789/article/details/128974654 https://pytorch.org/docs/stable/nn.html 1. nn.L1Loss 1.1 公式 L1Loss: 计算预测 x和 目标y之间的平均绝对值误差MAE, 即L1损失&#xff1a; l o s s 1 n ∑ i 1 , . . . n ∣ x i…
阅读更多...
leetcode算法之分治-快排

leetcode算法之分治-快排

目录 1.颜色分类2.排序数组3.数组中的第k个最大元素4.最小的k个数 1.颜色分类 颜色分类 class Solution { public:void sortColors(vector<int>& nums) {int n nums.size();int left -1,rightn,i0;while(i<right){if(nums[i] 0) swap(nums[left],nums[i]);e…
阅读更多...
最新文章

Copyright @ 2022~2023