Codeforces Round 866 (Div. 2)

A. Yura's New Name

题意:

给出一个仅由_或^组成的字符串,你可以在任意位置添加_或^字符,使得字符串满足:
任意字符要么属于^_^的一部分,要么属于^^的一部分。求最少添加的字符数量。

分析:

  1. 对于_我们只需处理没有组成^_^的_:
    ①如果_在首位置且左边没有^则添加^
    ②如果_在尾位置且右边没有^则添加^
    ③如果_在中间部分且右边没有^则添加^
  2. 当字符串只有一个^时末尾添加一个^

code:

#include <bits/stdc++.h>
using namespace std;

int main()
{
	std::ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);
	
	int t;
	cin >> t;
	
	while (t --)
	{
		string s;
		cin >> s;
		
		int cnt = 0;
		for (int i = 0; i < s.size(); i ++)
		{
			if (!i && s[i] == '_')
				cnt ++;
			if (s[i] == '_' && i + 1 < s.size() && s[i + 1] != '^') 
				cnt ++;
		}
		
		if (s[s.size() - 1] == '_' || (s.size() == 1 && s[0] == '^'))
			cnt ++;
			
		cout << cnt << endl;
	}
	
	return 0;
}

B. JoJo's Incredible Adventures

题意:

给定一个长度为n的01串,每次向右循环移动一位,例如00111->10011,循环移动n-1次,得到一个n×n的矩阵。取一个最大的子矩阵,这个矩阵的元素均为1,求其面积。

分析:

  1. 若全为1:S_max = n × n。
  2. 若不全为1:
    考虑全为1的最长子串,其长度为k。设矩阵的长宽分别为a, b。则a + b = k + 1。
    S = ab,S当且仅当a = b = (k + 1) / 2时取最大值(基本不等式)。由于每移动一次a减1,b 加1,当a = b = (k + 1) / 2时一共移动(k + 1) / 2 - 1次,(k + 1) / 2 - 1 < n - 1,所以S_max能取到。

code:

#include <bits/stdc++.h>
using namespace std;

typedef long long LL;

int main()
{
	std::ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);
	
	int t;
	cin >> t;
	
	while (t --)
	{
		string s;
		cin >> s;
		
		if (s.size() == 1)
			cout << (s[0] == '0' ? 0 : 1) << endl;
		else
		{
			LL len_m = 0, n = s.size();
			int idx = s.find('0');
			if (idx == -1)
				cout << n * n << endl;
			else
			{
				s += s;
				for (int i = 0; i < s.size(); i ++)
				{
					LL len = 0;
					while (s[i] == '1' && i < s.size())
						len ++, i ++;
					len_m = max(len_m, len);
				}
				cout << (len_m + 1) * (len_m + 1) / 4 << endl;
			}
		}
	}
	
	return 0;
}

C. Constructive Problem

题意:

能否只进行一次操作:"将序列a中的某个子序列修改为k",使得mex(a)恰好比原来多1。
mex(a)即不在集合a中的最小非负整数。

分析:

  1. 当只有一个元素时:若该元素不为0则输出"Yes",否则输出"No"
  2. 当有多个元素时:
    ①序列中不存在Mex + 1:只有当原序列是0,1,2,...,n - 1即n = Mex时输出"No",否则输出"Yes"。因为当n != Mex时我们可以将任意比Mex大的元素换成Mex使得最后mex(a) = Mex + 1
    ②序列中存在Mex:目的是增加Mex,消去Mex + 1。考虑贪心,将包含Mex + 1的最短子序列全部赋值为Mex,最后check一下mex(a)是否等于Mex + 1,如果等于输出"Yes"否则输出"No"。

code:

#include <bits/stdc++.h>
using namespace std;

typedef long long LL;
const int N = 2e6 + 5;
int a[N];

int Mex(int b[], int n)
{
	set<int> s;
	
	for (int i = 0; i < n; i ++)
		s.insert(b[i]);
	
	for (int i = 0;; i ++)
		if (s.count(i) == 0)
			return i;
}

int main()
{
	std::ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);
	
	int t;
	cin >> t;
	
	while (t --)
	{
		int n;
		cin >> n;
		
		unordered_map<int, int> mp; 
		int mex = 0, mex2 = 0;
		
		for (int i = 0; i < n; i ++)
		{
			cin >> a[i];
			mp[a[i]] += 1;
		}
		
		mex = Mex(a, n);
		
		if (n == 1)
		{
			if (a[0] == 0)
				cout << "No" << endl;
			else
				cout << "Yes" << endl;
		}
		else
		{
			if (mp[mex + 1] == 0)
			{
				if (n == mex)
					cout << "No" << endl;
				else
					cout << "Yes" << endl;
			}
			else
			{
				int l = 0x3f3f3f3f, r = -1;
				for (int i = 0; i < n; i ++)
				{
					if (a[i] == mex + 1)
					{
						l = min(l, i);
						r = max(r, i);
					}
				}
				for (int i = l; i <= r; i ++)
					a[i] = mex;
				
				mex2 = Mex(a, n);
				
				if (mex2 == mex + 1)
					cout << "Yes" << endl;
				else
					cout << "No" << endl;
			}
		}
	}
	
	return 0;
}

