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.rhkb.cn/news/420512.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

H5咖啡品牌官网响应式HTML网站模板源码

源码名称&#xff1a;咖啡品牌官网响应式HTML网站模板源码 源码介绍&#xff1a;一款咖啡品牌官网响应式HTML网站模板源码&#xff0c;源码含有11个页面&#xff0c;可用于咖啡品牌官网。 需求环境&#xff1a;H5 下载地址&#xff1a; https://www.51888w.com/307.html

echarts 柱状图数据集结合堆叠图

效果图&#xff1a; 1.使用echarts的数据集&#xff0c;可以动态展示多组数据统计a,b,c,d…&#xff1b; 2.其中每个数据又使用堆叠图展示详细数据&#xff0c;比如a可以分成成功和失败的次数进行堆叠&#xff0c; 3.所有数据使用不同颜色进行区分&#xff0c;而每个数据的失败…

Makefile学习总结

Makefile学习总结 目录 Makefile学习总结1. Makefile介绍2. Makefile规则3. Makefile文件里的赋值方法4. Makefile常用函数4.1 字符串替换和分析函数4.2 文件名函数4.3 其他函数 5. Makefile使用示例6、多级目录通用Makefile Demo6.1 一般通用Makefile的设计思想6.2 Demo分析 参…

可筛选的课程表设计excel表格@在线写作共享表格课程表设计模板参考

文章目录 abstract表格任务1. 时间段与课次安排2. 课程种类多样3. 教师与教室安排4. 课程颜色编码5. 课表标注 参考方案:样式预览全表添加不影响筛选列的跨列显示内容方案1方案2(pass) 针对指定老师筛选并生成课表&#x1f47a;在线表格链接(wps)要点表格说明&#x1f47a;列交…

Pow(x, n)

优质博文&#xff1a;IT-BLOG-CN 题目 实现pow(x, n) &#xff0c;即计算x的整数n次幂函数&#xff08;即&#xff0c;xn &#xff09;。 示例 1&#xff1a; 输入&#xff1a;x 2.00000, n 10 输出&#xff1a;1024.00000 示例 2&#xff1a; 输入&#xff1a;x 2.100…

【spring】IDEA 新建一个spring boot 项目

参考新建项目-sprintboot 选择版本、依赖,我选了一堆 maven会重新下载一次么?

系统工程建模MBSE

################################# ############# 片段一 ############## ################################# 下图采用“V”模式显示了集成的基于模型的系统/嵌入式软件开发流程Harmony。左侧描述了自顶向下的设计流程,而右侧显示了自底而上的从单元测试到最终系统验收测试…

vue3 项目中使用git

一.vue项目创建 二.创建本地仓库并和远程仓库进行绑定 在vue3-project-git 项目文件夹下 初始化一个新的Git仓库&#xff0c;可以看到初始化成功之后就会出现一个.git文件&#xff0c;该文件包含所有必要的 Git 配置和版本控制信息。 创建远程仓库: 打开gitee ,点击右上角 ‘…

低代码用户中心:构建高效平台的新时代

一、低代码开发平台概述 低代码开发平台是一种通过图形化界面和预构建组件来简化应用开发的工具。开发者可以通过拖放组件和配置参数的方式&#xff0c;快速创建和修改应用程序&#xff0c;显著降低了编写代码的复杂度和时间成本。这种平台非常适合用来快速构建和部署企业内部…

Sapiens:人类视觉模型的基础

文章目录 摘要1、引言2、相关工作3、方法3.1、Humans-300M 数据集3.2、预训练3.3、二维姿态估计3.4、身体部位分割3.5、深度估计3.6、表面法线估计 4、实验4.1、实现细节4.2、二维姿态估计4.3、身体部位分割4.4、深度估计4.5、表面法线估计4.6、讨论 5、结论 摘要 我们介绍了 …

无线麦克风什么品牌好?麦克风领夹式的哪个牌子最好?麦克风推荐

