蓝桥杯 第三场 小白入门赛

news/2024/2/25 11:38:02/文章来源:https://blog.csdn.net/wyzz_yz/article/details/135598329

召唤神坤

  • 有意思🤔(ikun)。
  • 虽然是第一题但也要配得上神坤的身份。

思路1

  • 枚举分母,选择一个数据结构来选出分母两侧最大的两个数做分子。
  • 2s常数大些也无碍。
  • 我选择好写的ST表

思路2

  • 写两个 d p dp dp 分别表示 1 1 1 i i i 的最大值, i i i n n n 的最大值。再枚举。
  • 这个不放码了看的别人的思路。
signed main() {int T = 1;
//    T = read();while (T--) {int n = read();vector<int> a(n + 1), logn(n + 1);vector<vector<int>> f(n + 1, vector<int>(30));for (int i = 1; i <= n; ++i) f[i][0] = a[i] = read();logn[0] = -1;for (int i = 1; i <= n; ++i) logn[i] = logn[i >> 1] + 1;for (int j = 1; j <= logn[n]; ++j) {for (int i = 1; i + (1 << j) - 1 <= n; ++i) {f[i][j] = max(f[i][j - 1], f[i + (1 << (j - 1))][j - 1]);}}int ans = 0;for (int i = 2; i < n; ++i) {int l = 1, r = i - 1, s = logn[r - l + 1];int wi = max(f[l][s], f[r - (1 << s) + 1][s]);l = i + 1, r = n, s = logn[r - l + 1];int wk = max(f[l][s], f[r - (1 << s) + 1][s]);ans = max(ans, (wi + wk) / a[i]);}write(ans);}return 0;
}

聪明的交换策略

分析

  • 依据题意就是要么 0 0 0 1 1 1 右,要么 1 1 1 0 0 0 右。
  • 考虑 0 0 0 左还是 0 0 0 右即可。考虑 1 1 1 也行一样的。
signed main() {int T = 1;
//    T = read();while (T--) {int n = read();string s; cin >> s;vector<int> pos;for (int i = 0; i < s.size(); ++i) {if (s[i] ^ '1') pos.push_back(i);}int ans = 1e17, tmp1 = 0, tmp2 = 0;for (int i = 0; i < pos.size(); ++i) tmp1 += pos[i] - i;ans = min(ans, tmp1);for (int i = pos.size() - 1, j = n - 1; i >= 0; --i, --j) tmp2 += j - pos[i];ans = min(ans, tmp2);write(ans);}return 0;
}

怪兽突击

ps:总觉得codeforces做过。。

思路

  • 枚举每个 i i i (当然要小于等于 k k k )。
signed main() {int T = 1;
//    T = read();while (T--) {int n = read(), k = read();vector<int> a(n + 1), b(n + 1);for (int i = 1; i <= n; ++i) a[i] = read();for (int i = 1; i <= n; ++i) b[i] = read();priority_queue<int, vector<int>, greater<int>> pq;int ans = 1e17, cnt = 0;for (int i = 1; i <= n && i <= k; ++i) {cnt += a[i];pq.push(a[i] + b[i]);ans = min(ans, cnt + (k - i) * pq.top());}write(ans);}return 0;
}

蓝桥快打

思路

  • 根据 A , C A,C A,C 可以得出攻击次数的范围, B ≤ n ⋅ x B\leq n\cdot x Bnx
signed main() {int T = 1;T = read();while (T--) {int a = read(), b = read(), c = read();int r = a / c + (a % c > 0);writeln(b / r + (b % r > 0));}return 0;
}

奇怪的段

思路

  • d p dp dp
  • 方程: d p i = m a x ( d p i − 1 , j , d p i − 1 , j − 1 ) + a i ⋅ p j dp_i=max(dp_{i-1,j},dp_{i-1,j-1})+a_i\cdot p_j dpi=max(dpi1,j,dpi1,j1)+aipj
  • 注意有负数
