Codeforces Round 970 (Div. 3)(ABCDEF)

Codeforces Round 970 (Div. 3)

A:Sakurako's Exams

签到

题意:给定1,2的数量,判断是否能用加减符号使得这些1,2计算出0

void solve()
{
	cin>>n>>m;
	if(n%2)cout<<"NO\n";
	else
	{
		if(m%2==0||n)cout<<"YES\n";
		else cout<<"NO\n";
	}
	return ;
}

B:Square or Not

签到

题意:给定01序列,问从上到下，从左到右排列是否可以得到一个周围为1,内部为0的正方形

void solve()
{
	string s;
	cin>>n;
	cin>>s;
	int t=sqrt(n);
	if(t*t!=n)
	{
		cout<<"No\n";
		return;
	}
	else 
	{
		int idx=0;
		for(int i=0;i<t;i++)
		{
			for(int j=0;j<t;j++)
			{
				int now=i*t+j;
				if(i==0||j==0||i==t-1||j==t-1)
				{
					if(s[now]=='0')
					{
						cout<<"No\n";
						return;
					}
				}
				else if(s[now]=='1')
				{
					cout<<"No\n";
					return;
				}
			}
		}
	}
	cout<<"Yes\n";
	return ;
}

C:Longest Good Arrays

题意:给定左右边界了l,r,问在范围内凑出最长的满足a[i]-a[i-1]<a[i+1]-a[i](i>=2)的最长数组的长度

思路:最优一定是前后两项差从左到右分别为1,2,3,4...,所以二分数组最后一个元素,满足小于r-l的第一个元素位置，再+1就是答案

int n,m;
int cha;
bool check(int x)
{
	return (x+1)*x/2>cha;
}
void solve()
{
	cin>>n>>m;
	cha=m-n;
	int l=0,r=1e8;
	while(l+1<r)
	{
		int mid=l+r>>1;
		check(mid)?r=mid:l=mid;
	}
	cout<<l+1<<'\n';
	return ;
}

D:Sakurako's Hobby

题意:输入一个数组大小n,然后输入n个数q[i](1<=i<=n)代表i可以到达q[i]（保证q数组一定是一个排列）,然后输入一个01串,当第i个位置为‘1’代表为白块，为'0'代表为黑块,f[i]为能够到达i这个点的所有黑块的数量,输出所有f[i](1<=i<=n)

例如:

输入

2

2 1

00

输出

2 2 

(因为1位置的点都能由1,2到达)

思路:并查集,把所有有联系的点都缩到一个根上(由于是一个排列，所以所有可以直接可以到达或者间接到达的点都可以形成一个环，也就是相互到达)，最后问f[i]只需要把一个环中的所有店都累加到find(i),也就是根节点上

代码:

#include <map>
#include <set>
#include <queue>
#include <deque>
#include <cmath>
#include <vector>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <unordered_map>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define pp pop_back()
#define int long long
#define laile cout<<"laile"<<endl
#define lowbit(x) ((x)&(-x))
#define double long double
#define sf(x) scanf("%lld",&x)
#define sff(x,y) scanf("%lld %lld",&x,&y)
#define sd(x) scanf("%Lf",&x)
#define sdd(x,y) scanf("%Lf %Lf",&x,&y)
#define _for(i,n) for(int i=0;i<(n);++i)
#define _rep(i,a,b) for(int i=(a);i<=(b);++i)
#define _pre(i,a,b) for(int i=(a);i>=(b);--i)
#define all(x) (x).begin(), (x).end()
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
typedef unsigned long long ULL;
typedef pair<int,int>PII;
const int N=1e6+10,INF=4e18;
int n,m;
int f[N],q[N],cnt[N];
bool st[N];
int find(int x)
{
	if(x!=f[x])return f[x]=find(f[x]);
	return f[x];
}
void root(int a,int b)
{
	int x=find(a),y=find(b);
	if(x!=y)f[x]=y;
}
void solve()
{
	cin>>n;
	_rep(i,1,n)cin>>q[i],f[i]=i,st[i]=false,cnt[i]=0;
	string s;
	cin>>s;
	s=" "+s;
	_rep(i,1,n)
	{
		int now=i;
		while(!st[now])
		{
			st[now]=true;
			root(now,q[now]);
			now=q[now];
		}
	}	
    _rep(i,1,n)
		if(s[i]=='0')
			cnt[find(i)]++;
	_rep(i,1,n)
		cout<<cnt[find(i)]<<" ";
	cout<<'\n';
	return ;
}
signed main()
{
	IOS;
	int T=1;
	cin>>T;
	while(T--)
		solve();
	return 0;
}

