AtCoder Beginner Contest 353
A
题意:检查是否有比第一个数大的数
#include<bits/stdc++.h>using namespace std;int main()
{int n;cin>>n;int a;cin>>a;int f=0;for(int i=2;i<=n;i++){int k;cin>>k;if(k>a){cout<<i<<endl;f=1;break;}}if(f==0){cout<<"-1"<<endl;}return 0;}
B
题意:有n组人,还有一个k大小的座舱,题目保证每组人都小于k,计算要做多少个座舱
模拟,依次让每组人往里边坐,如果发现一组人不能完全坐满,则答案加1,换一个空的座舱
#include<bits/stdc++.h>using namespace std;
int n;
int a[110];
int main()
{int k;int res=0;cin>>n>>k;for(int i=0;i<n;i++) cin>>a[i];int i=0;int x=k;while(i<n){x-=a[i];i++;while(x>=a[i]&&i<n){x-=a[i];i++;}res++;x=k;}cout<<res<<endl;return 0;}
C
思路:可以推出每个元素都会被加n-1次,那么可以把他们每个元素都乘以n-1,
因为当两个数相加大于1e8时,会取余数,就是相当于减去了一个1e8,所以还要计算减去1e8的个数
先排序,然后二分找每个数和其他数相加大于等于1e8的个数
如果找到的数,是在当前数的位置的前边,那么x=i+1(当前的位置+1),这样做是为了避免重复减去1e8
如果一个目标数被查找到的位置,是当前位置的前边,那么之前在更新被查找到的位置的数时,已经减去了一个1e8了,所以此时不能再减去1e8,同理,被查找到的位置 是当前位置,那么也要加1,这两个数不能相加
#include<bits/stdc++.h>using namespace std;
const int N = 3e5 + 10,mod=1e8;
#define int long long
int n;
int a[N];
int find(int x)
{int l=0,r=n+1;while(l<r){int mid=l+r>>1;if(a[mid]>=x) r=mid;else l=mid+1;}return r;}
signed main()
{cin>>n;for(int i=1;i<=n;i++) cin>>a[i];int res=0;sort(a+1,a+n+1);int cnt=0;for(int i=1;i<=n;i++){res+=(n-1)*a[i];int x=find(mod-a[i]);if(x<=i)//避免重复减去mod x=i+1;if(x>n) continue;res=res-(n-x+1)*mod;}cout<<res<<endl;return 0;}
D
模拟
以第i个数为中心点
res加上(i-1)*a[i]
i后边的数,依次加上10^(数的位数),此处可以做个优化,先记录每个数的位数,存进map中,
在更新第i个数时,只需遍历1到10(因为位数是1到10)
#include<bits/stdc++.h>using namespace std;
const int N = 2e5 + 10,mod=998244353;
#define int long long
int n;
int a[N];
int q[15]={0,10,100,1000,10000,100000,1000000,10000000,100000000,1000000000,10000000000};
map<int,int> mp;
int ck(int x)
{int cnt=0;while(x){cnt++;x/=10;}return cnt;
}
signed main()
{cin>>n;for(int i=1;i<=n;i++) cin>>a[i];for(int i=1;i<=n;i++)mp[ck(a[i])]++;int res=0;for(int i=1;i<=n;i++){res=(res+(i-1)*a[i]%mod)%mod;mp[ck(a[i])]--;for(int j=1;j<=10;j++){res=(res+(a[i]*mp[j]%mod)*(q[j]%mod)%mod)%mod;}}cout<<res<<endl;return 0;}
E
依次计算最长公共前缀子串,记录每个子串出现的次数,每个字串贡献的价值为,cnt[i]*(cnt[i]-1)/2
3
ab ab ab
可以看出a字串出现了3次,ab字串出现了3次,总贡献值6
当时在想计算ab字串时,会不会重复?因为前边已经计算过a字串了
ab ab ac
此时就可以看出,必须得一个一个前缀字串考虑,因为第一个a字串,可以和第二个,第三个匹配,第二个和第三个匹配,产生3的贡献值,但ab字串只能和第二个匹配产生2的贡献值,因为题目要的是每次匹配的最长公共前缀字串的长度
突然想到,是不是也可以看为,ab字串的长度是2,a的字串在前边已经计算过了,而ab字串只是计算以b结尾的ab字串的数量可以产生的贡献值
再举一个例子 a ab abc abcd
字典树可以快速存储和查询字符串
#include<bits/stdc++.h>using namespace std;
const int N = 3e5 + 10,mod=998244353;
#define int long longint n;
int a[N];
map<string,int> mp;
int son[N][26],cnt[N],idx;
void insert(string s)
{int p=0;//p代表的是p表示第几个结点for(int i=0;i<s.size();i++){int x=s[i]-'a';if(!son[p][x]) son[p][x]=++idx;cnt[p]++;//每经历过一个字串就标记一下p=son[p][x];//将p指向他的子节点}cnt[p]++;
}
signed main()
{string str;cin>>n;for(int i=1;i<=n;i++) {cin>>str;insert(str);}int res=0;for(int i=1;i<=idx;i++){res+=(cnt[i]*(cnt[i]-1)/2);}cout<<res<<endl;return 0;}
相关文章:
AtCoder Beginner Contest 353
A 题意:检查是否有比第一个数大的数 #include<bits/stdc.h>using namespace std;int main() {int n;cin>>n;int a;cin>>a;int f0;for(int i2;i<n;i){int k;cin>>k;if(k>a){cout<<i<<endl;f1;break;}}if(f0){cout<&l…...
深度解读《深度探索C++对象模型》之虚继承的实现分析和效率评测(一)
目录 前言 具有虚基类的对象的构造过程 通过子类的对象存取虚基类成员的实现分析 接下来我将持续更新“深度解读《深度探索C对象模型》”系列,敬请期待,欢迎左下角点击关注!也可以关注公众号:iShare爱分享,或文章末…...
计算机Java项目|Springboot房产销售系统
作者主页:编程指南针 作者简介:Java领域优质创作者、CSDN博客专家 、CSDN内容合伙人、掘金特邀作者、阿里云博客专家、51CTO特邀作者、多年架构师设计经验、腾讯课堂常驻讲师 主要内容:Java项目、Python项目、前端项目、人工智能与大数据、简…...
学习3D几何和特征一致的高斯溅射目标去除
earning 3D Geometry and Feature Consistent Gaussian Splatting for Object Removal 学习3D几何和特征一致的高斯溅射目标去除 Yuxin Wang 王玉欣 HKUST &Qianyi Wu Monash University &Guofeng Zhang Zhejiang University &Dan Xu HKUST 香港科技大学&吴倩…...
PHP 使用常量实现枚举类
PHP 使用常量实现枚举类 <?php abstract class Enum {private static $constCacheArray NULL;private static function getConstants() {if (self::$constCacheArray NULL) {self::$constCacheArray [];}$calledClass get_called_class();if (!array_key_exists($call…...
Linux操作系统基础题库
一. 单选题(共2题,40分) 1. (单选题)Linux操作系统自诞生至今,有数十万的程序开发人员参与到了它的开发与完善中,如今Linux已发展成为是一个成熟、稳定的操作系统。从以下选项中选出关于Linux特点描述完全正确的一项。…...
Java抽象类:为何它是你代码架构的基石?
目录 1、抽象类的概念 2、抽象类语法 3、抽象类特性 4、抽象类的作用 5、 完结散花 个人主页:秋风起,再归来~ 文章专栏:javaSE的修炼之路 个人格言:悟已往之不谏,知来者犹可追 克…...
Flutter 中的 ToggleButtons 小部件:全面指南
Flutter 中的 ToggleButtons 小部件:全面指南 在 Flutter 中,ToggleButtons 是一种允许用户在一组选项中进行切换选择的控件。它通常用于展示一组相关选项,让用户可以快速切换选择。ToggleButtons 是一种水平排列的按钮集合,其中…...
【MYSQL】一颗B+树可以保存多少条数据
引言 事万物都有自己的单元体系,若干个小单体组成一个个大的个体。就像拼乐高一样,可以自由组合。所以说,如果能熟悉最小单元,就意味着我们抓住了事物的本事,再复杂的问题也会迎刃而解。 存储单元 存储器范围比较大…...
ssm125四六级报名与成绩查询系统+jsp
四六级报名与成绩查询系统的设计与实现 摘 要 互联网发展至今,无论是其理论还是技术都已经成熟,而且它广泛参与在社会中的方方面面。它让信息都可以通过网络传播,搭配信息管理工具可以很好地为人们提供服务。针对四六级报名信息管理混乱&am…...
【Unity从零开始学习制作手机游戏】第01节:控制3D胶囊体运动
1. 新建Project L01 使用3D Mobile模板。 2. 建立一个平面,用来承载物体 3. 导入Unity库内的胶囊体 下载 StandardAssets https://download.unitychina.cn/download_unity/e80cc3114ac1/WindowsStandardAssetsInstaller/UnityStandardAssetsSetup-5.6.7f1.exe …...
内容安全(DPI和DFI解析)
内容安全前言: 防火墙的本质其实就是包过滤,我们通常所说的安全设备(如:IPS、IDS、AV、WAF)的检测重心是应用层。下一代防火墙基于传统防火墙的拓展能力,就是可以将以上的安全设备模块集成在一起࿰…...
2024数维杯数学建模A题B题C题思路+模型+代码(开赛后第一时间更新)
2024数维杯数学建模A题B题C题思路模型代码(开赛后第一时间更新) https://mbd.pub/o/bread/ZpWakpdq https://mbd.pub/o/bread/ZpWakpdq 2024年第九届数维杯大学生数学建模挑战赛参赛规则 竞赛要求及论文提交方式; ①本次参赛作品统一在线提交到竞赛…...
SpringSecurity多表,多端账户登录
本文章对应视频SpringSecurity6多端账号登录,可无限扩展教程,记得三连哦,这对我很重要呢! 温馨提示:视频与文章相辅相成,结合学习效果更强哦!更多视频教程可移步B站【石添的编程哲学】 SpringSe…...
绝地求生PUBG新老艾伦格有什么差别 老艾伦格什么时候回归
复古风格的艾伦格原始地图携带着那些标志性的记忆符号华丽回归,邀请您沉浸于往昔的每一处细节探索中。我们不仅还原了游戏诞生的起点,还在其中巧妙融入现代游戏元素,构筑一座连接昔日与今朝的桥梁,完美融合了经典与创新的游戏体验…...
Windows下安装Node.js、npm和electronic,并运行一个Hello, World!脚本程序
20240510 By wdhuag 目录 简介: 参考: 安装Node.js 安装npm 配置npm: 修改包存放目录和缓存目录 切换镜像源 使用 nrm 切换镜像源 安装Electron 运行一个Hello, World!脚本程序 安装Yarn JavaScript 指南 简介: Nod…...
【精品案例】化工炼化企业信息化建设解决方案(74页PPT)
一、资料介绍 化工炼化企业信息化建设解决方案是一份详尽且全面的指导文件,旨在助力化工炼化企业实现信息化、智能化和数字化转型。本资料以74页的PPT形式呈现,围绕智能化工程施工方案、化工炼化企业信息化以及化工行业数字化转型等关键词,为…...
【Unity Animation 2D】Unity Animation 2D骨骼绑定与动画制作
一、图片格式为png格式,并且角色各部分分离 图片参数设置 需要将Sprite Mode设置为Single,否则图片不能作为一个整体 1、创建骨骼 1.1 旋转Create Bone,点击鼠标左键确定骨骼位置,移动鼠标再次点击鼠标左键确定骨骼,…...
工器具管理(基于若依)
文章目录 前言一、工器具管理项目总览 二、入库功能1. 前端1.1 界面展示1.2 具体操作实现1.3 js文件 2. 后端2.1 工器具信息回显2.2 工器具入库 三、领用功能1. 前端1.1 界面展示1.2 具体实现操作1.3 js文件 2. 后端2.1 工器具信息回显2.2 工器具领用 遇到的问题1. 同一页面展示…...
UE4_照亮环境_光束light beam
学习笔记,不喜勿喷,侵权立删!祝愿生活越来越好! 光束:模拟大气中散射的光线。利用定向光源模拟真实曙暮光效果或大气散射的阴影,即可生成 光束 。这些光线为场景添加深度和真实度。 一:一些参数…...
国防科技大学计算机基础课程笔记02信息编码
1.机内码和国标码 国标码就是我们非常熟悉的这个GB2312,但是因为都是16进制,因此这个了16进制的数据既可以翻译成为这个机器码,也可以翻译成为这个国标码,所以这个时候很容易会出现这个歧义的情况; 因此,我们的这个国…...
【机器视觉】单目测距——运动结构恢复
ps:图是随便找的,为了凑个封面 前言 在前面对光流法进行进一步改进,希望将2D光流推广至3D场景流时,发现2D转3D过程中存在尺度歧义问题,需要补全摄像头拍摄图像中缺失的深度信息,否则解空间不收敛…...
linux arm系统烧录
1、打开瑞芯微程序 2、按住linux arm 的 recover按键 插入电源 3、当瑞芯微检测到有设备 4、松开recover按键 5、选择升级固件 6、点击固件选择本地刷机的linux arm 镜像 7、点击升级 (忘了有没有这步了 估计有) 刷机程序 和 镜像 就不提供了。要刷的时…...
04-初识css
一、css样式引入 1.1.内部样式 <div style"width: 100px;"></div>1.2.外部样式 1.2.1.外部样式1 <style>.aa {width: 100px;} </style> <div class"aa"></div>1.2.2.外部样式2 <!-- rel内表面引入的是style样…...
css3笔记 (1) 自用
outline: none 用于移除元素获得焦点时默认的轮廓线 broder:0 用于移除边框 font-size:0 用于设置字体不显示 list-style: none 消除<li> 标签默认样式 margin: xx auto 版心居中 width:100% 通栏 vertical-align 作用于行内元素 / 表格单元格ÿ…...
Java多线程实现之Thread类深度解析
Java多线程实现之Thread类深度解析 一、多线程基础概念1.1 什么是线程1.2 多线程的优势1.3 Java多线程模型 二、Thread类的基本结构与构造函数2.1 Thread类的继承关系2.2 构造函数 三、创建和启动线程3.1 继承Thread类创建线程3.2 实现Runnable接口创建线程 四、Thread类的核心…...
Device Mapper 机制
Device Mapper 机制详解 Device Mapper(简称 DM)是 Linux 内核中的一套通用块设备映射框架,为 LVM、加密磁盘、RAID 等提供底层支持。本文将详细介绍 Device Mapper 的原理、实现、内核配置、常用工具、操作测试流程,并配以详细的…...
Pinocchio 库详解及其在足式机器人上的应用
Pinocchio 库详解及其在足式机器人上的应用 Pinocchio (Pinocchio is not only a nose) 是一个开源的 C 库,专门用于快速计算机器人模型的正向运动学、逆向运动学、雅可比矩阵、动力学和动力学导数。它主要关注效率和准确性,并提供了一个通用的框架&…...
基于PHP的连锁酒店管理系统
有需要请加文章底部Q哦 可远程调试 基于PHP的连锁酒店管理系统 一 介绍 连锁酒店管理系统基于原生PHP开发,数据库mysql,前端bootstrap。系统角色分为用户和管理员。 技术栈 phpmysqlbootstrapphpstudyvscode 二 功能 用户 1 注册/登录/注销 2 个人中…...
springboot 日志类切面,接口成功记录日志,失败不记录
springboot 日志类切面,接口成功记录日志,失败不记录 自定义一个注解方法 import java.lang.annotation.ElementType; import java.lang.annotation.Retention; import java.lang.annotation.RetentionPolicy; import java.lang.annotation.Target;/***…...