signed main() {int T = 1;
//    T = read();while (T--) {int n = read(), k = read();vector<int> a(n + 1), p(k + 1);vector<vector<int>> dp(n + 1, vector<int>(201, -1e15));dp[0][0] = 0;for (int i = 1; i <= n; ++i) a[i] = read();for (int i = 1; i <= k; ++i) p[i] = read();for (int i = 1; i <= n; ++i) {for (int j = 1; j <= k; ++j) {dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - 1]) + a[i] * p[j];}}write(dp[n][k]);}return 0;
}

小蓝的反击

ps:是个区间求解问题,涉及基础数论。

思路

  • 枚举每一个 i i i ,找到最小位置 j j j 满足 A ∣ ∏ k = i j 1 a k , B ∣ ∏ k = i j 2 a k A| \prod_{k=i}^{j_1}a_k,\;B|\prod_{k=i}^{j_2}a_k Ak=ij1ak,Bk=ij2ak
  • 如果 j 1 j_1 j1 不存在那么往后再也不能整除 A A A 了。如果 j 2 j_2 j2 不存在,那么从 j 1 j_1 j1 n n n 都能整出 A A A 。都存在只有 j 2 > j 1 j_2 >j_1 j2>j1 才对答案有贡献。
  • A , B A,B A,B 质因数分解记录因子和各因子数量。
  • A , B A,B A,B 每一个因子做前缀和。
  • 二分枚举区间询问是否存在(该有的因子和数量都要满足)。

ps:前缀和那儿显然是个二维的,试想质因数分解有可能出现因数很大的情况,第二维是因数大小会 M E L MEL MEL ,所以第二维应该为数量,而数量最多是10(前十个质数相乘已经 > 1 0 9 >10^9 >109 )。看题解有个 d p dp dp 的,巨,我不会。

signed main() {auto getFactor = [&] (int v) {vector<pii> vec;for (int i = 2; i <= v / i; ++i) {if (!(v % i)) {vec.push_back({i, 0});while (!(v % i)) v /= i, ++vec.back().second;}}if (v ^ 1) vec.push_back({v, 1});return vec;};int T = 1;
//    T = read();while (T--) {int n = read(), a = read(), b = read();auto vec1 = getFactor(a), vec2 = getFactor(b);vector<vector<int>> prefa(n + 1, vector<int>(10)), prefb(n + 1, vector<int>(10));for (int i = 1; i <= n; ++i) {int u = read();for (int j = 0; j < vec1.size(); ++j) {int tmp = u, v = vec1[j].first;while (!(tmp % v)) {++prefa[i][j];tmp /= v;}prefa[i][j] += prefa[i - 1][j];}for (int j = 0; j < vec2.size(); ++j) {int tmp = u, v = vec2[j].first;while (!(tmp % v)) {++prefb[i][j];tmp /= v;}prefb[i][j] += prefb[i - 1][j];}}auto find = [&] (int i, int j, int cnt, int op) {int l = i, r = n, tmp = op? prefb[i - 1][j]: prefa[i - 1][j];int ans = -1;while (l <= r) {int mid = (l + r) >> 1, v = op? prefb[mid][j]: prefa[mid][j];if (v - tmp >= cnt) ans = mid, r = mid - 1;else l = mid + 1;}return ans;};long long int ans = 0;for (int i = 1; i <= n; ++i) {int pos1 = i;for (int j = 0; j < vec1.size(); ++j) {int pos = find(i, j, vec1[j].second, 0);if (pos ^ -1) pos1 = max(pos1, pos);else {pos1 = -1;break;}}if (pos1 == -1) break;int pos2 = i;for (int j = 0; j < vec2.size(); ++j) {int pos = find(i, j, vec2[j].second, 1);if (pos ^ -1) pos2 = max(pos2, pos);else {pos2 = -1;break;}}if (pos2 == -1) ans += (n - pos1 + 1) * 1ll;else if (pos2 > pos1) ans += (pos2 - pos1) * 1ll;}// write(ans);cout << ans;}return 0;
}

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

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

相关文章

mac快捷创建文件的方法

