美团0316春招笔试题
下面是美团2024-03-16笔试真题,进行了VP,由于未参与评测,故不保证正确性,仅供参考。
第一题 小美点外卖
求和然后减去满减和红包即可。
#include <bits/stdc++.h>
using namespace std;
using LL = long long ;
int n, t, x, y;
LL ans;int main() {scanf("%d", &n);while (n -- ) {scanf("%d", &t);ans += t;}scanf("%d%d", &x, &y);printf("%lld\n", ans - x - y);
}
第二题 小美的合法单词
考虑三种情况分别需要的操作次数,取最小值即可。
先扫描字符串s,并用变量big和small分别统计字符串s中大写字母、小写字母的个数。
然后还要处理第一个字符是大写的情况:
首先初始化变量t=s.size(),当第一个字符是大写字母时,执行t = t - 1 - small。减去1是因为去掉第一个大写字母,然后再减去small,这样得到的就是后面剩余的大写字符个数。
为什么是t-1-small而不是t-1-big呢?举个例子:s=“AaaBbCD”,此时big=4,small=3。
- 若执行t-1-big,则此时t的结果就是2,那么答案为min{big, small, t} = 2,但显然答案应该是3(将后面的B,C,D修改为小写)。
- 若执行t-1-small,则此时t的结果就是3,那么答案为min{big, small, t} = 3,这显然就是正确答案3(将后面的B,C,D修改为小写)。
说白了就是由于题目要求第一个字母大写,后面所有字母都是小写。t-1-small就是将后面统计除了首位这个大写字母外剩余部分的大写字母个数,而我们需要将这些大写字母个数就是我们需要修改为小写字母所需要的操作次数。
#include <bits/stdc++.h>
using namespace std;int main() {string s;cin >> s;int big = 0, small = 0, t = s.size();for (auto& c : s) {if (c >= 'A' && c <= 'Z') ++ big;else if (c >= 'a' && c <= 'z') ++ small;}if (s[0] >= 'A' && s[0] <= 'Z') t = t - 1 - small;printf("%d\n", min({small, big, t}));
}
第三题 翻倍元素
统计每个元素最后翻倍的次数即可。
如下表:
数组元素a[] | 翻倍次数times[] | 最终结果 |
---|---|---|
a[1]=1 | 1 | 1 × 2 1 1\times 2^1 1×21 |
a[2]=2 | 1 | 2 × 2 1 2\times 2^1 2×21 |
a[3]=3 | 2 | 3 × 2 2 3\times 2^2 3×22 |
a[4]=4 | 2 | 4 × 2 2 4\times 2^2 4×22 |
因此最终结果为2、4、12、16,答案即为2+4+12+16=34。
对于快速求 a b a^b ab显然可以使用快速幂。
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10, MOD = 1e9 + 7;
int a[N], times[N], n, m;int qmi(int a, int b) {int ans = 1;while (b) {if (b & 1) ans = ans * a % MOD;a = a * a % MOD;b >>= 1;}return ans % MOD;
}int main() {scanf("%d%d", &n, &m);for (int i = 1; i <= n; ++ i) {scanf("%d", &a[i]);times[i] = m;}for (int i = 1; i <= m; ++ i) {int x;scanf("%d", &x);-- times[x];}int ans = 0;for (int i = 1; i <= n; ++ i) {ans = (ans + a[i] * qmi(2, times[i]) % MOD) % MOD;}printf("%d\n", ans);
}
第四题 小美的众数
首先需要观察到元素 a i a_i ai只有1和2这两种取值。由于它的数值只有1和2,所以记录一个前缀和。如果说当前值是1就前缀和加1,如果说当前值是2,就前缀和减1。即我们定义数组 s i s_i si表示区间 [ 1 , i ] [1,i] [1,i]中元素1和元素2的被标记为+1和-1之后的前缀和。
对于一个前缀和 s i s_i si来说,它前面有多少个 s j s_j sj的值比 s i s_i si小,就说明,1的个数会大于等于2的个数,那么这些数量的区间,众数必然是元素1。 i i i减去这些区间的数量,也就是剩下的区间数量,众数就是2了。
对于如何求一个前缀和 s i s_i si来说,它前面有多少个 s j s_j sj的值比 s i s_i si小,这可以用树状数组来求解。
为什么要加偏移量OFFSET = n+1
呢?
这是因为数组s[]
取值有可能是负数(这是由于将元素1和元素2的被标记为+1和-1导致的),最坏情况下s[]
取值可能是 − n -n −n。但是我们知道树状数组下标是从1开始的,不能是<1的,故我们加上偏移量n+1,使得保证树状数组的下标是正确从1开始。
如何理解query(s[i] + OFFSET) + (i - query(s[i] + OFFSET)) * 2
这个式子呢?
query(s[i] + OFFSET)
其实完整写法是query(s[i] + OFFSET) * 1
,它求解的是如果当前区间 [ 1 , i ] [1,i] [1,i]中的众数是元素1的话,那么就求这些子区间中众数1的总和。(i - query(s[i] + OFFSET)) * 2
,它求解的是如果当前区间 [ 1 , i ] [1,i] [1,i]中的众数是元素1的话,那么就求这些子区间中众数1的总和。当前有 i i i个元素,其中众数是元素1的个数有query(s[i] + OFFSET)
个,那么众数是元素2的个数就为(i - query(s[i] + OFFSET))
。然后求这些子区间中众数2的总和即可。
#include <bits/stdc++.h>
const int N = 2e5 + 10;
using LL = long long ;
int a[N], s[N], tr[N * 2], n;inline int lowbit(int x) {return x & -x;
}void modify(int x, int k) {for (int i = x; i <= 2 * n + 10; i += lowbit(i)) tr[i] += k;
}LL query(int x) {LL ans = 0;for (int i = x; i; i -= lowbit(i)) ans += tr[i];return ans;
}int main() {scanf("%d", &n);int OFFSET = n + 1; // 偏移量,防止下标是负数,使得下标从1开始for (int i = 1; i <= n; ++ i) scanf("%d", &a[i]);modify(0 + OFFSET, 1); // 边界初始化!!!LL ans = 0;for (int i = 1; i <= n; ++ i) {if (a[i] == 1) s[i] += s[i - 1] + 1;else s[i] += s[i - 1] - 1;// query(s[i] + OFFSET) * 1计算出如果1是众数时的和// (i - query(s[i] + OFFSET)) * 2计算出如果2是众数时的和ans += query(s[i] + OFFSET) + (i - query(s[i] + OFFSET)) * 2;modify(s[i] + OFFSET, 1);}printf("%lld", ans);
}
第五题 小美的逆序对
本题可以考虑使用树状数组来求逆序对。
我们可以先对原数组求一遍逆序对。对于第 i i i个数字,它在变为最小的数字后,在它之前的所有比它小的数字都会和它组成逆序对,在它之后所有比它小的数字会由原本构成逆序对转变成不构成逆序对。设在它左侧比它小的数字的个数为cnt
,那么在它右侧比它小的数字的个数就是x - 1 - cnt
。因此当元素x取反后,它左侧这cnt
个数字就比x大,增加了cnt
个逆序对,然后它右侧这x-1-cnt
个数字就比x大,减少了x-1-cnt
个逆序对。由此逆序对的增量就是x - (x - 1 - cnt)
个。考虑原本的逆序对数目s
,则第 i i i个数字取反后的逆序对数目为s + x - (x - 1 - cnt)
。
#include <bits/stdc++.h>
const int N = 2e5 + 10;
using LL = long long ;
int t[N], tr[N], n;inline int lowbit(int x) {return x & -x;
}void modify(int x, int k) {for (int i = x; i <= n; i += lowbit(i)) tr[i] += k;
}LL query(int x) {LL ans = 0;for (int i = x; i; i -= lowbit(i)) ans += tr[i];return ans;
}int main() {scanf("%d", &n);LL s = 0;for (int i = 1; i <= n; ++ i) {int x;scanf("%d", &x);s += query(n) - query(x);// cnt表示x左侧比x小的元素个数, x - 1 - cnt表示x右侧比x小的元素个数LL cnt = query(x - 1);t[i] = cnt - (x - 1 - cnt);modify(x, 1);}for (int i = 1; i <= n; ++ i) printf("%lld ", s + t[i]);
}
相关文章:

美团0316春招笔试题
下面是美团2024-03-16笔试真题,进行了VP,由于未参与评测,故不保证正确性,仅供参考。 第一题 小美点外卖 求和然后减去满减和红包即可。 #include <bits/stdc.h> using namespace std; using LL long long ; int n, t, x,…...

typescript 实现RabbitMQ死信队列和延迟队列 订单10分钟未付归还库存
Manjaro安装RabbitMQ 安装 sudo pacman -S rabbitmq rabbitmqadmin启动管理模块 sudo rabbitmq-plugins enable rabbitmq_managementsudo rabbitmq-server管理界面 http://127.0.0.1:15672/ 默认用户名和密码都是guest。 要使用 rabbitmqctl 命令添加用户并分配权限…...

怎样才能把重建大师的空三导进去CC?
导出空三文件xml两者都是通用的,cc和photoscan都可以兼容。 重建大师是一款专为超大规模实景三维数据生产而设计的集群并行处理软件,输入倾斜照片,激光点云,POS信息及像控点,输出高精度彩色网格模型,可一键…...

命令模式(请求与具体实现解耦)
目录 前言 UML plantuml 类图 实战代码 模板 Command Invoker Receiver Client 前言 命令模式解耦了命令请求者(Invoker)和命令执行者(receiver),使得 Invoker 不再直接引用 receiver,而是依赖于…...

开发一款MMOARPG难度到底有多大
开发一款MMOARPG难度到底有多大 MMORPG游戏开发到底有多难,我们按照过去开发的标准,就比如开发一款传奇,那时候哪会用什么别人的引擎,都是自研,从基础图形API开始。我们不考虑美术和策划,就单指程序&#x…...

RTSP应用:实现视频流的实时推送
在实现实时视频流推送的项目中,RTSP(Real Time Streaming Protocol)协议扮演着核心角色。本文将指导你通过安装FFmpeg软件,下载并编译live555,以及配置ffmpeg进行视频流推送,来实现一个基本的RTSP流媒体服务…...

Java八股文(数据结构)
Java八股文の数据结构 数据结构 数据结构 请解释以下数据结构的概念:链表、栈、队列和树。 链表是一种线性数据结构,由节点组成,每个节点包含了指向下一个节点的指针; 栈是一种后进先出(LIFO)的数据结构&a…...

ActiveMQ Artemis 系列| High Availability 主备模式(消息复制) 版本2.19.1
一、ActiveMQ Artemis 介绍 Apache ActiveMQ Artemis 是一个高性能的开源消息代理,它完全符合 Java Message Service (JMS) 2.0 规范,并支持多种通信协议,包括 AMQP、MQTT、STOMP 和 OpenWire 等。ActiveMQ Artemis 由 Apache Software Foun…...

QGIS插件系列--WhiteBox Tools
WhiteBox Tools(官网机翻): WhiteboxTools是由圭尔夫大学地貌测量和水文地理信息学研究小组(GHRG)开发的高级地理空间软件包和数据分析平台。该项目始于2017年<>月,并在分析能力方面迅速发展。WhiteboxTools的一…...

SpringMVC设置全局异常处理器
文章目录 背景分析使用ControllerAdvice(RestControllerAdvice)ExceptionHandler实现全局异常全局异常处理-多个处理器匹配顺序存在一个类中存在不同的类中 对于过滤器和拦截器中的异常,有两种思路可以考虑 背景 在项目中我们有需求做一个全…...

Acwing_795前缀和 【一维前缀和】+【模板】二维前缀和
Acwing_795前缀和 【一维前缀和】 题目: 代码: #include <bits/stdc.h> #define int long long #define INF 0X3f3f3f3f #define endl \n using namespace std; const int N 100010; int arr[N];int n,m; int l,r; signed main(){std::ios::s…...

docker 部署 gitlab-ce 16.9.1
文章目录 [toc]拉取 gitlab-ce 镜像创建 gitlab-ce 持久化目录启停脚本配置配置 gitlab-ce编辑 gitlab-ce 配置文件重启 gitlab-ce配置 root 密码 设置中文 gitlab/gitlab-ce(需要科学上网) 拉取 gitlab-ce 镜像 docker pull gitlab/gitlab-ce:16.9.1-ce.0查看镜像是不是有 Vo…...

29.Python从入门到精通—Python3 面向对象继承 多继承 方法重写 类属性与方法
29.从入门到精通:Python3 面向对象继承 多继承 方法重写 类属性与方法 继承多继承方法重写类属性与方法 继承 在面向对象编程中,继承是指通过继承现有类的属性和方法来创建新类的过程。新类称为子类(或派生类),现有类…...

jQuery如何获取元素宽高?
在jQuery中,获取元素的宽和高有多种方法,取决于你是否需要包括边框、内边距或其他额外空间。以下是几种常用的方式: 获取元素内容区域的宽和高(不包括边框和内边距): var width $(#yourElement).width(); …...

springdata框架对es集成
什么是spring data框架 Spring Data是一个用于简化数据库、非关系型数据库、索引库访问,并支持云服务的开源框架。其主要目标是使得对数据的访问变得方便快捷,并支持 map-reduce框架和云计算数据服务。Spring Data可以极大的简化JPA(Elasticsearch…)的…...

jvm(虚拟机)运行时数据区域介绍
Java虚拟机(JVM)运行时数据区域是Java程序在运行过程中使用的内存区域,它主要包括以下几个部分: 程序计数器(Program Counter Register): 程序计数器是一块较小的内存区域,是线程私有…...

C++ MFC 只启动一个程序实例 唤醒之前的实例(完整源码)
初级代码游戏的专栏介绍与文章目录-CSDN博客 很多时候我们希望只允许启动一个程序实例,如果再次运行,就唤醒之前的实例。 目录 1 概述 2 相关技术介绍 2.1 互斥对象 2.2 查找窗口 2.3 唤醒窗口 1 概述 技术上并不难,涉及到以下几个技术…...

2024多云管理平台CMP排名看这里!
随着云计算技术的迅猛发展,多云管理平台CMP应运而生。多云管理平台CMP仅能够简化对多个云环境的统一管理,还能提高资源利用效率和降低成本。因此了解多云管理平台CMP品牌是必要的。2024多云管理平台CMP排名看这里!仅供参考哈! 20…...

MySQL 数据库的日志管理、备份与恢复
一. 数据库备份 1.数据备份的重要性 备份的主要目的是灾难恢复。 在生产环境中,数据的安全性至关重要。 任何数据的丢失都可能产生严重的后果。 造成数据丢失的原因: 程序错误人为,操作错误,运算错误,磁盘故障灾难(如火灾、地震࿰…...

一、Go开发环境搭建
文章目录 1、开发工具2、开发环境配置3、Hello World4、语法 1、开发工具 https://code.visualstudio.com/download 2、开发环境配置 类比Java的JDK,go的SDK下载:https://studygolang.com/dl 解压: 配置环境变量path,将命令&quo…...

包子凑数(蓝桥杯,闫氏DP分析法)
题目描述: 小明几乎每天早晨都会在一家包子铺吃早餐。 他发现这家包子铺有 N 种蒸笼,其中第 i 种蒸笼恰好能放 Ai 个包子。 每种蒸笼都有非常多笼,可以认为是无限笼。 每当有顾客想买 X 个包子,卖包子的大叔就会迅速选出若干笼…...

Java八股文(JVM)
Java八股文のJVM JVM JVM 什么是Java虚拟机(JVM)? Java虚拟机是一个运行Java字节码的虚拟机。 它负责将Java程序翻译成机器代码并执行。 JVM的主要组成部分是什么? JVM包括以下组件: ● 类加载器(ClassLoa…...

云硬盘扩容后将空间增加到原有分区的解决方案
大家好,我是爱编程的喵喵。双985硕士毕业,现担任全栈工程师一职,热衷于将数据思维应用到工作与生活中。从事机器学习以及相关的前后端开发工作。曾在阿里云、科大讯飞、CCF等比赛获得多次Top名次。现为CSDN博客专家、人工智能领域优质创作者。喜欢通过博客创作的方式对所学的…...

Tensorflow2.0笔记 - metrics做损失和准确度信息度量
本笔记主要记录metrics相关的内容,详细内容请参考代码注释,代码本身只使用了Accuracy和Mean。本节的代码基于上篇笔记FashionMnist的代码经过简单修改而来,上篇笔记链接如下: Tensorflow2.0笔记 - FashionMnist数据集训练-CSDN博…...

LeetCode 面试经典150题 290.单词规律
题目: 给定一种规律 pattern 和一个字符串 s ,判断 s 是否遵循相同的规律。 这里的 遵循 指完全匹配,例如, pattern 里的每个字母和字符串 s 中的每个非空单词之间存在着双向连接的对应规律。 思路:一一映射需要用到…...

【CASS精品教程】CASS中计算四参数和七参数(以RTK数据为例)
文章目录 一、四参数介绍二、四参数计算三、七参数介绍四、四参数、七参数的区别一、四参数介绍 两个不同的二维平面直角坐标系之间转换通常使用四参数模型,四参数适合小范围测区的空间坐标转换,相对于七参数转换的优势在于只需要2个公共已知点就能进行转换,操作简单。 在…...

什么是RISC-V?开源 ISA 如何重塑未来的处理器设计
RISC-V代表了处理器架构的范式转变,特点是其开源模型简化了设计理念并促进了全球community-driven的开发。RISC-V导致了处理器技术发展前进方式的重大转变,提供了一个不受传统复杂性阻碍的全新视角。 RISC-V起源于加州大学伯克利分校的学术起点ÿ…...

展馆设计中展示有哪些要求
1、展示产品特点和功能 产品展示应突出产品的特点、功能和优势。通过使用适当的展示方式和展示环境,使观众能够直观地了解产品的外观、结构、性能等方面。可以使用实物展示、模型、原型、图表、动画等方式,以多种角度和视角展示产品的特点和功能。 2、提…...

python实战之PyQt5桌面软件
一. 演示效果 二. 准备工作 1. 使用pip 下载所需包 pyqt5 2. 下载可视化UI工具 QT Designer 链接:https://pan.baidu.com/s/1ic4S3ocEF90Y4L1GqYHPPA?pwdywct 提取码:ywct 3. 可视化UI工具汉化 把上面的链接打开, 里面有安装和汉化包, 前面的路径还要看…...

Switch 和 PS1 模拟器:3000+ 游戏随心玩 | 开源日报 No.174
Ryujinx/Ryujinx Stars: 26.1k License: MIT Ryujinx 是用 C# 编写的实验性任天堂 Switch 模拟器。 该项目旨在提供出色的准确性和性能、用户友好的界面以及稳定的构建。它已经通过了大约 4050 个测试,其中超过 4000 个可以启动并进入游戏,其中大约 340…...