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

LeeCode 1787 DP

题意

传送门 LeeCode 1787 使所有区间的异或结果为零

题解

任一个元素都至多对 k k k个长度为 k k k的区间产生影响,故难以直接依次处理每一个元素。

观察到满足条件的数组中模 k k k意义下索引相等的各个元素相同,故可以依次处理每一个同余类。 d p [ i ] [ j ] dp[i][j] dp[i][j]表示前 i i i个同余类异或结果为 j j j情况下的最小更改元素数。直接枚举每一种取值,时间复杂度 O ( n 2 20 ) O(n2^{20}) O(n220),难以胜任。设同余类 i i i元素规模为 m m m,则至多改动 m m m个元素,则可以从任一个状态转移过来,那么贪心地选择改动数量最少的状态即可。对于出现在同余类中的取值,直接暴力枚举即可。总时间复杂度 O ( n 2 10 ) O(n2^{10}) O(n210)

#include <bits/stdc++.h>
using namespace std;class Solution {public:int minChanges(vector<int>& nums, int k) {vector<map<int, int>> cnt(k);vector<int> num(k);int n = nums.size();for (int i = 0; i < n; ++i) {num[i % k] += 1;cnt[i % k][nums[i]] += 1;}auto _min = [](int& x, int y) {x = min(x, y);};const int lg = 10;const int inf = 1e9;vector<vector<int>> dp(k + 1, vector<int>(1 << lg, inf));dp[0][0] = 0;for (int i = 0; i < k; ++i) {int m = num[i];int p = min_element(dp[i].begin(), dp[i].end()) - dp[i].begin();for (int j = 0; j < 1 << lg; ++j) {for (auto& [x, c] : cnt[i]) {_min(dp[i + 1][j], dp[i][j ^ x] + m - c);}_min(dp[i + 1][j], dp[i][p] + m);}}return dp[k][0];}
};

相关文章:

LeeCode 1787 DP

题意 传送门 LeeCode 1787 使所有区间的异或结果为零 题解 任一个元素都至多对 k k k个长度为 k k k的区间产生影响&#xff0c;故难以直接依次处理每一个元素。 观察到满足条件的数组中模 k k k意义下索引相等的各个元素相同&#xff0c;故可以依次处理每一个同余类。 d p…...

如何有效屏蔽手机上的骚扰电话20240530

如何有效屏蔽手机上的骚扰电话 引言 最近&#xff0c;我的手机经常接到954开头的7位数字座机电话&#xff0c;这些骚扰电话让我非常困扰。由于我经常点外卖&#xff0c;无法屏蔽所有陌生号码&#xff0c;因此需要一个既能屏蔽特定前缀的骚扰电话&#xff0c;又不影响日常生活…...

Linux CGroup资源限制(概念限制进程CPU使用)

Linux CGroup资源限制&#xff08;详解&#xff09; 最近客户认为我们程序占用cpu过高&#xff0c;希望我们限制&#xff0c;排查之后发现是因为程序频繁gc导致&#xff0c;为了精细化、灵活的的限制&#xff0c;想到了使用Linux CGroup。 0 前置知识 ①概念及作用 官网&#…...

Latex中标注通讯作者

** 直接使用脚注&#xff0c;不用添加宏包 多个同地址的并列&#xff0c;建议加点空格&#xff0c;好看一些 ** \title{xxxxxxxxxxxxxxxxxxx}\author{xxxxxxxxxxxxxxxxxxx\footnote{Corresponding author} ,bbbbbbbbbbbbbbbbbbb}\address{xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx…...

PyQt5开发笔记:1.环境搭建与界面美化

推荐视频教程&#xff1a; https://www.bilibili.com/video/BV1LT4y1e72X?p23&vd_source7ab611f3afb3d469faad93d3996f99ba 一、打开网址&#xff0c;点击下载 https://build-system.fman.io/qt-designer-download 下载后&#xff0c;点开exe 不推荐&#xff1a;http…...

公派/自费访问学者申请出国访学的常见问题解答(下)

06、学术背景和研究成果要求&#xff1f; 访学是面向学术单位和企事业单位开放的。 针对学术单位&#xff0c;比如高校与科研院所&#xff0c;学科内涉及的论文发表&#xff0c;课题研究&#xff0c;专利&#xff0c;著作&#xff0c;含金量较高的奖项等背景都是国外比较看重…...

完全指南:C语言学习资源汇总

C语言是编程学习的基石&#xff0c;无论是为了职业发展还是个人兴趣&#xff0c;掌握C语言都是技术生涯的重要一步。为了帮助初学者和有经验的程序员更好地学习和深化对C语言的理解&#xff0c;我们汇总了一系列优秀的书籍和在线资源。这些资源将帮助你从基础知识到高级概念&am…...