E:Alternating String

题意:给定一个字符串,现在有两个操作

1:选一个字母删除(但是这个最多只能操作一次)

2:将一个位置的字母改成另一个字母

问你把这个字符串变成一个:奇数位置字母都相同,偶数位置字母都相同 的字符串的最小操作次数

思路

只要发现一个特点就可以想到这个思路,那就是当你选择把当前这个点i的字母删除之后，后面所有的字母所在的奇偶位置就发生了互换

1.首先考虑不删除字母的情况

维护一个hou[26][2]的数组,其中第一维代表哪个字母(0~25),第二维 0/1 代表 奇数位/偶数位 

那么我首先遍历奇数位置的所有字母,求和sum就是奇数位置字母的数量,求最大值ma就是奇数位置 字母的众数那么sum-ma就是奇数位置最少需要改变的字母的数量

偶数位置同理，那么就能求导不删除字母情况下最小操作次数

2,考虑删除字母的情况

假如我现在删除的是i号点,那么1~i-1号点的奇偶性质未发生改变,那么我就从小到大遍历即可,i+1~n号点的奇偶性质全部发生了改变,那么显然如果我能预处理出i+1~n的所有状态，也就是前面说到的hou[26][2],那么奇数位本来是hou[0~25][0]现在只需要考虑hou[0~25][1]，偶数位置同理，那么就可以发现这个hou[0~25][2]显然可以提前预处理出来，然后遍历到第i个点的时候把1~i的状态删去就行，这些都可以线性处理，时间复杂度O(26*n)

代码:

#include <map>
#include <set>
#include <queue>
#include <deque>
#include <cmath>
#include <vector>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <unordered_map>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define pp pop_back()
#define int long long
#define laile cout<<"laile"<<endl
#define lowbit(x) ((x)&(-x))
#define double long double
#define sf(x) scanf("%lld",&x)
#define sff(x,y) scanf("%lld %lld",&x,&y)
#define sd(x) scanf("%Lf",&x)
#define sdd(x,y) scanf("%Lf %Lf",&x,&y)
#define _for(i,n) for(int i=0;i<(n);++i)
#define _rep(i,a,b) for(int i=(a);i<=(b);++i)
#define _pre(i,a,b) for(int i=(a);i>=(b);--i)
#define all(x) (x).begin(), (x).end()
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
typedef unsigned long long ULL;
typedef pair<int,int>PII;
const int N=1e6+10,INF=4e18;
int n,m;
int now[26][2],hou[26][2];//now储存1~i-1的状态,hou储存i+1~n的状态
void solve()
{
	cin>>n;
	string s;
	cin>>s;
	memset(now,0,sizeof(now));
	memset(hou,0,sizeof(hou));
	s=" "+s;
	_rep(i,1,n)
		hou[s[i]-'a'][i%2]++;
	int res=0,sum,ma;
	_rep(j,0,1)
	{
		sum=0;	
		ma=0;
		_rep(i,0,25)
		{
			sum+=hou[i][j];
			ma=max(hou[i][j],ma);
		}
		res+=sum-ma;
	}
	if(n%2)
	{
		res=INF;
		_rep(i,1,n)
		{
			int nowres=0;
			hou[s[i]-'a'][i%2]--;
			_rep(j,0,1)
			{
				sum=0;
				ma=0;
				_rep(k,0,25)
				{
					sum+=hou[k][j];
					sum+=now[k][j^1];
					ma=max(ma,hou[k][j]+now[k][j^1]);
				}
				nowres+=sum-ma;
			}
			now[s[i]-'a'][i%2]++;
			res=min(res,nowres+1);
		}
	}
	cout<<res<<"\n";
	return ;
}
signed main()
{
	IOS;
	int T=1;
	cin>>T;
	while(T--)
		solve();
	return 0;
}

