当前位置: 首页 > news >正文

牛客 7.13 月赛(留 C逆元 Ddp)

B-最少剩几个?_牛客小白月赛98 (nowcoder.com)

思路

奇数+偶数 = 奇数;奇数*偶数 = 奇数

所以在既有奇数又有偶数时,两者结合可以同时删除

先分别统计奇数,偶数个数

若偶个数大于奇个数,答案是偶个数-奇个数

若奇个数大于偶个数,奇数个数减去偶个数再对2取模

ac代码
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)int main()
{IOS;int n,ans;int ji=0,ou=0;cin>>n;vector<ll>a(n);for(int i=0;i<n;i++) {cin>>a[i];if(a[i] & 1) ji++;else ou++; }if(ou>ji)  ans=ou-ji;else{if((ji-ou)%2) ans=1;else ans=0;}cout<<ans<<endl;   return 0;
}

C-两个函数_牛客小白月赛98 (nowcoder.com)

(超时问题如何解决)

初始代码(超时)
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)int main()
{IOS;ll q,a,x;cin>>q;for(int i=0;i<q;i++){ll ans=0;cin>>a>>x;if(x==1) ans=(a*x)%998244353;else{for(int i=1;i<x;i++){ans+=(a*(a%998244353*i)%998244353)%998244353;ans%=998244353;					}}ans%=998244353;cout<<ans<<endl;}return 0;
}
解决思路

1.  快速幂

时间复杂度是 O(log n),相比于直接进行指数运算,大大提高了计算效率

快速幂代码

int FastPow(int a,int x,int mod)
{int ans = 1;a%=mod;while(x){if(x&1) ans=(ans*a)%mod;a= (a*a)%mod;x>>=1;}return ans;
}

2.  递推式

因为是求和过程,可以用递推式

ac代码
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
ll mod=998244353;int main()
{IOS;ll q,a,x;cin>>q;for(int i=0;i<q;i++){ll ans=0;cin>>a>>x;if(x==1) ans=a%mod;else {a = a*a %mod;ans=(x-1)*x/2 %mod *a %mod;}cout<<ans<<endl;}return 0;
}

D-切割 01 串 2.0_牛客小白月赛98 (nowcoder.com)

思路:

1.  前缀和

        记录在索引的每一个位置处之前,0或1的个数

2.dp

        dp[i][j] 表示考虑前 i 个字符时,最多可以进行多少次切割;对于每个长度 len,遍历所有可能的切割起点 l,使得 l + len - 1 不超过序列的长度;对于每个起点 l,计算可能的切割终点 r;

   对于每个起点 l 和终点 r,遍历所有可能的切割分割点 k,使得 k 在 l 和 r 之间;

动态规划过程的关键在于,通过递归地考虑所有可能的切割方式,并使用前缀和数组来快速计算分割点 k 两侧的子串中0和1的累计数量。通过这种方式,算法能够高效地找到满足条件的切割次数的最大值

代码
#include<bits/stdc++.h>
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)using namespace std;/*
算法:区间DP + 前缀和 O(N*N*N)
数据结构:s0,s1前缀和数组 + 二维dp[l][r]
*/const int N = 510;int s0[N], s1[N];
int dp[N][N];void solve() {int n, L, R;string s;cin >> n >> L >> R >> s;s = " " + s;for (int i = 1; i <= n; i ++ )s0[i] = s0[i - 1] + (s[i] == '0'),s1[i] = s1[i - 1] + (s[i] == '1');for (int len = 1; len <= n; len ++ )for (int l = 1; l <= n; l ++ ){int r = l + len - 1;if (r > n) break;for (int k = l; k < r; k ++ ){int c0 = s0[k] - s0[l - 1];int c1 = s1[r] - s1[k];if (L <= abs(c0 - c1) && abs(c0 - c1) <= R) dp[l][r] = max(dp[l][r], 1 + dp[l][k] + dp[k + 1][r]);}}cout << dp[1][n] << '\n';
}signed main() {IOS;int t = 1;
//    cin >> t;while (t--) {solve();}return 0;
}

相关文章:

牛客 7.13 月赛(留 C逆元 Ddp)