原文链接:https://www.cnblogs.com/XiongTingyang/p/17323325.html

本站文章如无特殊说明,均为本站原创,如若转载,请注明出处:Codeforces Round 866 (Div. 2) - Python技术站

(0)
上一篇 2023年4月25日
下一篇 2023年4月25日

相关文章

  • python实现决策树C4.5算法详解(在ID3基础上改进)

    Python实现决策树C4.5算法详解(在ID3基础上改进) 决策树是一种常见的机器学习算法,它可以用于分类和回归问题。C4.5算法是一种基于信息增益比的决策树算法,它在ID3算法的基础上进行了改进,可以处理连续属性和缺失值。在本文中,我们将介绍如何使用Python实现C4.5算法,并详细讲解实现原理。 实现原理 C4.5算法的实现原理比较复杂,我们可以分为…

    python 2023年5月14日
    00
  • python 算法题——快乐数的多种解法

    下面是关于“Python算法题——快乐数的多种解法”的完整攻略。 1. 题目描述 快乐数是指:对于一个正整数,每一次将该数替换为它每个位置上的数字的平方和,然后重复这个过程直到这个数变为 1,或者是无限循环但始终变不到 1。如果可以变为 1,那么这个数就是快乐数。 例如,19 是一个快乐数,计算过程如下: 1^2 + 9^2 = 828^2 + 2^2 = …

    python 2023年5月13日
    00
  • Python实现简单层次聚类算法以及可视化

    Python实现简单层次聚类算法以及可视化 层次聚类是一种常用的聚类算法,它可以将数据集分成不同的层结构。本文中,我们将介绍如何使用Python实现简单层次聚类法以及可视化。我们将分为以下几个步骤: 加载数据集 数据预处理 定义层次聚类法 可视化聚类结果 示例说明 步骤1:加载数据集 在实现层次聚类算法之前,需要加载数据集。在这个例子中,我们将使用Iris数…

    python 2023年5月14日
    00
  • oracle 数据库学习 基本结构介绍

    Oracle 数据库学习:基本结构介绍攻略 概述 Oracle 数据库是目前世界上使用最为广泛的一种关系型数据库。学习 Oracle 数据库需要具备一定的数据库基础知识,特别是SQL语言的使用,才能更好地理解 Oracle 数据库的基本结构。本攻略将从以下几个方面介绍 Oracle 数据库的基本结构: 数据库系统组成; Oracle 实例; 数据库; 表空间…

    数据结构 2023年5月17日
    00
  • Lua学习笔记之数据结构

    下面开始对”Lua学习笔记之数据结构”的完整攻略进行详细说明。 一、前言 在学习Lua时,数据结构是非常重要的一个方面,掌握了数据结构,就可以更好地编写Lua程序,提高程序的性能和可读性。本篇攻略主要介绍四种Lua数据结构:数组、表、字符串和函数,分别介绍其含义、特点、创建方法以及基本操作。 二、数组 2.1 数组的定义和创建 Lua中的数组是一种类似于C语…

    数据结构 2023年5月17日
    00
  • JavaScript 处理树数据结构的方法示例

    下面是“JavaScript 处理树数据结构的方法示例”的完整攻略。 什么是树数据结构 树形数据结构是一种非常重要的数据结构,常被用于模拟现实中大量的层级结构。例如:文件目录、网站导航等。其是由一个根节点和若干个子节点构成的,每个节点可以有0个或多个子节点。 使用 JavaScript 处理树形数据结构 了解了树形数据结构后,我们可以使用 JavaScrip…

    数据结构 2023年5月17日
    00
  • Python 深入了解opencv图像分割算法

    Python深入了解OpenCV图像分割算法 OpenCV是一个广泛使用的计算机视觉库,它提供了许多图像处理和计算机视觉算法。其中,图像分割是计算机视觉中的重要问题,它的目标是将图像分成不同的区域,每个区域具有相似的特征。在本文中,我们将深入了解OpenCV中的图像分割算法,并提供两个示例说明。 图像分割算法 图像分割算法可以分为两类:基于区域的分割和基于边…

    python 2023年5月14日
    00
  • 蒙特卡罗方法:当丢失确定性时的处理办法

    一、简介   蒙特卡罗(Monte Carlo),也可翻译为蒙特卡洛,只是不同的音译选词,比较常用的是蒙特卡罗。是摩洛哥的一片城区,以拥有豪华赌场闻名,蒙特卡罗方法是基于概率的。基本思想:如果你想预测一件事情的结果,你只要把随机生成的各种输入值,把这件事模拟很多遍,根据模拟出的结果就可以看到事情的结果大致是什么情况。蒙特卡罗算法是基于蒙特卡罗方法的算法。 二…

    算法与数据结构 2023年4月17日
    00
合作推广
合作推广
分享本页
返回顶部