mac快捷创建文件的方法 在macbook的使用中&#xff0c;当我们在桌面或访达等地方使用右键时&#xff0c;可以看到新建文件夹的选项&#xff0c;却怎么也找不到创建文件的选项。这种情况有时候会带来不便。这篇文章给大家带来一个非常简单解决这个问题。 下载 在App Store中搜索…

使用numpy处理图片——90度旋转

大纲 左旋转90度向右旋转90旋转180度 代码地址 在《使用numpy处理图片——镜像翻转和旋转》一文中&#xff0c;我们介绍了如何将图片旋转的方法。本文将使用更简单的方法旋转图片90度。 左旋转90度 import numpy as np import PIL.Image as Imagedata np.array(Image.open(t…

5.3 Verilog 带参数例化

5.3 Verilog 带参数例化 分类 Verilog 教程 关键词&#xff1a; defparam&#xff0c;参数&#xff0c;例化&#xff0c;ram 当一个模块被另一个模块引用例化时&#xff0c;高层模块可以对低层模块的参数值进行改写。这样就允许在编译时将不同的参数传递给多个相同名字的模块…

获取本地IP网卡信息

提示&#xff1a;文章写完后&#xff0c;目录可以自动生成&#xff0c;如何生成可参考右边的帮助文档 文章目录 前言一、获取本地IP&#xff0c;以及全部网卡信息总结 前言 一、获取本地IP&#xff0c;以及全部网卡信息 const os require(node:os) function getIPAdress(){/…

初识Ubuntu

其实还是linux操作系统 命令都一样 但是在学习初级阶段&#xff0c;我还是将其分开有便于我的学习和稳固。 cat 查看文件 命令 Ubuntu工作中经常是用普通用户&#xff0c;在需要时才进行登录管理员用户 sudn -i 切换成管理用户 我们远程连接时 如果出现 hostname -I没有出现…

Spring Boot 中批量执行 SQL 脚本的实践

在Spring Boot应用中&#xff0c;有时候我们需要批量执行存储在数据库中的 SQL 脚本。本文将介绍一个实际的案例&#xff0c;演示如何通过 Spring Boot、MyBatis 和数据库来实现这一目标。 0、数据库层 CREATE TABLE batchUpdate (id INT AUTO_INCREMENT PRIMARY KEY,update_…

Shopee买家通系统:领先科技助力卖家全自动化营销

在虾皮卖家和服务商的竞争激烈的市场环境下&#xff0c;不断追求创新和效率提升是至关重要的。近期推出的Shopee买家通系统正是基于最新的防指纹防关联技术&#xff0c;以其独特的能力完全模拟真人运行&#xff0c;实现全自动化操作&#xff0c;为卖家们提供了一款卓越的营销工…

跟着cherno手搓游戏引擎【7】Input轮询

在引擎程序中任何时间&#xff0c;任何位置都能知道按键是否按下、鼠标的位置等等信息。 与事件系统的区别&#xff1a;事件系统是在按下时调用并传递按键状态&#xff1b;轮询是每时每刻都能获取按键状态 创建基类&#xff1a; YOTO/Input.h&#xff1a;名如其意 #pragma …

强化学习应用(一):基于Q-learning的无人机物流路径规划研究(提供Python代码)

一、Q-learning简介 Q-learning是一种强化学习算法&#xff0c;用于解决基于马尔可夫决策过程&#xff08;MDP&#xff09;的问题。它通过学习一个价值函数来指导智能体在环境中做出决策&#xff0c;以最大化累积奖励。 Q-learning算法的核心思想是通过不断更新一个称为Q值的…

C++力扣题目77--组合

给定两个整数 n 和 k&#xff0c;返回范围 [1, n] 中所有可能的 k 个数的组合。 你可以按 任何顺序 返回答案。 示例 1&#xff1a; 输入&#xff1a;n 4, k 2 输出&#xff1a; [[2,4],[3,4],[2,3],[1,2],[1,3],[1,4], ] 示例 2&#xff1a; 输入&#xff1a;n 1, k …

k8s源码阅读:Informer源码解析