Kubernetes——Ingress详解

目录 前言——Service策略的作用 1.外部访问方案 2.使用场景和限制 2.1NodePort 2.2LoadBalancer 2.3externalIPs 2.4Ingress 3.Ingress如何实现对外服务 4.LB和Ingress结合起来实现对外服务的过程 一、Ingress 1.定义 2.组成 3.工作原理 4.总结 二、部署Nginx-I…...

反射、类加载、静态代理,jdk动态代理,cglib代理

一、 反射 反射是在程序运行状态下&#xff0c;动态获取类的结构&#xff08;属性&#xff0c;构造器&#xff0c;方法&#xff0c;注解&#xff09;&#xff0c;动态的创建类对象然后调用类中的属性方法。反射的起源Class&#xff0c;Class中包含类反射要使用的API 获取Class的…...

MySQL Hints:控制查询优化器的选择

码到三十五 &#xff1a; 个人主页 MySQL Hints是优化数据库查询性能的一种强大工具。它们允许开发者在SQL查询中嵌入指令&#xff0c;以影响MySQL优化器的决策过程。在某些情况下&#xff0c;优化器可能无法选择最佳的查询执行计划&#xff0c;这时我们可以使用Hints来引导优化…...

【TB作品】msp430g2553单片机,OLED,PCF8591,ADC,DAC

硬件 OLED PCF8591 /** OLED* VCC GND* SCL接P2^0* SDA接P2^1*//** PCF8591* VCC GND* SCL接P1^4* SDA接P1^5*//* 板子上按键 P1.3 *//* 单片机ADC输入引脚 P1.1 *//* 说明&#xff1a;将PCF8591的DAC输出接到单片机ADC输入引脚 P1.1&#xff0c;单片机采集电压并显示 */功能…...

C#WPF数字大屏项目实战10--不良指标分页

1、区域划分 2、区域布局 3、视图模型 4、控件绑定 5、运行效果 走过路过&#xff0c;不要错过&#xff0c;欢迎点赞&#xff0c;收藏&#xff0c;转载&#xff0c;复制&#xff0c;抄袭&#xff0c;留言&#xff0c;动动你的金手指&#xff0c;财务自由...

数字塔问题

#include<iostream> using namespace std; //从下向上得到最优值 void dtower(int a[][100],int s[][100],int n) {for(int in; i>1; i--){for(int j1; j<i; j){if(in)s[i][j]a[i][j];else{int ts[i1][j];if(t<s[i1][j1])ts[i1][j1];s[i][j]a[i][j]t;}}} } void…...

【介绍下Pwn,什么是Pwn?】

&#x1f308;个人主页: 程序员不想敲代码啊 &#x1f3c6;CSDN优质创作者&#xff0c;CSDN实力新星&#xff0c;CSDN博客专家 &#x1f44d;点赞⭐评论⭐收藏 &#x1f91d;希望本文对您有所裨益&#xff0c;如有不足之处&#xff0c;欢迎在评论区提出指正&#xff0c;让我们共…...

Python:b站多个视频爬取下载

&#x1f4da;博客主页&#xff1a;knighthood2001 ✨公众号&#xff1a;认知up吧 &#xff08;目前正在带领大家一起提升认知&#xff0c;感兴趣可以来围观一下&#xff09; &#x1f383;知识星球&#xff1a;【认知up吧|成长|副业】介绍 ❤️如遇文章付费&#xff0c;可先看…...

Java常规题技术分享

一、数组排序和添加成员 设计类Student和类StudentClass。 (1) 类Student有字符串属性name、double属性grade和int属性age 有带参数的构造方法&#xff0c;可设置三个属性的值 有各个属性的置取方法 (2)类StudentClass有Student数组属性stus存放班级成员&#xff0c;有int…...

Pytorch语义分割(1)-----加载数据

在语义分割中用到的数据无非就是原始图片&#xff08;image&#xff09;和标注后得到的mask图片&#xff0c;所以在读取数据的时候只要返回图片和标签信息就OK 了。 import torch import os import numpy as np from torch.utils.data import Dataset from utils_func import …...

Java中加号的多种用途

在Java中&#xff0c; 符号有多种用途&#xff0c;主要根据上下文而定。以下是在Java中的一些主要用途&#xff1a; 加法运算符&#xff1a; 这是最常见的用途&#xff0c;用于数字相加。 int a 5;int b 3;int sum a b; // sum is 8 字符串连接符&#xff1a; 当用…...

React useCallback用法