B-最少剩几个&#xff1f;_牛客小白月赛98 (nowcoder.com) 思路 奇数偶数 奇数&#xff1b;奇数*偶数 奇数 所以在既有奇数又有偶数时&#xff0c;两者结合可以同时删除 先分别统计奇数&#xff0c;偶数个数 若偶个数大于奇个数&#xff0c;答案是偶个数-奇个数 若奇个数…...

LeetCode 92. 反转链表 II

LeetCode 92. 反转链表 II 给你单链表的头指针 head 和两个整数 left 和 right &#xff0c;其中 left < right 。请你反转从位置 left 到位置 right 的链表节点&#xff0c;返回 反转后的链表 。 示例 1&#xff1a; 输入&#xff1a;head [1,2,3,4,5], left 2, right 4…...

mac M1 创建Mysql8.0容器

MySLQ8.0 拉取m1镜像 docker pull mysql:8.0创建挂载文件夹并且赋予权限 sudo chmod 777 /Users/zhao/software/dockerLocalData/mysql 创建容器并且挂载 docker run --name mysql_8 \-e MYSQL_ROOT_PASSWORDadmin \-v /Users/zhao/software/dockerLocalData/mysql/:/var/l…...

【Vue3】4个比较重要的设计模式!!

大家好,我是CodeQi! 一位热衷于技术分享的码仔。 在我投身于前端开发的职业生涯期间,曾有一次承接了一个大型项目的维护工作。此项目运用的是 Vue 框架,然而其代码结构紊乱不堪,可维护性极度糟糕😫。 这使我深刻领会到,理解并运用 Vue 中的重要设计模式是何等关键! …...

Ubuntu安装virtualbox(win10)

virtualbox下载安装 1、下载virtualbox 下载路径&#xff1a;Linux_Downloads – Oracle VM VirtualBox 根据自己的Ubuntu版本选择对应的安装包下载 2、安装virtualbox 到下载路径&#xff08;一般为~/Download&#xff09;打开终端输入命令 sudo dpkg -i xxx.deb 继续执…...

二次开发源码 借贷系统uniapp/借贷认证系统/小额信贷系统/工薪贷APP/资金贷系统h5

前端&#xff1a;UNIAPP 后端&#xff1a;ThinkPHP 数据库&#xff1a; Mysql 前端使用的uniapp 可以打包APP H5 小程序 系统提供了完善的网络借贷体系&#xff0c;为金融中介平台提供从获客到贷后管理全流程服务&#xff0c;解决了借贷手续繁琐、流程缓慢等问题 此源码为运营…...

LG 选择 Flutter 来增强其智能电视操作系统 webOS

可以这个话题会让大多数人困惑&#xff0c;2024 年了为什么还会冒出 webOS 这种老古董&#xff1f;然后 LG 为什么选择 webOS &#xff1f;现在为什么又选择 Flutter &#xff1f; 其实早在 Google I/O 发布 Flutter 3.22 版本的时候&#xff0c;就提到了 LG 选择 Flutter 来增…...

[ACM独立出版] 2024年虚拟现实、图像和信号处理国际学术会议(VRISP 2024,8月2日-4)

2024年虚拟现实、图像和信号处理国际学术会议&#xff08;VRISP 2024&#xff09;将于2024年8月2-4日在中国厦门召开。 VRISP 2024将围绕“虚拟现实、图像和信号处理”的最新研究领域&#xff0c;为来自国内外高等院校、科学研究所、企事业单位的专家、教授、学者、工程师等提供…...

ASP.NET Core中创建中间件的几种方式

前言 今天我们一起来盘点一下在ASP.NET Core应用程序中添加和创建中间件常见的四种方式。 中间件介绍 ASP.NET Core中间件&#xff08;Middleware&#xff09;是用于处理HTTP请求和响应的组件&#xff0c;它们被安排在请求处理管道中&#xff0c;并按顺序执行。中间件的设计是为…...

Atcoder ABC351 A-E 题解

A: 打卡题 题目描述 一中队和二中队正在进行一场棒球比赛&#xff0c;一中队是第一棒。 目前&#xff0c;比赛已进行到第九局上半&#xff0c;第九局下半即将开始。 一中队在 第i局 (1 < i < 9) 上半场得到了 Ai 分&#xff0c;二中队在 第j局 (1 < j < 8) 下…...