写在之前 Kubernetes的Informer机制是一种用于监控资源对象变化的机制。它提供了一种简化开发者编写控制器的方式&#xff0c;允许控制器能够及时感知并响应 Kubernetes 集群中资源对象的变化。Informer通过与Kubernetes API服务器进行交互&#xff0c;通过监听API服务器上资源…

【设计模式-03】Strategy策略模式及应用场景

一、简要描述 Java 官方文档 Overview (Java SE 18 & JDK 18)module indexhttps://docs.oracle.com/en/java/javase/18/docs/api/index.html Java中使用到的策略模式 Comparator、comparable Comparator (Java SE 18 & JDK 18)declaration: module: java.base, pa…

WPF真入门教程28--项目案例--MQTT服务器和客户端

1、先上图看帅照 这个案例还是布局加视图模型&#xff0c;样式应用&#xff0c;业务逻辑&#xff0c;该项目是一个mqtt服务器和客户端的通信工具&#xff0c;这里不去分析mqtt的通信原理&#xff0c;关注在于wpf技能的应用&#xff0c;能够掌握这个例子&#xff0c;离项目开发…

C#编程-在线程中使用同步

在线程中使用同步 在线程应用程序中,线程需要相互共享数据。但是,应用程序应该确保一个线程不更改另一个线程使用的数据。考虑有两个线程的场景。一个线程从文件读取工资,另一个线程尝试更新工资。当两个线程同时工作时,数据就会受损。下图显示了两个线程同时访问一个文件…

杨中科 .NETCORE EFCORE第七部分 一对一,多对多

一对一 一对一关系配置 1、builder.HasOne(o >o.Delivery).WithOne(d>d.Order).HasForeignKey(d>dOrderId); 2、测试插入和获取数据 示例 新建 Order 新建 Delivery DeliveryConfig OrderConfig 执行 迁移命令 查看数据库 测试数据插入 运行查看数据 多对多…

Python文件自动化处理

os模块 Python标准库和操作系统有关的操作创建、移动、复制文件和文件夹文件路径和名称处理 路径的操作 获取当前Python程序运行路径不同操作系统之间路径的表示方式 windows中采用反斜杠(\)作为文件夹之间的分隔符 Mac和Linux中采用斜杠(/)作为文件夹之间的分隔符 把文件…

Qt优秀开源项目之二十一:遇见QSkinny,一个轻量级Qt UI库

目录 一.QSkinny简介 二.工作原理 三.编译 一.QSkinny简介 QSkinny库基于Qt Graphic View和Qt/Quick中少量的核心类。它提供了一组轻量级控件&#xff0c;可以在C或QML中使用这些控件。QSkinny默认是启用硬件加速的&#xff0c;非常适合嵌入式设备&#xff0c;目前已经应用于…

[DL]深度学习_Feature Pyramid Network

FPN结构详解 目录 一、概念介绍 二、结构详解 1、对比试验 2、特征图融合 3、结构详解 4、不同尺度预测 5、Proposal映射到预测特征层 一、概念介绍 Feature Pyramid Network (FPN)是一种用于目标检测和语义分割的神经网络架构。它的目标是解决在处理不同尺度的图像时…

SQLServer 为角色开视图SELECT权限,报错提示需要开基础表权限

问题&#xff1a; 创建了个视图V&#xff0c;里面包含V库的a表&#xff0c;和T库的b表 为角色开启视图V的SELECT权限&#xff0c;提示T库的b表无SELECT权限&#xff0c;报错如下 解决方案&#xff1a; ①在T库建个视图TV&#xff0c;里面包含b表&#xff08;注意是在b表的对…

基于SSM的戏剧推广网站的设计与实现

末尾获取源码 开发语言&#xff1a;Java Java开发工具&#xff1a;JDK1.8 后端框架&#xff1a;SSM 前端&#xff1a;Vue、HTML 数据库&#xff1a;MySQL5.7和Navicat管理工具结合 服务器&#xff1a;Tomcat8.5 开发软件&#xff1a;IDEA / Eclipse 是否Maven项目&#xff1a;是…