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]重复不算)的平均数是什么
思路:
假设四个元素
那么答案就是
等价于
用一个后缀和维护形如的东西这道题就轻松解决了,只需要注意一下取模和乘法逆元的问题就行了
#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;
}
相关文章:
Codeforces Round 970 (Div. 3)(ABCDEF)
Codeforces Round 970 (Div. 3) A:Sakurakos Exams 签到 题意:给定1,2的数量,判断是否能用加减符号使得这些1,2计算出0 void solve() {cin>>n>>m;if(n%2)cout<<"NO\n";else{if(m%20||n)cout<<"YES\n";else cout<<"…...

springboot基于ssm+Jsp的人才招聘网站系统的设计与实现 jw2cs
目录 前言详细视频演示后端技术栈具体实现截图开发核心技术:开发工具核心代码部分展示系统设计操作可行性可行性论证试验方案源码获取 前言 👇🏻 博主介绍:👇🏻 全网粉丝50W,博客专家、CSDN特邀作者、CSDN…...

高质量共建“一带一路”!苏州金龙助力非洲交通驶向共同繁荣之旅
9月6日,中非合作论坛在北京落下帷幕。此次论坛,“高质量共建‘一带一路’”成为重要议题。截止至目前,苏州金龙海格客车已向阿尔及利亚、埃塞俄比亚、南非等所有参与共建“一带一路”的非洲国家累计出口客车14000台。从产品销售,到…...

嵌入式初学-C语言-数据结构--四
栈 1. 基本概念 栈是一种逻辑结构,是特殊的线性表。特殊在: 只能在固定的一端操作 只要满足上述条件,那么这种特殊的线性表就会呈现一种“后进先出”的逻辑,这种逻辑就被称为栈。栈 在生活中到处可见,比如堆叠的盘子…...
【HarmonyOS 4】应用性能优化
1. ArkTs 高性能编程 1.1 ArkTs 高性能编程规则 1.1.1 限制一些 TypeScript 的特性,比如需要不支持属性的动态变更、变量或参数需要明确的类型声明和返回值声明等。1.1.2 禁用 ts-ignore、ts-expect-error 等屏蔽编译校验的命令。1.1.3 开启 TypeScript 的严格模式…...

MySQL——表操作
目录 一、创建表 二、查看表 2.1 查看表中某成员的数据 2.2 查看整个表中的表成员 2.3 查看创建表时的句柄 三、修改表 alter 3.1 重命名 rename 3.2 新增一列 add 3.3 更改列属性 modify 3.4 更改列名称 change 3.5 删除某列 上一篇博客介绍了库的操作,…...
阅读笔记--Guiding Attention in End-to-End Driving Models(二)
端到端驾驶的注意力学习(Attention Learning for End-to-End Driving)关键内容学习 3.1 问题设置(Problem Setup) 模仿学习(Imitation Learning, IL):介绍了模仿学习的概念,即通过…...
Linux: network: TCP: errno: EWOULDBLOCK
https://mzhan017.blog.csdn.net/article/details/108010013 这个errno的意思: 如果是send接口函数返回的错误,代表tcp socket的sending buffer满了,让应用程序等上一段时间重试send。 所以,这个产生的原因就不固定了: 可能是当前系统太忙,导致系统发包慢,buffer累积; 可…...
闲话“设计模式”
Q1、请详细介绍 软件架构设计模式(智能化),应用程序设计模式(自动化),编程语言设计模式(人性化)(后面括号中 是我 希望 其 具有的特点) 的概念,有…...

Sentence-BERT实现文本匹配【CoSENT损失】
引言 还是基于Sentence-BERT架构,或者说Bi-Encoder架构,但是本文使用的是苏神提出的CoSENT损失函数1。 点击来都是缘分,之前过时的方法可以不细看,别的文章可以不收藏,现在是最流行的方法,这篇文章建议收藏…...

业余考什么证书比较实用?
在业余时间里,获得一些有用的证书不仅能提升你的专业素养,还能增强你在职场上的竞争力。 特别是职业技能证书和行业认证证书,这两者受到了广大职场人士的高度关注。 一、业余时间考取的实用证书 行业认证证书主要针对特定行业或职业&#…...

16款facebook辅助工具,总有一款适合你!
Hey小伙伴们~👋 是不是想利用FB大展拳脚,却苦于不知道如何开始?别急,今天就给你们安利16个超实用的FB营销工具,涵盖了内容创建和发布的应用程序,以及数据追踪分析、商品销售等多个方面让你轻松get海外获客新…...
给网站发外链的好处,你了解多少?
在当今这个信息爆炸的互联网时代,网站优化和推广成为了每一个网站主不可忽视的重要环节。其中,给网站发外链,即在其他网站上设置指向自己网站的链接,是一种高效且被广泛采用的策略。那么,给网站发外链究竟能带来哪些好…...
安卓链接正常显示,ios#符被转义%23导致链接访问404
原因分析: url中含有特殊字符 中文未编码 都有可能导致URL转换失败,所以需要对url编码处理 如下: guard let allowUrl webUrl.addingPercentEncoding(withAllowedCharacters: .urlQueryAllowed) else {return} 后面发现当url中有#号时&a…...

excel分列
Excel中有这么几列,希望将每一列内容再分出3列: 可以通过以下步骤在 Excel 表格中将 B 到 F 列的内容拆分为每列的 3 列,分别为 pred_label、pred_score 和 pred_class: 确定数据结构:假设 B 列到 F 列中的内容都是按类…...

STM32 HAL DMA 中断碰到的问题
流程 串口收数据—>dma搬运到变量—>空闲中断----->接收完成 配置 dma中断全部去掉 串口中断开启 freertos中断全部去掉 时钟配置 代码 开启中断 // DMA 空闲检查 void receives_uaru_7(void) {RXU7 0;//清除中断标志HAL_UARTEx_ReceiveToIdle_DMA(&hua…...
让树莓派智能语音助手实现定时提醒功能
最初的时候是想直接在rasa 的chatbot上实现,因为rasa本身是带有remindschedule模块的。不过经过一番折腾后,忽然发现,chatbot上实现的定时,语音助手不一定会有响应。因为,我目前语音助手的代码设置了长时间无应答会结束…...

AIoTedge边缘计算+边缘物联网平台
在数字化转型的浪潮中,AIoTedge边缘计算平台以其边云协同的架构和强大的分布式AIoT处理能力,正成为推动智能技术发展的关键力量。AIoTedge通过在数据源附近处理信息,实现低延迟、快速响应,增强了应用的实时性。同时,它…...
Java使用拷贝asset文件,解密,并用DexclassLoader加载执行
//asset中加密的apk文件重命名为index.html,拷贝到私有目录 //解密 //加载,执行apk中的方法 public static void handleByJava(Context context){File copyedFile new File(context.getFilesDir().getAbsolutePath() "/" "main.html");FileUtil.copyAss…...

【AcWing】861. 二分图的最大匹配(匈牙利算法)
匈牙利算法,他可以在比较快的时间复杂度之内告诉我们左边和右边成功匹配的最大数是多少 匹配指的是边的数量,成功的匹配指的是两个未被使用的点之间存在一条边(就不存在两条边共用了一个点的)。 匈牙利算法可以返回成功匹配的最大匹配数是多少。 #incl…...

Zustand 状态管理库:极简而强大的解决方案
Zustand 是一个轻量级、快速和可扩展的状态管理库,特别适合 React 应用。它以简洁的 API 和高效的性能解决了 Redux 等状态管理方案中的繁琐问题。 核心优势对比 基本使用指南 1. 创建 Store // store.js import create from zustandconst useStore create((set)…...
从零实现富文本编辑器#5-编辑器选区模型的状态结构表达
先前我们总结了浏览器选区模型的交互策略,并且实现了基本的选区操作,还调研了自绘选区的实现。那么相对的,我们还需要设计编辑器的选区表达,也可以称为模型选区。编辑器中应用变更时的操作范围,就是以模型选区为基准来…...

【大模型RAG】Docker 一键部署 Milvus 完整攻略
本文概要 Milvus 2.5 Stand-alone 版可通过 Docker 在几分钟内完成安装;只需暴露 19530(gRPC)与 9091(HTTP/WebUI)两个端口,即可让本地电脑通过 PyMilvus 或浏览器访问远程 Linux 服务器上的 Milvus。下面…...
Element Plus 表单(el-form)中关于正整数输入的校验规则
目录 1 单个正整数输入1.1 模板1.2 校验规则 2 两个正整数输入(联动)2.1 模板2.2 校验规则2.3 CSS 1 单个正整数输入 1.1 模板 <el-formref"formRef":model"formData":rules"formRules"label-width"150px"…...

云原生玩法三问:构建自定义开发环境
云原生玩法三问:构建自定义开发环境 引言 临时运维一个古董项目,无文档,无环境,无交接人,俗称三无。 运行设备的环境老,本地环境版本高,ssh不过去。正好最近对 腾讯出品的云原生 cnb 感兴趣&…...
Linux离线(zip方式)安装docker
目录 基础信息操作系统信息docker信息 安装实例安装步骤示例 遇到的问题问题1:修改默认工作路径启动失败问题2 找不到对应组 基础信息 操作系统信息 OS版本:CentOS 7 64位 内核版本:3.10.0 相关命令: uname -rcat /etc/os-rele…...
Go 并发编程基础:通道(Channel)的使用
在 Go 中,Channel 是 Goroutine 之间通信的核心机制。它提供了一个线程安全的通信方式,用于在多个 Goroutine 之间传递数据,从而实现高效的并发编程。 本章将介绍 Channel 的基本概念、用法、缓冲、关闭机制以及 select 的使用。 一、Channel…...

AI+无人机如何守护濒危物种?YOLOv8实现95%精准识别
【导读】 野生动物监测在理解和保护生态系统中发挥着至关重要的作用。然而,传统的野生动物观察方法往往耗时耗力、成本高昂且范围有限。无人机的出现为野生动物监测提供了有前景的替代方案,能够实现大范围覆盖并远程采集数据。尽管具备这些优势…...

push [特殊字符] present
push 🆚 present 前言present和dismiss特点代码演示 push和pop特点代码演示 前言 在 iOS 开发中,push 和 present 是两种不同的视图控制器切换方式,它们有着显著的区别。 present和dismiss 特点 在当前控制器上方新建视图层级需要手动调用…...

代码规范和架构【立芯理论一】(2025.06.08)
1、代码规范的目标 代码简洁精炼、美观,可持续性好高效率高复用,可移植性好高内聚,低耦合没有冗余规范性,代码有规可循,可以看出自己当时的思考过程特殊排版,特殊语法,特殊指令,必须…...