F:Sakurako's Boxt

题意:给定一个数组,为元素之间两两相乘(a[1]*a[2]和a[2]*a[1]重复不算)的平均数是什么

思路:

假设四个元素a_1,a_2,a_3,a_4

那么答案就是\frac{a_1*a_2+a_1*a_3+a_1*a_4+a_2*a_3+a_2*a_4+a_3*a_4}{6}

等价于\frac{a_1*(a_2+a_3+a_4)+a_2*(a_3+a_4)+a_3*(a_4)}{C\binom{2}{4}}

用一个后缀和维护形如(a_2+a_3+a_4)的东西这道题就轻松解决了,只需要注意一下取模和乘法逆元的问题就行了

#include <map>
#include <set>
#include <queue>
#include <deque>
#include <cmath>
#include <vector>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <unordered_map>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define pp pop_back()
#define int long long
#define laile cout<<"laile"<<endl
#define lowbit(x) ((x)&(-x))
#define double long double
#define sf(x) scanf("%lld",&x)
#define sff(x,y) scanf("%lld %lld",&x,&y)
#define sd(x) scanf("%Lf",&x)
#define sdd(x,y) scanf("%Lf %Lf",&x,&y)
#define _for(i,n) for(int i=0;i<(n);++i)
#define _rep(i,a,b) for(int i=(a);i<=(b);++i)
#define _pre(i,a,b) for(int i=(a);i>=(b);--i)
#define all(x) (x).begin(), (x).end()
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
typedef unsigned long long ULL;
typedef pair<int,int>PII;
const int N=1e6+10,INF=4e18,P=1e9+7;
int n,m;
int hou[N],q[N];
int qmi(int a,int b)
{
	int res=1;
	while(b)
	{
		if(b&1)res=res*a%P;
		a=a*a%P;
		b>>=1;
	}
	return res;
}
void solve()
{
	cin>>n;
	_rep(i,1,n)cin>>q[i];
	hou[n+1]=0;
	_pre(i,n,1)
		hou[i]=hou[i+1]+q[i];
	int res=0;
	_rep(i,1,n)
	{
		res+=(q[i]*(hou[i+1]%P)%P);
		res%=P;
	}
//	cout<<"res="<<res<<" "<<n<<endl;
	
	cout<<(res*qmi((n*(n-1)/2)%P,P-2)%P)<<'\n';
	return ;
}
signed main()
{
	IOS;
	int T=1;
	cin>>T;
	while(T--)
		solve();
	return 0;
}

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

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

相关文章

如何在docker容器中导入.sql文件

如何在docker容器中导入.sql文件

一、准备工作 确保容器运行&#xff1a; 首先确认包含 MySQL 服务的 Docker 容器正在运行。可以通过 docker ps 命令查看正在运行的容器列表。如果容器未运行&#xff0c;使用 docker start [container_id] 命令启动容器。 准备数据库文件&#xff1a; 将需要导入的数据库文件&…
阅读更多...
用户画像的人群圈选

用户画像的人群圈选

背景 用户画像的人群圈选一般涉及到bitmap的运算&#xff0c;我们可以使用java中的RoaringBitmap进行运算&#xff0c;也可以直接使用ck的bitmap进行运算&#xff0c;本文就来看一下这两种方式 人群圈选 使用java的RoaringBitmap进行运算&#xff1a; 使用clickhouse的bit…
阅读更多...
145-Linux权限维持Rootkit后门Strace监控Alias别名Cron定时任务

145-Linux权限维持Rootkit后门Strace监控Alias别名Cron定时任务