近年来&#xff0c;无线领夹麦克风成为了网络主播、在线教育老师的新宠。它小巧便携&#xff0c;能够提供清晰的语音录制&#xff0c;完美匹配快节奏的工作与学习需求。但市场上的产品质量参差不齐&#xff0c;一些低价产品不仅音质差&#xff0c;甚至存在电池寿命短、兼容性差…

程序员的数字化工具有哪些?你用了多少?是否吓到你?

一、程序员常用的数字化工具有哪些&#xff1f; 程序员在日常工作中的数字化工具非常多样&#xff0c;涵盖了编码、测试、部署、协作等多个方面。以下是一些常见的工具&#xff1a; 集成开发环境&#xff08;IDE&#xff09;&#xff1a; IntelliJ IDEAEclipseVisual Studio Co…

(9月10日)最新植物大战僵尸杂交版【v2.4.0版本已更新】

植物大战僵尸杂交版下载链接【v2.4.0版本已更新】 新增了多种植物和僵尸&#xff0c;例如“海豌豆”、“豌豆海草”、“海洋星”等&#xff0c;以及新的僵尸类型&#xff0c;如“僵尸坚果巨人”和“僵尸豌豆小鬼”。 引入了新的游戏模式&#xff0c;例如“超级杂交地图”和“乒…

SQL进阶技巧:如何利用SQL解决趣味赛马问题?| 非等值关联匹配问题

目录 0 问题描述 1 数据准备 2 问题分析 方法一:先分后合思想 方法2:非等值关联匹配 3 小结 0 问题描述 有一张赛马记录表,如下所示: create table RacingResults ( trace_id char(3) not null,race_date date not null, race_nbr int not null,win_name char(30) n…

1万3医学考研题库医学题库ACCESS\EXCEL数据库

今天这个题库按知识点分章节模块智能练习&#xff0c;覆盖书本上所有知识点以及考点&#xff0c;在真#题的解析里边也有详细的展示&#xff1b;另外&#xff0c;这份数据库与《4820道西#医综合真题西#医真#题ACCESS数据库》、《4170条中#医综合真#题中医真#题ACCESS\EXCEL数据库…

去除恢复出厂设置中UI文字显示

文章目录 需求场景 一、代码跟踪与分析在线文字搜索RK平台本地源码搜索实际测试验证代码推理 二、实现方案三、延伸知识四、知识总结 需求 需求&#xff1a;去除恢复出厂设置中UI文字显示 场景 Android 相关产品各种方向旋转、强制横竖屏等需求&#xff0c;导致在恢复出厂设…

Bootstrap简介

Bootstrap 一.Bootstrap简介 什么是Bootstrap? Bootstrap 是一个用于快速开发 Web 应用程序和网站的前端框架。Bootstrap 是基于 HTML、CSS、JAVASCRIPT 的。 为什么使用Bootstrap? 快速开发&#xff1a;Bootstrap 提供了一套预设的CSS样式和JavaScript组件&#xff0c;如…

JVM系列(七) -对象的内存分配流程

一、摘要 在之前的文章中,我们介绍了类加载的过程、JVM 内存布局和对象的创建过程相关的知识。 本篇综合之前的知识,重点介绍一下对象的内存分配流程。 二、对象的内存分配原则 在之前的 JVM 内存结构布局的文章中,我们介绍到了 Java 堆的内存布局,由 年轻代 (Young Ge…

LLM时代的transformer参数量、计算量、激活值的分析

导读&#xff1a;本文可以看作是对分析transformer模型的参数量、计算量、中间激活、KV cache的详细说明 定性分析 GPU上都存了哪些东西 首先我们来从全局整体的角度看一看&#xff0c;在训练阶段GPU显存上都有哪些内容&#xff1a; Model States&#xff1a;模型训练过程中…

标签的ref属性

标签的ref属性 当我们想要获取一个标签对应的 DOM 元素的时候在 JavaScript 中&#xff0c;我们通过 document.getElementById() 来借助类选择器的写法获取&#xff0c;但是在 Vue 中&#xff0c;我们的 DOM 元素是挂载在同一个网页上的&#xff0c;这些名称难免会重复&#x…