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

Codeforces Round #699 (Div. 2)

E.

题意:n本书,每本书有颜色a[i],一次操作可以将其中一本书放在末尾,求满足:相同颜色的书都是相邻的 的最小操作次数.

显然最多只需要n次,考虑能节省多少次.倒着考虑,记f[i]为i~n最多能节约的次数.先预处理出每种颜色的出现的位置范围l[i],r[i].

1.不节约这本书f[i] = f[i + 1]

2.if i == l[a[i]], f[i] = cnt[a[i]] + f[r[a[i]]+1]

3.if i != l[a[i]], f[i] = cnt[a[i]](位置i后的a[i]个数),为什么不加上f[r[a[i]]+1]呢?首先这个转移必然不可能是最优的,肯定会被前面i = l[a[i]]时替换掉,所以我们只考虑这部分被继承时的情况.如果被继承只有可能前面出现i' == l[a[i']],并且r[a[i']]>i,那么f[i'] = cnt[a[i']] + f[r[a[i']+1]],此时我们保留a[i']和i以及i后面的a[i]不动,先将i前面i'后面的a[i]移到末尾,再把其他与a[i],a[i']不同的数移到末尾即可.

#include <bits/stdc++.h>
#define int long long
#define IOS ios::sync_with_stdio(false), cin.tie(0) 
#define ll long long 
// #define double long double
#define ull unsigned long long 
#define PII pair<int, int> 
#define PDI pair<double, int> 
#define PDD pair<double, double> 
#define debug(a) cout << #a << " = " << a << endl 
#define point(n) cout << fixed << setprecision(n)
#define all(x) (x).begin(), (x).end() 
#define mem(x, y) memset((x), (y), sizeof(x))
#define lbt(x) (x & (-x)) 
#define SZ(x) ((x).size()) 
#define inf 0x3f3f3f3f
#define INF 0x3f3f3f3f3f3f3f3f
// namespace nqio { const unsigned R = 4e5, W = 4e5; char* a, * b, i[R], o[W], * c = o, * d = o + W, h[40], * p = h, y; bool s; struct q { void r(char& x) { x = a == b && (b = (a = i) + fread(i, 1, R, stdin), a == b) ? -1 : *a++; } void f() { fwrite(o, 1, c - o, stdout); c = o; } ~q() { f(); }void w(char x) { *c = x; if (++c == d) f(); } q& operator >>(char& x) { do r(x); while (x <= 32); return *this; } q& operator >>(char* x) { do r(*x); while (*x <= 32); while (*x > 32) r(*++x); *x = 0; return *this; } template<typename t> q& operator>>(t& x) { for (r(y), s = 0; !isdigit(y); r(y)) s |= y == 45; if (s) for (x = 0; isdigit(y); r(y)) x = x * 10 - (y ^ 48); else for (x = 0; isdigit(y); r(y)) x = x * 10 + (y ^ 48); return *this; } q& operator <<(char x) { w(x); return *this; }q& operator<< (char* x) { while (*x) w(*x++); return *this; }q& operator <<(const char* x) { while (*x) w(*x++); return *this; }template<typename t> q& operator<< (t x) { if (!x) w(48); else if (x < 0) for (w(45); x; x /= 10) *p++ = 48 | -(x % 10); else for (; x; x /= 10) *p++ = 48 | x % 10; while (p != h) w(*--p); return *this; } }qio; }using nqio::qio;
using namespace std;
mt19937 rnd(random_device{}());
const int N = 2e6 + 10;
int n, a[N], f[N], l[N], r[N];
map<int, int> cnt;
signed main() {IOS;cin >> n;for (int i = 1; i <= n; ++i) {cin >> a[i];}for (int i = 1; i <= n; ++i) {r[a[i]] = i;}for (int i = n; i >= 1; --i) {l[a[i]] = i;}for (int i = n; i >= 1; --i) {++cnt[a[i]];f[i] = f[i + 1];if (i == l[a[i]]) f[i] = max(f[i], f[r[a[i]] + 1] + cnt[a[i]]);else f[i] = max(f[i], cnt[a[i]]);}cout << n - f[1] << "\n";
}

F.

题意:对n个节点1为根的树ab染色,有x个a,n-x个b.定义i节点上的字符串为1到i路径上的字符.求字符串种类数最少多少种,输出染色方案.

首先每一层尽可能染成一种颜色,如果恰好平分,那么答案为树的最大深度.这毫无疑问是答案下界,我们再去找答案上界,猜测是最大深度+1.假设我们在染色某一层时,剩下m个点未染色,有t个非叶节点,那么我们肯定能将这t个非叶节点染成同一种颜色,因为至少还有t个叶子节点,我们只需要拿数量多的颜色来染即可,然后染叶子节点,显然能调整成与刚才非叶节点同一种颜色.

问题转化成了将每一层都染成a或者b,能否刚好染好每一层.这是一个典型的多重背包,我们将每层点的个数看成是物品,x或者n - x看成容积,然后求出选出若干层能否得到容积即可.由于要回溯,我们不压缩状态.设f[i][j]为考虑前i个物品,选的点数为j的可行性,可行性多重背包可以用贪心优化成O(nm).修改状态为f[i][j]为前i个物品凑出j的前提下,前i - 1个物品最多凑的价值.

这里详细说一下多重背包的优化方法:

由于我们只关注可行性,所以我们只需要关注会传递可行性的转移即可.

1.如果前i - 1个物品能凑出j,那么显然前i个也肯定能凑出来.if (f[i - 1][j] != -1) f[i][j] = j

2.如果前i - 1个物品凑不出来j,需要用第i个物品配合前i - 1个物品来凑,我们让体积从小到大枚举,先得到小于j能凑出来的体积,如果能凑出j - v[i],(v[i]为第i个物品的体积),那么如果还有至少一个i号物品,肯定能凑出j - v[i],换而言之,如果f[j - v[i]] != -1 && (j - f[i][j - v[i]) / v[i] <= cnt[i],那么f[i][j] = f[i][j - v[i]].

回溯的时候,我们需要求出拼成容积m每个价值的物品用了多少个.可以倒着来used[i] = (cur - f[i][cur]) / v[i]; cur = f[i][cur].

#include <bits/stdc++.h>
#define int long long
#define IOS ios::sync_with_stdio(false), cin.tie(0) 
#define ll long long 
// #define double long double
#define ull unsigned long long 
#define PII pair<int, int> 
#define PDI pair<double, int> 
#define PDD pair<double, double> 
#define debug(a) cout << #a << " = " << a << endl 
#define point(n) cout << fixed << setprecision(n)
#define all(x) (x).begin(), (x).end() 
#define mem(x, y) memset((x), (y), sizeof(x))
#define lbt(x) (x & (-x)) 
#define SZ(x) ((x).size()) 
#define inf 0x3f3f3f3f
#define INF 0x3f3f3f3f3f3f3f3f
// namespace nqio { const unsigned R = 4e5, W = 4e5; char* a, * b, i[R], o[W], * c = o, * d = o + W, h[40], * p = h, y; bool s; struct q { void r(char& x) { x = a == b && (b = (a = i) + fread(i, 1, R, stdin), a == b) ? -1 : *a++; } void f() { fwrite(o, 1, c - o, stdout); c = o; } ~q() { f(); }void w(char x) { *c = x; if (++c == d) f(); } q& operator >>(char& x) { do r(x); while (x <= 32); return *this; } q& operator >>(char* x) { do r(*x); while (*x <= 32); while (*x > 32) r(*++x); *x = 0; return *this; } template<typename t> q& operator>>(t& x) { for (r(y), s = 0; !isdigit(y); r(y)) s |= y == 45; if (s) for (x = 0; isdigit(y); r(y)) x = x * 10 - (y ^ 48); else for (x = 0; isdigit(y); r(y)) x = x * 10 + (y ^ 48); return *this; } q& operator <<(char x) { w(x); return *this; }q& operator<< (char* x) { while (*x) w(*x++); return *this; }q& operator <<(const char* x) { while (*x) w(*x++); return *this; }template<typename t> q& operator<< (t x) { if (!x) w(48); else if (x < 0) for (w(45); x; x /= 10) *p++ = 48 | -(x % 10); else for (; x; x /= 10) *p++ = 48 | x % 10; while (p != h) w(*--p); return *this; } }qio; }using nqio::qio;
using namespace std;
mt19937 rnd(random_device{}());
const int N = 2e6 + 10;
int n, a[N], f[N], l[N], r[N];
map<int, int> cnt;
signed main() {IOS;cin >> n;for (int i = 1; i <= n; ++i) {cin >> a[i];}for (int i = 1; i <= n; ++i) {r[a[i]] = i;}for (int i = n; i >= 1; --i) {l[a[i]] = i;}for (int i = n; i >= 1; --i) {++cnt[a[i]];f[i] = f[i + 1];if (i == l[a[i]]) f[i] = max(f[i], f[r[a[i]] + 1] + cnt[a[i]]);else f[i] = max(f[i], cnt[a[i]]);}cout << n - f[1] << "\n";
}

相关文章:

Codeforces Round #699 (Div. 2)

E. 题意:n本书,每本书有颜色a[i],一次操作可以将其中一本书放在末尾,求满足:相同颜色的书都是相邻的 的最小操作次数. 显然最多只需要n次,考虑能节省多少次.倒着考虑,记f[i]为i~n最多能节约的次数.先预处理出每种颜色的出现的位置范围l[i],r[i]. 1.不节约这本书f[i] f[i 1]…...

MySQL存储过程的传参和流程控制

目录 一.存储过程传参—in 演示 二.存储过程传参—out 演示 三.存储过程传参—inout 演示 四.流程控制—判断 格式 演示 五.流程控制—case 语法 演示 六.流程控制—循环 循环—while 循环—repeat 循环—loop 一.存储过程传参—in in表示传入的参数&#xff0c;可以传…...

MySQl学习(从入门到精通11)

MySQl学习&#xff08;从入门到精通11&#xff09;第 14 章_视图1. 常见的数据库对象2. 视图概述2. 1 为什么使用视图&#xff1f;2. 2 视图的理解3. 创建视图3. 1 创建单表视图3. 2 创建多表联合视图3. 3 基于视图创建视图4. 查看视图5. 更新视图的数据5. 1 一般情况5. 2 不可…...

关于ThreadLocal

弱引用 1.1 java中的各种引用和测试: https://blog.csdn.net/thewindkee/article/details/102723838 1.2 treadlocal中的弱引用测试: https://blog.csdn.net/thewindkee/article/details/103726942 (这篇很重要) 内存泄露: https://zhuanlan.zhihu.com/p/523628871 综合考虑 …...

【C++】类和对象(中)

文章目录1. 类的6个默认成员函数2. 构造函数概念特性3. 析构函数概念特性4. 拷贝构造函数概念特征5. 运算符重载5.1 前置和后置重载5.2 赋值运算符重载6. 日期类的实现7. const成员8. 取地址及const取地址操作符重载1. 类的6个默认成员函数 如果一个类中什么成员都没有&#x…...

js下载文件

url为文件的src地址 url必须符合同源策略或者url的接口地址允许跨域&#xff0c;否则浏览器会报跨域错误 axios.get(data.url ,{ responseType: ‘blob’, }) .then( response>{ let blob new Blob([response.data]); let url window.URL.createObjectURL(blob); // 创建 …...

ESP8266 + STC15+ I2C OLED带网络校时功能的定时器时钟

ESP8266 + STC15+ I2C OLED带网络校时功能的定时器时钟 📍相关篇《ESP8266 + STC15基于AT指令通过TCP通讯协议获取时间》 📌ESP8266 AT固件基于安信可AT固件,相关刷AT固件可以参考《NodeMCU-刷写AT固件》 🔖STC15 单片机采用的是:STC15F2K60S2 晶振频率采用内部:22.11…...

计算机入门基础知识大全

♥️作者&#xff1a;小刘在C站 ♥️个人主页&#xff1a;小刘主页 ♥️每天分享云计算网络运维课堂笔记&#xff0c;努力不一定有收获&#xff0c;但一定会有收获加油&#xff01;一起努力&#xff0c;共赴美好人生&#xff01; ♥️夕阳下&#xff0c;是最美的&#xff0c;绽…...

Python程序出现错误怎么办?

Python 异常处理 python提供了两个非常重要的功能来处理python程序在运行中出现的异常和错误。你可以使用该功能来调试python程序。 异常处理: 本站Python教程会具体介绍。 断言(Assertions):本站Python教程会具体介绍。 python标准异常 异常名称 描述 BaseException 所有异常…...

【Vue3】v-if和v-for优先级

&#x1f388;博客主页&#xff1a;&#x1f308;我的主页&#x1f308; &#x1f388;欢迎点赞 &#x1f44d; 收藏 &#x1f31f;留言 &#x1f4dd; 欢迎讨论&#xff01;&#x1f44f; &#x1f388;本文由 【泠青沼~】 原创&#xff0c;首发于 CSDN&#x1f6a9;&#x1f…...

Windows上实现 IOS 自动化测试

本文介绍如何使用tideviceWDAairtest/facebook-wda实现在Windows上进行IOS APP自动化测试 环境准备 Windows Python环境 Python 3.6 WebDriverAgent安装 下载最新的项目到Mac&#xff1a;https://github.com/appium/WebDriverAgent $ git clone https://github.com/appiu…...

Linux云服务器下怎么重置MySQL8.0数据库密码

文章目录一、修改my.cnf配置文件为mysql免登陆二、免密登陆mysql三.给root用户重置密码1、首先查看当前root用户相关信息&#xff0c;在mysql数据库的user表中2、把root密码置为空3、退出mysql&#xff0c;删除/etc/my.cnf文件中添加进去的skip-grant-tables 重启mysql服务4、使…...

JVM调优

JVM调优-VisualVmVisualVm/ Jconsule远程连接第一种方式第二种方式&#xff1a;java 11开启远程GC连接如果还连不上考虑防火墙拦截了端口firewall-cmd --list-all,查看一下并暴露对应端口连接配置VisualVm界面简介采集GC信息的一些命令垃圾回收器切换VisualVm/ Jconsule远程连接…...

【配电网规划】SOCPR和基于线性离散最优潮流(OPF)模型的配电网规划( DNP )(Matlab代码实现)

&#x1f4a5;&#x1f4a5;&#x1f49e;&#x1f49e;欢迎来到本博客❤️❤️&#x1f4a5;&#x1f4a5; &#x1f3c6;博主优势&#xff1a;&#x1f31e;&#x1f31e;&#x1f31e;博客内容尽量做到思维缜密&#xff0c;逻辑清晰&#xff0c;为了方便读者。 ⛳️座右铭&a…...

锦正茂EM3电磁铁的技术参数

产品特点&#xff1a; ※U形结构、视野开阔、磁场强度高、磁场强度大小调节方便 ※体积小、重量轻、占空比小、结构紧凑、磁场性能更佳 ※电磁铁的工作气隙调节轻便灵活&#xff0c;极头处设有螺纹&#xff0c;更换极头装卸方便 ※可选配工作间隙刻度指示 ※小气隙时用于铁…...

Go最新版下载 Go1.20版新特性

Go官方正式发布了Go1.20稳定版 该版本依然保持 Go1 兼容性&#xff0c;可以升级到 Go1.20&#xff0c;而不需要做任何代码改动。 可以使用你任何喜欢的方式升级&#xff1a; 比如&#xff1a; go install golang.org/dl/go1.20latest 具体的可以参考官网教程&#xff1a; ht…...

Pywirt:一款基于Python的Windows安全应急响应工具

关于Pywirt Pywirt是一款基于Python开发的网络安全工具&#xff0c;该工具专门针对Windows操作系统设计&#xff0c;可以帮助广大研究人员使用winrm并通过在Windows操作系统上收集各种信息来加快安全事件应急响应的速度。 该工具已在Windows 10操作系统上进行过完整测试。 功…...

KDZD832 智能蓄电池活化仪

一、产品概述 KDZD832 智能蓄电池活化仪&#xff08;2V-24V 一体机&#xff0c;适用于 2V、6V、12V/24V 蓄电池&#xff0c;以下简称活化仪&#xff09;&#xff0c;是专用于日常维护中对落后蓄电池处理的便携式产品&#xff0c;它具有四种独立的使用方式&#xff1a;电池放电…...

纯css实现loading加载中(多种展现形式)

前言 现如今网页越来越趋近于动画&#xff0c;相信大家平时浏览网页或多或少都能看到一些动画效果&#xff0c;今天我们来做一个有意思的动画效果&#xff0c;纯 css 实现 loading 加载中&#xff08;多种展现形式&#xff09;&#xff0c;下面一起看看吧。 1. 常规 loading 实…...

【面试题】2023 vue高频面试知识点汇总

一、MVVM原理在Vue2官方文档中没有找到Vue是MVVM的直接证据&#xff0c;但文档有提到&#xff1a;虽然没有完全遵循MVVM模型&#xff0c;但是 Vue 的设计也受到了它的启发&#xff0c;因此在文档中经常会使用vm(ViewModel 的缩写) 这个变量名表示 Vue 实例。为了感受MVVM模型的…...

linux之kylin系统nginx的安装

一、nginx的作用 1.可做高性能的web服务器 直接处理静态资源&#xff08;HTML/CSS/图片等&#xff09;&#xff0c;响应速度远超传统服务器类似apache支持高并发连接 2.反向代理服务器 隐藏后端服务器IP地址&#xff0c;提高安全性 3.负载均衡服务器 支持多种策略分发流量…...

【入坑系列】TiDB 强制索引在不同库下不生效问题

文章目录 背景SQL 优化情况线上SQL运行情况分析怀疑1:执行计划绑定问题?尝试:SHOW WARNINGS 查看警告探索 TiDB 的 USE_INDEX 写法Hint 不生效问题排查解决参考背景 项目中使用 TiDB 数据库,并对 SQL 进行优化了,添加了强制索引。 UAT 环境已经生效,但 PROD 环境强制索…...

centos 7 部署awstats 网站访问检测

一、基础环境准备&#xff08;两种安装方式都要做&#xff09; bash # 安装必要依赖 yum install -y httpd perl mod_perl perl-Time-HiRes perl-DateTime systemctl enable httpd # 设置 Apache 开机自启 systemctl start httpd # 启动 Apache二、安装 AWStats&#xff0…...

大数据零基础学习day1之环境准备和大数据初步理解

学习大数据会使用到多台Linux服务器。 一、环境准备 1、VMware 基于VMware构建Linux虚拟机 是大数据从业者或者IT从业者的必备技能之一也是成本低廉的方案 所以VMware虚拟机方案是必须要学习的。 &#xff08;1&#xff09;设置网关 打开VMware虚拟机&#xff0c;点击编辑…...

Vue2 第一节_Vue2上手_插值表达式{{}}_访问数据和修改数据_Vue开发者工具

文章目录 1.Vue2上手-如何创建一个Vue实例,进行初始化渲染2. 插值表达式{{}}3. 访问数据和修改数据4. vue响应式5. Vue开发者工具--方便调试 1.Vue2上手-如何创建一个Vue实例,进行初始化渲染 准备容器引包创建Vue实例 new Vue()指定配置项 ->渲染数据 准备一个容器,例如: …...

微服务商城-商品微服务

数据表 CREATE TABLE product (id bigint(20) UNSIGNED NOT NULL AUTO_INCREMENT COMMENT 商品id,cateid smallint(6) UNSIGNED NOT NULL DEFAULT 0 COMMENT 类别Id,name varchar(100) NOT NULL DEFAULT COMMENT 商品名称,subtitle varchar(200) NOT NULL DEFAULT COMMENT 商…...

06 Deep learning神经网络编程基础 激活函数 --吴恩达

深度学习激活函数详解 一、核心作用 引入非线性:使神经网络可学习复杂模式控制输出范围:如Sigmoid将输出限制在(0,1)梯度传递:影响反向传播的稳定性二、常见类型及数学表达 Sigmoid σ ( x ) = 1 1 +...

华为云Flexus+DeepSeek征文|DeepSeek-V3/R1 商用服务开通全流程与本地部署搭建

华为云FlexusDeepSeek征文&#xff5c;DeepSeek-V3/R1 商用服务开通全流程与本地部署搭建 前言 如今大模型其性能出色&#xff0c;华为云 ModelArts Studio_MaaS大模型即服务平台华为云内置了大模型&#xff0c;能助力我们轻松驾驭 DeepSeek-V3/R1&#xff0c;本文中将分享如何…...

Maven 概述、安装、配置、仓库、私服详解

目录 1、Maven 概述 1.1 Maven 的定义 1.2 Maven 解决的问题 1.3 Maven 的核心特性与优势 2、Maven 安装 2.1 下载 Maven 2.2 安装配置 Maven 2.3 测试安装 2.4 修改 Maven 本地仓库的默认路径 3、Maven 配置 3.1 配置本地仓库 3.2 配置 JDK 3.3 IDEA 配置本地 Ma…...

代理篇12|深入理解 Vite中的Proxy接口代理配置

在前端开发中,常常会遇到 跨域请求接口 的情况。为了解决这个问题,Vite 和 Webpack 都提供了 proxy 代理功能,用于将本地开发请求转发到后端服务器。 什么是代理(proxy)? 代理是在开发过程中,前端项目通过开发服务器,将指定的请求“转发”到真实的后端服务器,从而绕…...