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查找算法之插补查找算法的实现

    Python查找算法之插补查找算法的实现 插补查找算法是一种高效的查找算法,它是在二分查找算法的基础上进行改进的。插补查算法的基本思想是根据查找值在查找表中的位置进行插值计算,从而确定下一次查找的位置。本文将详细讲解Python查找算法之插补查找算法的实现,包括算法原理、Python实现过程和示例。 算法原理 插补查找算法是一基于二分查找法的改进算法,它的基…

    python 2023年5月13日
    00
  • Python实现迪杰斯特拉算法过程解析

    Python实现迪杰斯特拉算法过程解析 迪杰斯特拉算法是一种用于解决带权图中单源最短路径问题的贪心算法。它的本思想是从起点开始,逐步扩展其他节点,每次选择当前距离起点最近的节点,并更新与该节点相邻的节点距离。本文将详细介绍Python实现迪杰斯特拉算法的过程,并提供两个示例说明。 迪杰斯特算的实现 1. 初始化 首先,我们需要初始化一个距离列表和一个已访问列…

    python 2023年5月13日
    00
  • 字典树的基本知识及使用C语言的相关实现

    字典树的基本知识 字典树,英文名为Trie树,又称单词查找树或键树,是一种树形数据结构,用于表示关联数组或映射。它的优点是,可以大大减少无谓的字符串比较,查询效率比哈希表高。 字典树的核心概念是节点,每个节点包含一个字符和指向子节点的指针。根节点为空字符,每个字符串以一个独立的路径插入节点。如果一个字符串是另一个字符串的前缀,那么这个字符串的节点是另一个字符…

    数据结构 2023年5月17日
    00
  • C++数据结构之堆详解

    C++数据结构之堆详解 什么是堆 堆是一种完全二叉树。 堆分为大根堆和小根堆,大根堆满足每个节点的值都大于等于它的子节点,小根堆满足每个节点的值都小于等于它的子节点。 堆的实现 常见的实现堆的方式有数组和链表两种。 数组 由于二叉堆是完全二叉树,所以可以用数组来实现: 对于一个节点i,它的左子节点的下标是2 * i + 1,右子节点的下标是2 * i + 2…

    数据结构 2023年5月17日
    00
  • 利用python实现PSO算法优化二元函数

    下面是详细讲解“利用Python实现PSO算法优化二元函数”的完整攻略。 PSO算法 粒子群优化算法(Particle Swarm Optimization,PSO)是一种基于群体智能的化算法,它模拟了鸟群捕食的行为,通过不断调整粒子的位置和速度来寻找最优解。 PSO法的基本思想是将待化问题看作一个多维空间中的搜索问题,将每个解看作空间中的一个粒子通过不断调…

    python 2023年5月14日
    00
  • 在Python中实现贪婪排名算法的教程

    在Python中实现贪婪排名算法的教程 贪婪排名算法是一种常用的排序算法,其基本思想是根据每个元素的权重值进行排序,从而得到排名列表。在Python中可以使用sorted()函数实现贪婪排名算法。本文将详细讲解Python实现贪婪排名算法的完整攻略,包算法原理、Python实现过程和示例。 算法原理 贪婪排名算法的基本思想是:根据每个素的权重值进行排序,从而…

    python 2023年5月14日
    00
  • 深入解析MySQL索引数据结构

    深入解析MySQL索引数据结构 MySQL索引是优化查询效率的重要一环,本文将深入解析MySQL索引数据结构,帮助读者理解MySQL索引原理,并通过两个示例说明不同类型的索引在实际应用中的效果。 索引数据结构 MySQL支持两种类型的索引数据结构:B-Tree索引和Hash索引。 B-Tree索引 B-Tree索引是MySQL常用的索引类型,用于优化WHER…

    数据结构 2023年5月17日
    00
  • C++数据结构之链表详解

    C++数据结构之链表详解 链表是一种重要的数据结构,它可以动态的分配内存空间,实现灵活的元素插入,删除等操作。本文将详细讲解链表的定义、实现、常见操作以及链表的应用。 定义与特点 链表是一种线性表数据结构,由一系列节点组成,每个节点包含数据和指向下一个节点的指针。链表分为单向链表和双向链表,其中单向链表的每个节点只包含一个指针,指向下一个节点,而双向链表的每…

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