【终极指南】从零开始征服机器学习:初学者的黄金路线图

踏入机器学习的世界&#xff0c;对许多初学者而言&#xff0c;无疑是一场既兴奋又略带忐忑的冒险。尤其对于那些非数学或计算机专业背景的同学&#xff0c;或是已经在职场打拼的朋友们&#xff0c;寻找一条适合自己的入门路径&#xff0c;显得尤为重要。鉴于此&#xff0c;本文…...

MongoDB自学笔记(三)

一、前文回顾 上一篇文章中我们学习了更新操作&#xff0c;以及讲解了部分的更新操作符&#xff0c;今天我们继续学习剩余的更新操作符。 二、更新操作符 1、$rename 语法&#xff1a;{ $rename: { < field1 >: < newName1 >, < field2 >: < newName2…...

编程中的智慧之设计模式三

深入探索设计模式&#xff1a;实际应用和优化策略 在前两篇文章中&#xff0c;我们详细探讨了创建型模式、结构型模式、行为模式和架构模式的基本概念及其在Java中的实现。在本文中&#xff0c;我们将进一步探讨如何在实际项目中应用和优化这些模式&#xff0c;尤其是如何在大…...

《YOLOv10改进实战专栏》专栏介绍 专栏目录

《YOLOv10改进实战专栏》介绍及目录 YOLOv10官方仓库地址 专栏地址&#xff1a;点击跳转 专栏导航如下&#xff1a; &#x1f380;基础入门篇&#x1f380; 万字长文&#xff0c;小白新手怎么开始做YOLO实验&#xff0c;从零开始教&#xff01;整体思路在这里&#xff0c;科研指…...

Python酷库之旅-第三方库Pandas(030)

目录 一、用法精讲 79、pandas.Series.dtype属性 79-1、语法 79-2、参数 79-3、功能 79-4、返回值 79-5、说明 79-6、用法 79-6-1、数据准备 79-6-2、代码示例 79-6-3、结果输出 80、pandas.Series.shape属性 80-1、语法 80-2、参数 80-3、功能 80-4、返回值 …...

神经网络中的激活函数举例,它们各自的特点,以及哪个激活函数效果更好,为什么

sigmoid&#xff1a; \(\sigma(x)1/(1e^{-x})\)&#xff1b; 优&#xff1a;将数值压缩到 0 1&#xff0c;导数为 \(\sigma(x)(1-\sigma(x))\) 好算。劣&#xff1a;输出均值非0&#xff08;0.5&#xff09;&#xff0c;梯度消失&#xff08;Gradient vanishing&#xff09;每次…...

【树莓派3B+】控制引脚输出高低电平

前言一、安装RPI.GPIO库二、编写简单的输出高低电平的程序三、运行程序总结 前言 首先检查一下自己的板子有没有带库 我这个是有的。 ok&#xff0c;正式进入步骤 一、安装RPI.GPIO库 如果还没有安装RPi.GPIO库&#xff0c;可以通过以下命令在树莓派上安装&#xff1a; p…...

【Redis7】高阶篇

1 Redis单线程 VS 多线程(入门篇) 1.1 面试题 redis到底是单线程还是多线程&#xff1f; IO多路复用听说过吗&#xff1f; redis为什么快&#xff1f; 1.2 Redis为什么选择单线程&#xff1f; 1.2.1 是什么 这种问法其实并不严谨&#xff0c;为啥这么说呢? Redis的版本…...

在学习使用LabVIEW的过程中,需要注意哪些问题?

在学习使用LabVIEW的过程中&#xff0c;需要注意以下问题&#xff1a; 1. 基础知识 图形化编程思维&#xff1a; LabVIEW采用图形化编程方式&#xff0c;与传统的文本编程语言有很大不同&#xff0c;需要适应这种新的编程思维方式。数据流概念&#xff1a; 理解LabVIEW的核心数…...

网络编程-TCP/IP