useCallback 是 React 中的一个 Hook&#xff0c;它用于优化性能&#xff0c;通过缓存函数的引用来避免在组件的每次渲染时都创建新的函数实例。这对于避免不必要的子组件重新渲染特别有用&#xff0c;因为如果传递给子组件的回调函数在每次渲染时都不同&#xff0c;即使子组件…...

Flutter 中的 ErrorWidget 小部件:全面指南

Flutter 中的 ErrorWidget 小部件&#xff1a;全面指南 Flutter 是一个由 Google 开发的跨平台 UI 框架&#xff0c;它允许开发者使用 Dart 语言构建高性能、美观的应用。在 Flutter 的丰富组件库中&#xff0c;ErrorWidget 是一个特殊的组件&#xff0c;用于在渲染过程中捕获…...

wordpress后台更新后 前端没变化的解决方法

使用siteground主机的wordpress网站&#xff0c;会出现更新了网站内容和修改了php模板文件、js文件、css文件、图片文件后&#xff0c;网站没有变化的情况。 不熟悉siteground主机的新手&#xff0c;遇到这个问题&#xff0c;就很抓狂&#xff0c;明明是哪都没操作错误&#x…...

shell脚本--常见案例

1、自动备份文件或目录 2、批量重命名文件 3、查找并删除指定名称的文件&#xff1a; 4、批量删除文件 5、查找并替换文件内容 6、批量创建文件 7、创建文件夹并移动文件 8、在文件夹中查找文件...

java 实现excel文件转pdf | 无水印 | 无限制

文章目录 目录 文章目录 前言 1.项目远程仓库配置 2.pom文件引入相关依赖 3.代码破解 二、Excel转PDF 1.代码实现 2.Aspose.License.xml 授权文件 总结 前言 java处理excel转pdf一直没找到什么好用的免费jar包工具,自己手写的难度,恐怕高级程序员花费一年的事件,也…...

Frozen-Flask :将 Flask 应用“冻结”为静态文件

Frozen-Flask 是一个用于将 Flask 应用“冻结”为静态文件的 Python 扩展。它的核心用途是&#xff1a;将一个 Flask Web 应用生成成纯静态 HTML 文件&#xff0c;从而可以部署到静态网站托管服务上&#xff0c;如 GitHub Pages、Netlify 或任何支持静态文件的网站服务器。 &am…...

相机从app启动流程

一、流程框架图 二、具体流程分析 1、得到cameralist和对应的静态信息 目录如下: 重点代码分析: 启动相机前,先要通过getCameraIdList获取camera的个数以及id,然后可以通过getCameraCharacteristics获取对应id camera的capabilities(静态信息)进行一些openCamera前的…...

NFT模式:数字资产确权与链游经济系统构建

NFT模式&#xff1a;数字资产确权与链游经济系统构建 ——从技术架构到可持续生态的范式革命 一、确权技术革新&#xff1a;构建可信数字资产基石 1. 区块链底层架构的进化 跨链互操作协议&#xff1a;基于LayerZero协议实现以太坊、Solana等公链资产互通&#xff0c;通过零知…...

IT供电系统绝缘监测及故障定位解决方案

随着新能源的快速发展&#xff0c;光伏电站、储能系统及充电设备已广泛应用于现代能源网络。在光伏领域&#xff0c;IT供电系统凭借其持续供电性好、安全性高等优势成为光伏首选&#xff0c;但在长期运行中&#xff0c;例如老化、潮湿、隐裂、机械损伤等问题会影响光伏板绝缘层…...

深入解析C++中的extern关键字:跨文件共享变量与函数的终极指南

&#x1f680; C extern 关键字深度解析&#xff1a;跨文件编程的终极指南 &#x1f4c5; 更新时间&#xff1a;2025年6月5日 &#x1f3f7;️ 标签&#xff1a;C | extern关键字 | 多文件编程 | 链接与声明 | 现代C 文章目录 前言&#x1f525;一、extern 是什么&#xff1f;&…...

全志A40i android7.1 调试信息打印串口由uart0改为uart3

一&#xff0c;概述 1. 目的 将调试信息打印串口由uart0改为uart3。 2. 版本信息 Uboot版本&#xff1a;2014.07&#xff1b; Kernel版本&#xff1a;Linux-3.10&#xff1b; 二&#xff0c;Uboot 1. sys_config.fex改动 使能uart3(TX:PH00 RX:PH01)&#xff0c;并让boo…...

分布式增量爬虫实现方案

之前我们在讨论的是分布式爬虫如何实现增量爬取。增量爬虫的目标是只爬取新产生或发生变化的页面&#xff0c;避免重复抓取&#xff0c;以节省资源和时间。 在分布式环境下&#xff0c;增量爬虫的实现需要考虑多个爬虫节点之间的协调和去重。 另一种思路&#xff1a;将增量判…...