参考 【权限维持】Linux&Rootkit后门&Strace监控&Alias别名&Cron定时任务_alias lsalerts(){ ls $* --colorauto;python -c "-CSDN博客 参考 FlowUs 息流 - 新一代生产力工具 权限维持-Linux-定时任务-Cron后门 利用系统的定时任务功能进行反弹Shell 1…
阅读更多...
用Unity2D制作一个人物，实现移动、跳起、人物静止和动起来时的动画：中（人物移动、跳起、静止动作）

用Unity2D制作一个人物，实现移动、跳起、人物静止和动起来时的动画：中（人物移动、跳起、静止动作）

上回我们学到创建一个地形和一个人物&#xff0c;今天我们实现一下人物实现移动和跳起&#xff0c;依次点击&#xff0c;我们准备创建一个C#文件 创建好我们点击进去&#xff0c;就会跳转到我们的Vision Studio&#xff0c;然后输入这些代码 using UnityEngine;public class M…
阅读更多...
java基础概念21-权限修饰符、代码块

java基础概念21-权限修饰符、代码块

一、权限修饰符 1-1、作用 权限修饰符&#xff0c;是用来控制一个成员能够被访问的范围的。 可以修饰&#xff1a;成员变量&#xff0c;方法&#xff0c;构造方法&#xff0c;内部类。 1-2、权限修饰符的分类 二、代码块 局部代码块构造代码块静态代码块 2-1、局部代码块 …
阅读更多...
IM即时通讯，稳定可靠的即时通讯服务-WorkPlus

IM即时通讯，稳定可靠的即时通讯服务-WorkPlus

在现代企业日常工作中&#xff0c;即时通讯已成为了一种不可或缺的沟通工具。为了满足企业对稳定可靠的即时通讯服务的需求&#xff0c;WorkPlus提供了一款优秀的IM即时通讯平台&#xff0c;以满足企业高效沟通和协作的要求。本文将深入探讨IM即时通讯服务的重要性以及WorkPlus…
阅读更多...
navigator.mediaDevices.getUserMedia检查用户的摄像头是否可用，虚拟摄像头问题

navigator.mediaDevices.getUserMedia检查用户的摄像头是否可用，虚拟摄像头问题

在Web开发中&#xff0c;检查用户的摄像头是否可用是一个常见的需求&#xff0c;尤其是在需要视频聊天或录制视频的应用程序中。navigator.mediaDevices.getUserMedia() API 提供了这一功能&#xff0c;它允许你请求访问用户的媒体设备&#xff0c;如摄像头和麦克风。虽然这个A…
阅读更多...
数据结构基础详解(C语言): 树与二叉树的应用_哈夫曼树与哈夫曼曼编码_并查集_二叉排序树_平衡二叉树

数据结构基础详解(C语言): 树与二叉树的应用_哈夫曼树与哈夫曼曼编码_并查集_二叉排序树_平衡二叉树

文章目录 树与二叉树的应用1.哈夫曼树与哈夫曼曼编码1.1 带权路径长度1.2 哈夫曼树1.2.1 哈夫曼树的构造1.3 哈夫曼编码 2.并查集2.1 并查集的三要素2.1.1 并查集的逻辑结构2.1.2 并查集的存储结构 2.2 并查集的优化2.2.1 初步优化&#xff08;并操作优化&#xff09;2.2.2 终极…
阅读更多...
【优选算法】---前缀和

【优选算法】---前缀和

前缀和 一、【模板】一维前缀和二、【模板】二维前缀和三、寻找数组的中心下标四、除自身以外数组的乘积五、和为K子数组六、和可被 K 整除的子数组七、连续数组八、矩阵区域和 一、【模板】一维前缀和 一维前缀和&#xff0c;链接 1、预处理出来一个前缀和数组 注意&#xf…
阅读更多...
消息中间件 --Kafka

消息中间件 --Kafka

一、 Kafka 1.kafka介绍 Kafka 是一个分布式流媒体平台,类似于消息队列或企业消息传递系统。 生产者发送消息&#xff0c;多个消费者只能有一个消费者接收到消息 生产者发送消息&#xff0c;多个消费者都可以接收到消息 producer&#xff1a;发布消息的对象称之为主题生产者…
阅读更多...
时序数据库 IoTDB 为什么选择 TPCx-IoT 基准测评？

时序数据库 IoTDB 为什么选择 TPCx-IoT 基准测评？

IoTDB 在 TPCx-IoT 榜单的 What 与 Why 解答&#xff01; 去年&#xff0c;我们发布了 IoTDB 多项性能表现位居国际数据库性能测试排行榜 benchANT&#xff08;Time Series: DevOps&#xff09;第一名的好消息。 刚刚落幕的数据库顶级会议 VLDB 上&#xff0c;我们又收获了一则…
阅读更多...
Python QT实现A-star寻路算法

Python QT实现A-star寻路算法

目录 1、界面使用方法 2、注意事项 3、补充说明 用Qt5搭建一个图形化测试寻路算法的测试环境。 1、界面使用方法 设定起点&#xff1a; 鼠标左键双击&#xff0c;设定红色的起点。左键双击设定起点&#xff0c;用红色标记。 设定终点&#xff1a; 鼠标右键双击&#xf…
阅读更多...
猴王采集——多多采集必备，关键词，类目整店采集，正在拼爆款截流采集

猴王采集——多多采集必备，关键词，类目整店采集，正在拼爆款截流采集

在日新月异的电商领域&#xff0c;数据就是商战的情报&#xff0c;而精准、高效的数据采集则成为商家们制胜的关键。今天&#xff0c;让我们一同探索一款颠覆传统、引领未来的数据采集工具 一、关键词类目整店采集&#xff1a; “猴王采集”凭借其强大的关键词搜索能力&#…
阅读更多...
什么是 TDengine?

什么是 TDengine?

TDengine 是一款专为物联网、工业互联网等场景设计并优化的大数据平台&#xff0c;其核心模块是高性能、集群开源、云原生、极简的时序数据库。它能安全高效地将大量设备、数据采集器每天产生的高达 TB 甚至 PB 级的数据进行汇聚、存储、分析和分发&#xff0c;对业务运行状态进…
阅读更多...
深入RabbitMQ世界：探索3种队列、4种交换机、7大工作模式及常见概念

深入RabbitMQ世界：探索3种队列、4种交换机、7大工作模式及常见概念

文章目录 文章导图RabbitMQ架构及相关概念四大核心概念名词解读 七大工作模式及四大交换机类型0、前置了解-默认交换机DirectExchange1、简单模式(Simple Queue)-默认DirectExchange2、 工作队列模式(Work Queues)-默认DirectExchange3、发布/订阅模式(Publish/Subscribe)-Fano…
阅读更多...
探索EasyCVR与AI技术深度融合：视频汇聚平台的新增长点

探索EasyCVR与AI技术深度融合：视频汇聚平台的新增长点

随着5G、AI、边缘计算、物联网&#xff08;IoT&#xff09;、云计算等技术的快速发展&#xff0c;万物互联已经从概念逐渐转变为现实&#xff0c;AIoT&#xff08;物联网人工智能&#xff09;的新时代正在加速到来。在这一背景下&#xff0c;视频技术作为信息传输和交互的重要手…
阅读更多...
简单实用的php全新实物商城系统

简单实用的php全新实物商城系统

免费开源电商系统,提供灵活的扩展特性、高度自动化与智能化、创新的管理模式和强大的自定义模块,让电商用户零成本拥有安全、高效、专业的移动商城。 代码是全新实物商城系统源码版。 代码下载
阅读更多...
c++进阶——unordered的封装

c++进阶——unordered的封装

嗨喽大家好呀&#xff0c;今天阿鑫给大家带来的是c进阶——unordered的封装&#xff0c;好久不见啦&#xff0c;下面让我们进入本节博客的内容吧&#xff01; c进阶——unordered的封装 unordered系列的基本架构unordered系列迭代器的封装unordered不支持修改keyoperator[]的…
阅读更多...
macos系统内置php文件列表 系统自带php卸载方法

macos系统内置php文件列表 系统自带php卸载方法

在macos系统中, 自带已经安装了php, 根据不同的macos版本php的版本号可能不同, 我们可以通过 which php 命令来查看mac自带的默认php安装路径, 不过注意这个只是php的执行文件路径. 系统自带php文件列表 一下就是macos默认安装的php文件列表. macos 10.15内置PHP文件列表配置…
阅读更多...
软件工程-图书管理系统的概要设计

软件工程-图书管理系统的概要设计

软件概要设计说明书 目录 软件概要设计说明书 一、引言 1.1 编写目的 1.2 背景 1.3 定义 1.3.1特定对象 1.3.2专业术语 1.4 参考资料 二、总体设计 2.1 需求规定 2.1.1信息要求 2.1.2功能要求 2.2 运行环境 2.3 基本概要设计和处理流程 2.4 体系结构设计 2.5 模…
阅读更多...
最新文章

Copyright @ 2022~2023