网络概述 网络采用分而治之的方法设计&#xff0c;将网络的功能划分为不同的模块&#xff0c;以分层的形式有机组合在一起。 每层实现不同的功能&#xff0c;其内部实现方法对外部其他层次来说是透明的。每层向上层提供服务&#xff0c;同时使用下层提供的服务 网络体系结构…...

使用VSCode开发Django指南

使用VSCode开发Django指南 一、概述 Django 是一个高级 Python 框架&#xff0c;专为快速、安全和可扩展的 Web 开发而设计。Django 包含对 URL 路由、页面模板和数据处理的丰富支持。 本文将创建一个简单的 Django 应用&#xff0c;其中包含三个使用通用基本模板的页面。在此…...

基于距离变化能量开销动态调整的WSN低功耗拓扑控制开销算法matlab仿真

目录 1.程序功能描述 2.测试软件版本以及运行结果展示 3.核心程序 4.算法仿真参数 5.算法理论概述 6.参考文献 7.完整程序 1.程序功能描述 通过动态调整节点通信的能量开销&#xff0c;平衡网络负载&#xff0c;延长WSN生命周期。具体通过建立基于距离的能量消耗模型&am…...

【Zephyr 系列 10】实战项目:打造一个蓝牙传感器终端 + 网关系统(完整架构与全栈实现)

🧠关键词:Zephyr、BLE、终端、网关、广播、连接、传感器、数据采集、低功耗、系统集成 📌目标读者:希望基于 Zephyr 构建 BLE 系统架构、实现终端与网关协作、具备产品交付能力的开发者 📊篇幅字数:约 5200 字 ✨ 项目总览 在物联网实际项目中,**“终端 + 网关”**是…...

SpringTask-03.入门案例

一.入门案例 启动类&#xff1a; package com.sky;import lombok.extern.slf4j.Slf4j; import org.springframework.boot.SpringApplication; import org.springframework.boot.autoconfigure.SpringBootApplication; import org.springframework.cache.annotation.EnableCach…...

如何理解 IP 数据报中的 TTL?

目录 前言理解 前言 面试灵魂一问&#xff1a;说说对 IP 数据报中 TTL 的理解&#xff1f;我们都知道&#xff0c;IP 数据报由首部和数据两部分组成&#xff0c;首部又分为两部分&#xff1a;固定部分和可变部分&#xff0c;共占 20 字节&#xff0c;而即将讨论的 TTL 就位于首…...

人机融合智能 | “人智交互”跨学科新领域

本文系统地提出基于“以人为中心AI(HCAI)”理念的人-人工智能交互(人智交互)这一跨学科新领域及框架,定义人智交互领域的理念、基本理论和关键问题、方法、开发流程和参与团队等,阐述提出人智交互新领域的意义。然后,提出人智交互研究的三种新范式取向以及它们的意义。最后,总结…...

C++.OpenGL (20/64)混合(Blending)

混合(Blending) 透明效果核心原理 #mermaid-svg-SWG0UzVfJms7Sm3e {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-SWG0UzVfJms7Sm3e .error-icon{fill:#552222;}#mermaid-svg-SWG0UzVfJms7Sm3e .error-text{fill…...

虚拟电厂发展三大趋势:市场化、技术主导、车网互联

市场化&#xff1a;从政策驱动到多元盈利 政策全面赋能 2025年4月&#xff0c;国家发改委、能源局发布《关于加快推进虚拟电厂发展的指导意见》&#xff0c;首次明确虚拟电厂为“独立市场主体”&#xff0c;提出硬性目标&#xff1a;2027年全国调节能力≥2000万千瓦&#xff0…...

python爬虫——气象数据爬取

一、导入库与全局配置 python 运行 import json import datetime import time import requests from sqlalchemy import create_engine import csv import pandas as pd作用&#xff1a; 引入数据解析、网络请求、时间处理、数据库操作等所需库。requests&#xff1a;发送 …...

嵌入式常见 CPU 架构

架构类型架构厂商芯片厂商典型芯片特点与应用场景PICRISC (8/16 位)MicrochipMicrochipPIC16F877A、PIC18F4550简化指令集&#xff0c;单周期执行&#xff1b;低功耗、CIP 独立外设&#xff1b;用于家电、小电机控制、安防面板等嵌入式场景8051CISC (8 位)Intel&#xff08;原始…...