优化dp贪心数论
这次三个题目都来自牛客周赛93，个人觉得出的很好，收获颇多。
1.简单贪心
题目意思：
任意选定两个数字，相加之和替代两个数字中的一个，另一个抹除。求操作之后最大字典序之和
思路：
最大字典序之和，给我们启发，第一个数字一定是最大的，所以再有限的k次操作中我们将除了数组中第一个数字之外，其他数字排序后的前k个数加入到第一个数字宜为最优方案。
特殊情况：
3 2 1 2 4 当k等于2的时候，该数组变成了下面这种
7 2 1 2，此时，后面最大的数字是2，那么这里就有两个方案（选择第一个，选择第二个）
第一个情况下：9 1 2
第二个情况下：9 2 1
不难看出当有重复数字出现的时候，我们选择最后一个数字宜为最优方案。（毕）
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define P pair<int,int>
const int op=2e5+5;
void solve() {int n, k;cin >> n >> k;vector<int> a(n + 1);priority_queue<P> answer;//优先队列for(int i = 1; i <= n; i++) {cin >> a[i];if(i > 1) {answer.emplace(a[i], i);//加入除了第一个数的所有数字}}vector<int> vis(n + 1, 0);while(k--) {auto [val, id] = answer.top();answer.pop();//当val相等的时候，优先队列会将id比较大的那一个拿出来，也就是我们说的有多个数相等的时候取出最靠后的数字a[1] += val;vis[id] = 1;}for(int i = 1; i <= n; i++) {if(!vis[i]) {cout << a[i] << " ";}}cout << endl;
}signed main() {int t = 1;cin>>t;while(t--) solve();return 0;
}2.数论
题目意思：
给定一个数组求出非空子序列下，有多少个子序列满足Mex(S)>=Max(S)-Min(S)
思路：
第一考虑选择一个数的情况下（也就是说子序列里面只有1个可重复数字）
例如（1 1 1 ）和（1）假设cnt[i]=k表示的是i数字有k个，那么方案数就是pow(2,k)-1（这里-1排除的是空的情况）
第二考虑多个数字情况下（0(若干个)，1（若干个），2（若干个）....x（若干个））此时在这种情况Mex(S)>=Max(S)-Min(S)才成立。
假设中间缺了一个数字C，那么x（Max）-0（Min）一定是小于C的。
于是我们从0开始找到第一个没有出现的数字（假设是d）那么答案就是在（0(若干个)，1（若干个），2（若干个）....d（若干个））中，此时的方案数和第一考虑的类似为：
[pow(2,cnt[0])-1]*[pow(2,cnt[1])-1]...*[pow(d,cnt[d])-1]
当然类似的，d-1也成立，于是：
[pow(2,cnt[0])-1]*[pow(2,cnt[1])-1]...*[pow(d-1,cnt[d-1])-1]
一直到0为止。
把第一考虑和第二考虑所有的方案数加在一起就是答案。（毕）
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int mod=1e9+7;
int nima(int a,int b){int sum=1;while(b){if(b&1){sum=(a*sum)%mod;}a=(a*a)%mod;b>>=1;}return sum;//打一个快速幂
}
signed main(){int n;cin>>n;vector<int>cnt(n+1);for(int i=1,x;i<=n;i++){cin>>x;cnt[x]++;//统计每一个数的个数}int ans=0;int s=1;for(int i=0;i<=n;i++){if(cnt[i]==0)break;//i这个数字不存在的时候就直接跳过，因为不连续了s*=nima(2ll,cnt[i])-1+mod;s%=mod;//s表示的是第i个子序列的方案数ans+=s;ans%=mod;}for(int i=1;i<=n;i++){//因为第0个已经在上面计算过了，后面我们直接从1开始计算ans+=(nima(2ll,cnt[i])-1+mod);ans%=mod;}cout<<ans<<endl;
}3.优化dp问题
题目意思：
计算所有从第一行到第n行构成字符串中回文的数量。
思路：
暴力情况下我们进行思维dp[i1][j1][i2][j2]，考虑是回文，我们从金字塔的中间开始往上往下进行同步跑，[i1][j1]表示的是向上的第i1行，第j1列，同理[i2][j2]表示的是向下的第i2列，第j2列。
但是由于n的范围比较大500，TLE，且MLE掉了。
继续优化，考虑到i1和i2到中间的距离一定是相等的，我们可以通过d来表示到中间的距离dp[d][j1][j2]。
该优化条件下TLE是不会了，但是如果常熟处理不好的情况下，还是会MLE的。
所以我们进行再次优化，考虑到赋值的情况下d+1的方案数只能是从d叠加过来的，故我们可以用&符号来进行滚动赋值。至此优化dp全部进行完毕。但是在滚动赋值的情况下，我们要清空上一个内容值。
细节：当n是偶数的情况下，我们对dp[0][j][j]进行初始化赋值，当n是奇数的情况下，我们只要对中间的那一行全部赋值1。
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int op=1e9+7;
signed main() {int n;cin >> n;int a[501][501];for (int i = 1; i <= n; i++)for (int j = 1; j <= i; j++) {cin >> a[i][j];int ans = 0;vector<vector<vector<int>>> dp(2, vector<vector<int>>(n + 3, vector<int>(n + 3)));//dp的初始化dp[2][501][501]if (n % 2 == 0) {//偶数的情况for (int j = 1; j <= n / 2; j++) {//对中间两行进行初始化if (a[n / 2][j] == a[n / 2 + 1][j]) {dp[0][j][j]++;}if (a[n / 2][j] == a[n / 2 + 1][j + 1]) {dp[0][j][j + 1]++;}}int m1 = n / 2, m2 = n / 2 + 1;//m1往上进行变量，m2往下进行遍历for (int d = 1; d <= n / 2 - 1; d++) {////这里就是滚动赋值的情况下，要将上一个状态清空for (int j = 1; j <= n; j++) {for (int k = 1; k <= n; k++) {dp[d & 1][j][k] = 0;}}for (int j = 1; j <= n; j++) {for (int k = 1; k <= n; k++) {if (a[m1 - d][j] == a[m2 + d][k]) {//当上下两个数字都相同的时候，可以进行dp转移//偶数的情况和期数的情况有点不同dp[d & 1][j][k] += dp[(d - 1) & 1][j][k];//根据题目所说一共有4种方案数的转移dp[d & 1][j][k] += dp[(d - 1) & 1][j + 1][k];dp[d & 1][j][k] += dp[(d - 1) & 1][j][k - 1];dp[d & 1][j][k] += dp[(d - 1) & 1][j + 1][k - 1];dp[d & 1][j][k] %= op;}}}}for (int j = 1; j <= n; j++) {////最后求第1行n个数字的所有方案数即可ans += dp[(n / 2 - 1) & 1][1][j];ans %= op;}cout << ans << endl;} else {int m = n / 2 + 1;for (int j = 1; j <= m; j++) {dp[0][j][j]++;}//奇数情况只要对中间的那一行进行赋值for (int d = 1; d <= n / 2; d++) {for (int j = 1; j <= n; j++) {for (int k = 1; k <= n; k++) {dp[d & 1][j][k] = 0;}}//这里和偶数的情况是一样的for (int j = 1; j <= n; j++) {for (int k = 1; k <= n; k++) {if (a[m - d][j] == a[m + d][k]) {dp[d & 1][j][k] += dp[(d - 1) & 1][j][k];dp[d & 1][j][k] += dp[(d - 1) & 1][j + 1][k];dp[d & 1][j][k] += dp[(d - 1) & 1][j][k - 1];dp[d & 1][j][k] += dp[(d - 1) & 1][j + 1][k - 1];dp[d & 1][j][k] %= op;}}}}for (int j = 1; j <= n; j++) {ans += dp[(n / 2) & 1][1][j];ans %= op;}cout << ans << endl;}}
}相关文章：
优化dp贪心数论
这次三个题目都来自牛客周赛93，个人觉得出的很好，收获颇多。 1.简单贪心 题目意思： 任意选定两个数字，相加之和替代两个数字中的一个，另一个抹除。求操作之后最大字典序之和 思路： 最大字典序之和&…...
详解MySQL 的 binlog，redo log，undo log
MySQL 的 binlog、redo log 和 undo log 是数据库事务处理与数据一致性的核心组件，各自承担不同的职责。 1. binlog（二进制日志） 定位：MySQL Server 层实现的逻辑日志，与存储引擎无关。作用： 主从复制&…...
SymPy|主元、重新表示、分数、约分表达式、极限、级数、ode、获取值、输出形式
SymPy 是一个 Python 的符号计算库，广泛应用于数学计算、物理建模、工程分析等领域。本文将详细介绍 SymPy 在处理主元操作、重新表示、分数、约分表达式、极限、级数、常微分方程（ODE）以及获取值和输出形式等方面的应用，通过完整…...
Java 05正则表达式
正则表达式 1.简介 一个字符串，指定一些规则，来校验其他的字符串 String s"";规则 需要进行匹配的字符串.matches(s);来判断2.字符类**（单个） [abc] String s"[ABC]"; "A".matches(s);返回true…...
IEEE 802.1Q协议下封装的VLAN数据帧格式
1.概要 802.1d定义了生成树 802.1w定义了快速生成树 802.1s定义了多生成树 802.1q定义了VLAN 2.说明 IEEE802.1q协议的作用是（生成VLAN标记）VLAN编号取值范围：0-4095，其中0和4095是保留编号，所最大值是ÿ…...
VMware三种网络配置对比
桥接模式（Bridged Mode） 核心特点： 虚拟机被视为局域网中的独立设备，直接使用物理网络适配器，需配置与宿主机同一网段的IP地址。 典型场景： 虚拟机需对外提供服务（如Web…...
再来1章linux系列-19 防火墙 iptables 双网卡主机的内核 firewall-cmd firewalld的高级规则
学习目标： 实验实验需求实验配置内容和分析 （每一个设备的每一步操作）实验结果验证其他 学习内容： 实验实验需求实验配置内容和分析 （每一个设备的每一步操作）实验结果验证其他 1.实验 2.实验需求 图…...
Word 转 HTML API 接口
Word 转 HTML API 接口 图像/转换 Word 文档转换为 HTML 文件转换 / 超高精度与还原度 文件转换 / Word。 1. 产品功能 超高精度与还原度的 HTML 文件转换；支持将 Word 文档转换为 HTML 格式；支持 .doc 和 .docx 格式；保持原始 Word 文档的…...
深入解析MATLAB codegen生成MEX文件的原理与优势
一、MATLAB codegen底层工作机制 1.1 MATLAB执行引擎的局限性 MATLAB作为解释型语言，其执行过程包含多个关键步骤： 语法解析：将.m文件代码转换为抽象语法树(AST) 类型推断：运行时动态确定变量类型 内存管理：自动处…...
PEFT简介及微调大模型DeepSeek-R1-Distill-Qwen-1.5B
🤗 PEFT（参数高效微调）是由Huggingface团队开发的开源框架，专为大型预训练模型（如GPT、LLaMA、T5等）设计，用于高效地将大型预训练模型适配到各种下游应用，而无需对模型的所有参数进行…...
Python训练营打卡 Day31
文件的规范拆分和写法 今日的示例代码包含2个部分 notebook文件夹内的ipynb文件，介绍下今天的思路项目文件夹中其他部分：拆分后的信贷项目，学习下如何拆分的，未来你看到的很多大项目都是类似的拆分方法 知识点回顾：文件…...
Google精准狙击OpenAI Codex，发布AI编程助手Jules！
自从OpenAI推出 Codex之后，Google就憋不住了，悄悄得瞄准了OpenAI的最新成果。 原计划是是打算在明天举行的Google I/O年度开发者大会上发布相关产品，但Google似乎已经一刻也等不了了。 就在昨天，谷歌正式推出了其AI编程——Ju…...
【办公类-18-04】（Python）“验血单信息”批量生成打印（学校、班级、姓名、性别）
背景说明 督导结束了，准备春游（夏游），搭档在给孩子写打卡单、心愿单，感慨“好多字都不会写了！” 此时，保健老师来发体检材料，叮嘱红色验血单的填写方法。 我觉得我的字也是一塌糊涂。我想用以前做“毕业证书”的方式，将班级幼儿信息打印在体检单上。 【办公类-18-03…...
如何使用通义灵码提高前端开发效率
工欲善其事，必先利其器。对于前端开发而言，使用VSCode已经能够极大地提高前端的开发效率了。但有了AI加持后，前端开发的效率又更上一层楼了！ 本文采用的AI是通义灵码插件提供的通义千问大模型，是目前AI性能榜第一梯队…...
苍穹外卖04 新增菜品菜品分页查询删除菜品修改菜品
2-6 新增菜品 02 05-新增菜品_需求分析和设计 03 06-新增菜品_代码开发_1 文件上传接口开发： 在这一部分我们主要在于对阿里云oss的代码开发和实现 1.配置阿里云oss： alioss:endpoint: oss-cn-beijing-internal.aliyuncs.comaccess-key-id: access-ke…...
C++ 读取英伟达显卡名称、架构及算力
C++ 读取英伟达显卡名称、架构及算力 通过CUDA Runtime API获取计算能力（推荐）CUDA计算能力（Compute Capability）的版本号直接对应显卡架构（如8.6=Ampere，9.0=Hopper）。实现步骤： 1.安装依赖： 安装 NVIDIA CUDA Toolkit。确保显卡驱动支持CUDA。2. C…...
VitePress 中以中文字符结尾的字体加粗 Markdown 格式无法解析
背景 在编写vitepress项目过程中，发现了一个markdown格式解析的问题。 md文件中，以中文句号结尾的字体加粗，无法正确解析： 不只是中文句号，只要是加粗语句中以中文字符结尾，都无法被正确解析 需要将中文…...
2.前端汇总
框架 html5 html语法 css css3 css语法 框架 tailwind css 官网 JavaScript JavaScript语法 typescript 语法 nodejs 语法 vue3 官网 组件 vite 打包 vue router -路由 pinia - 状态管理 ui element plus axios - ajax 后台管理系统前端快速开发框架 …...
外部因素导致的 ADC误差来源分析
前面分享了ADC自身因素带来的误差，现在再分享一波由于外部因素导致的ADC采样误差。 一、模拟信号源输入减少带来的误差 看一个STM32的ADC转换器的示意图： 从图中可以看到，输入源与采样引脚之间存在阻抗RAIN，流入引脚的电压可能因…...
集成运算放大器知识汇总
一、集成运放的组成 集成运算放大器，就是通过内部元器件的电参量关系将电参量进行运算，达到放大的目的。我们拆解来看： 集成：将电路封装，留出接口，使其模块化，便于移植。运算：这里…...
)
HBCPC2025 补题 （F、I)
HBCPC2025 补题 补题连接:Codeforces I 感染 做法1：std做法：树上dp统计贡献找最大 #include <bits/stdc.h> using namespace std; typedef long long ll; #define endl \n #define int long long #define pb push_back #define pii pair<int,…...
针对 CSDN高质量博文发布 的详细指南
结合技术写作规范与平台特性，分为 内容规划、写作技巧、排版优化、发布策略 四部分，确保专业性与传播效果： 一、内容规划：精准定位与深度挖掘 选题策略 热点结合：追踪技术趋势（如2025年AIGC、量子计算&am…...
python读写bin文件
import numpy as np# 创建二进制数据 data np.array([0x33, 0x34, 0x35, 0x36], dtypenp.uint8)# 写入bin文件 with open(example.bin, wb) as f:data.tofile(f)print("bin文件生成成功")data np.fromfile(example.bin, dtypenp.uint8) print("numpy读取结果:…...
矩阵的秩（Rank）
矩阵的秩（Rank）是线性代数中的核心概念，表示矩阵中线性无关的行（或列）的最大数量，反映了矩阵所包含的“独立信息”的多少。以下是其核心要点： 1. 秩的定义 行秩：矩阵中线性无关的行…...
Vue响应式系统演进与实现解析
一、Vue 2 响应式实现详解 1. 核心代码实现 // 依赖收集器（观察者模式） class Dep {constructor() {this.subscribers new Set();}depend() {if (activeEffect) {this.subscribers.add(activeEffect);}}notify() {this.subscribers.forEach(effect &g…...
【SPIN】高级时序规范（SPIN学习系列--6）
时序操作符[]（总是）和 <>（最终）可应用于任何LTL公式，因此 []<><>A 和 <>[]<>(A ∧ []B) 在语法上是正确的。本书不涉及LTL的演绎理论（如公理、推理规则及公式的结合律、交换…...
C语言学习之内存函数
今天我们来学习一下C语言中内存函数 以下内存函数的使用均需要包含头文件<string.h> 目录 memcpy函数的使用及其模拟实现 memcpy函数的模拟实现 memmove函数的使用和模拟实现 memmove函数的模拟实现 memset函数的使用 memcmp函数的使用 memcpy函数的使用及其模拟实现…...
Python 数据库编程
一、数据库连接基础 1. 标准流程 import database_module # 如mysql.connector, sqlite3等 # 1. 建立连接 connection database_module.connect( host"localhost", user"username", password"password", database"dbnam…...
软考软件评测师——软件工程之开发模型与方法
目录 一、核心概念 二、主流模型详解 （一）经典瀑布模型 （二）螺旋演进模型 （三）增量交付模型 （四）原型验证模型 （五）敏捷开发实践 三、模型选择指南 四…...
机器学习入门
机器学习入门 1 . 机器学习是什么？ 机器学习（Machine Learning, ML）是一种用数据经验替代显式规则编程来完成任务的方法──模型从样本 (X, y) 中学习 映射函数 f: X → Y，并在新样本上做出预测。和传统“if … else”程序相比&…...
git学习与使用（远程仓库、分支、工作流）
文章目录 前言简介git的工作流程git的安装配置git环境：git config --globalgit的基本使用新建目录初始化仓库（repository）添加到暂存区新增/修改/删除 文件状态会改变 提交到仓库查看提交（commit）的历史记录git其他命令…...
制造业或跨境电商相关行业三种模式：OEM、ODM、OBM
一、基础概念对比 模式定义核心能力利润来源控制权OEM代工生产（贴牌生产）纯生产制造能力加工费（薄利）品牌方掌控一切ODM设计生产（自主设计代工）设计研发能力设计溢价生产利润制造商掌握设计OBM自主品牌&am…...
APPtrace 智能参数系统：重构 App 用户增长与运营逻辑
一、免填时代：APPtrace 颠覆传统参数传递模式 传统 App 依赖「邀请码 / 手动绑定」实现用户关联，流程繁琐导致 20%-30% 的用户流失。APPtrace 通过 **「链接参数自动传递 安装后智能识别」** 技术，让用户在无感知状态下完成关系绑定、场景还…...
在 Excel 中使用 C# .NET 用户定义函数 操作步骤
点开选项 点击加载项 点击跳转 点击浏览 选择仙盟excel...
PyTest
一、基本用法: 1.测试框架做了什么: (1).测试发现 a.创建test_开头的文件 b.创建Test开头的类 c.创建test_开头的函数或方法 pytest中以每一个函数或方法作为一个用例 pytest主要以名字区分普通函数(方法)、用例 pytest的启动方式:在给定的项目中执行pytest命令即可 p…...
Python Day27 学习
今天学习讲义Day17的内容：无监督算法中的聚类浙大疏锦行 Q1. 什么是聚类？ 本质上就是一种分组分类 关于聚类的准备工作： 代码实现 # 先运行之前预处理好的代码 import pandas as pd import pandas as pd #用于数据处理和分析ÿ…...
在 Win 10 上，Tcl/Tk 脚本2个示例
set PATH 新增 D:\Git\mingw64\bin where tclsh D:\Git\mingw64\bin\tclsh.exe where wish D:\Git\mingw64\bin\wish.exe 编写 test_tk.tcl 如下 #!/usr/bin/tclsh # test 文件对话框 package require Tk# 弹出文件选择对话框，限制选择.txt文件 set filePath […...
渐开线少齿差传动学习笔记
之前看到了一个渐开线一齿差的视频，觉得比较有意思，想自己动手做一个看看，下面是最开始尝试的一个失败的结果，不知道小伙伴们发现问题了没？ 本来就是想凑一凑看看，但是发现不是凑起来不是件容易的事。那么…...
基于CATIA参数化圆锥建模的自动化插件开发实践——NX建模之圆锥体命令的参考与移植（二）
引言 在CATIA二次开发领域，参数化建模技术可提升复杂几何体的创建效率达60%。本文基于PySide6 GUI框架与pycatia接口库，深度解析锥体自动化建模工具的开发实践。该工具创新性地融合了NX的交互逻辑与CATIA的混合建模技术，实现双模式输入（高度/锥角）的智能参数转换，较传统…...
Java集合框架详解：单列集合与双列集合
目录 1. 引言：为什么需要集合框架 2. 基础概念：集合框架概述 2.1 集合框架的结构 编辑 编辑 2.2 集合与数组的比较 3. 前置知识：理解集合框架背后的基础数据结构 3.1 数组 3.2 链表 3.3 哈希表 3.4 二叉树与二叉查找树 3.5 红…...
leetcode 33. Search in Rotated Sorted Array
题目描述 可以发现的是，将数组从中间分开成左右两部分的时候，一定至少有一部分的数组是有序的。左部分[left,mid-1]，右部分[mid1,right]。 第一种情况：左右两部分都是有序的，说明nums[mid]就是整个数组的最大值。此时…...
OpenCV 图像色彩空间转换
一、知识点: 1、色彩空间转换函数 (1)、void cvtColor( InputArray src, OutputArray dst, int code, int dstCn 0, AlgorithmHint hint cv::ALGO_HINT_DEFAULT ); (2)、将图像从一种颜色空间转换为另一种。 (3)、参数说明: src: 输入图像，即要进行颜…...
python-leetcode 69.最小栈
题目： 设计一个支持push,pop,top,操作，并能在常数时间内检索到最小元素的栈。 辅助栈法： 1：使用两个栈，一个主栈用于存储所有元素，另一个辅助栈用于存储当前元素的最小值 2: 每次push时，将元…...
C#基础：yield return关键字的特点
一、特点 1.最终返回的结果是IEnumerable<T> 2.使用yield return时，返回的是单个元素（即T） 3.好处：延迟加载，需要时才计算 二、验证 通过打断点可知，只有当listB遍历的时候，才会进入Get…...
机器学习 集成学习方法之随机森林
集成学习方法之随机森林 1 集成学习2 随机森林的算法原理2.1 Sklearn API2.2 示例 1 集成学习 机器学习中有一种大类叫集成学习（Ensemble Learning），集成学习的基本思想就是将多个分类器组合，从而实现一个预测效果更好的集成分类…...
【Vue篇】组件的武林绝学：状态风暴下的乾坤挪移术
引言 🔍 Vue组件迷雾重重？ ✧ Scoped如何实现样式隔离？ ✧ Data为何必须是函数？ ✧ 父子组件如何跨域通信？ ✧ Props单向数据流如何破局？ 🚀 本文直击组件化七大核心： ▸ 样式隔离原…...
使用亮数据代理IP+Python爬虫批量爬取招聘信息训练面试类AI智能体（手把手教学版）
文章目录 一、为什么要用代理IP？(重要！！！)二、环境准备（三件套走起）2.1 安装必备库（pip大法好）2.2 获取亮数据代理（官网注册送试用） 三、编写爬虫代码&#x…...
【MySQL】第七弹——复习总结 视图
文章目录 🌏客户端和数据库操作🌏表操作🌏CRUD 增删改查总结🌏数据库约束🌏表的设计🌏分组查询🌏聚合函数🌏联合查询🌏SQL语句中各部分的执行顺序🪐视图 &…...
基于Springboot + vue3实现的工商局商家管理系统
项目描述 本系统包含管理员、商家两个角色。 管理员角色： 用户管理：管理系统中所有用户的信息，包括添加、删除和修改用户。 许可证申请管理：管理商家的许可证申请，包括搜索、修改或删除许可证申请。 许可证审批管理…...
前端开发——前端样式BUG调试全指南2025终极版
前端开发——前端样式BUG调试全指南2025终极版 前端样式BUG调试指南（2025终极版）一、调试方法论与工具链1. 问题定位三板斧(1) 现象复现与特征提取(2) 现代调试工具组合拳(3) 三维问题定位法 2. 深度排查六步法步骤1：样式覆盖检测步骤2&#…...