逆向思考 C. Fence Painting
Problem - 1481C - Codeforces

思路:逆序考虑,因为每一块木板都是被最后一次粉刷所决定的。
从后往前开始,对于 c i c_i ci来说,
- 如果这个颜色还有没有涂的木板,那么涂到其中一个木板即可
- 如果这个颜色下没有未涂的木板,找到一个已经土过的木板
- 如果这个颜色没有被涂,且没有已经被涂的木板,那么涂到一个相同木板上
- 如果这个颜色没有被涂,却没有已经被涂的木板,同时也没有相同木板,那么无解。
最后再检验一下,是否可行即可。
代码如下:
void solve() {int n,m; cin>>n>>m;bool ok = true;int pos = -1;vector<int> a(n + 1), b(a), c(m + 1),ans(m + 1), e(n + 1, -1);/*** ans存第j个人涂哪个木板* e存第z个颜色的最远位置*/vector<vector<int>> g(n + 1);for(int i = 1 ; i <= n; ++i) cin>>a[i];for(int i = 1; i <= n; ++i) cin>>b[i];for(int i = 1; i <= m; ++i) cin>>c[i];for(int i = 1; i <= n; ++i) {// 不相同表示,需要更改,先进行标记if(a[i] != b[i]) g[b[i]].push_back(i);e[b[i]] = i;}for(int i = m; i >= 1; --i) {// 现在木板中,没有将木板颜色更改为ci的需求if(g[c[i]].size() == 0) {// 如果是-1,表示没有已经被涂色的if(pos == -1) {// 如果这个ci颜色在木板中不存在,结束if(e[c[i]] == -1) {ok = false;break;}// 否则涂到相同木板上pos = e[c[i]];}} else {// 位置更新pos = g[c[i]].back();g[c[i]].pop_back();a[pos] = b[pos];}// 第i个人要涂的位置ans[i] = pos;}// 检查一下是否符合for(int i = 1; i <= n; ++i) ok &= a[i] == b[i];if(ok) {cout<<"YES\n";for(int i = 1; i <= m; ++i) cout<<ans[i]<<" \n"[i == m];} else cout<<"NO\n";
}
CF1481C Fence Painting - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
相关文章:
逆向思考 C. Fence Painting
Problem - 1481C - Codeforces 思路:逆序考虑,因为每一块木板都是被最后一次粉刷所决定的。 从后往前开始,对于 c i c_i ci来说, 如果这个颜色还有没有涂的木板,那么涂到其中一个木板即可如果这个颜色下没有未涂的…...
当当狸AR智能学习图集跨越千年文明传承,邀您“面对面”与虚拟诗人互动对诗
中华传统文化底蕴深厚,余韵悠长。即使经过千年的历史裂变,依然历久铭心慰藉着一代又一代人的灵魂。千百年后的今天,成为了我们独一无二的财富。 如今,国人学习中华传统文化的方式有很多,诗词集、动画影片、诗歌传颂等…...
CESM笔记——component活动状态+compset前缀解析+B1850,BHIST区别
时隔一年没写CSDN笔记了,一些CESM的知识点我都快忘了。诶,主要是在国外办公室的网屏蔽了好多国内的网络,CSDN登不上,回家又不想干活。。。好吧,好多借口。。。 昨天师弟问我一些问题,想想要不可以水一篇小…...
vue 页面跳转时,浏览器上方显示进度条
vue 页面跳转时,浏览器上方显示进度条 文章目录 vue 页面跳转时,浏览器上方显示进度条先看效果一、安装 nprogress二、main.js 引入nprogress1.引入库 三、在router.js中对路由钩子进行设置四、测试 先看效果 vue 页面跳转时,浏览器上方显示进…...
tqdm输出字符串被截断
tqdm输出截断 1.遇到的问题2.tqdm默认的字符串长度是80(ncols属性)3.修改tqdm的ncols属性4.本人字符串长度是64 1.遇到的问题 字符串打印,显示不完整, 2.tqdm默认的字符串长度是80(ncols属性) 3.修改tqdm的…...
Qt::UniqueConnection和lambda一块用无效
如果槽函数是lambda。 那么用了Qt::UniqueConnection也会出现槽函数被多次调用的问题。 原因: 参考官方文档: QObject Class | Qt Core 5.15.16https://doc.qt.io/qt-5/qobject.html#connect...
四川技能大赛——2023年四川网信人才技能大赛(网络安全管理员赛项)决赛
四川技能大赛——2023年四川网信人才技能大赛(网络安全管理员赛项)决赛 文章目录 四川技能大赛——2023年四川网信人才技能大赛(网络安全管理员赛项)决赛C1-比64少的bas - DONEC2-affine - DONEC3-简单的RSA - DONEM1-不要动我的f…...
死锁(面试常问)
1.什么是死锁 简单来说就是一个线程加锁后解锁不了 一个线程,一把锁,线程连续加锁两次。如果这个锁是不可重入锁,会死锁。两个线程,两把锁。 举几个例子,1.钥匙锁车里了,车钥匙锁家里了。2. 现在有一本书…...
GO设计模式——3、抽象工厂模式(创建型)
目录 抽象工厂模式(Abstract Factory Pattern) 抽象工厂模式的核心角色 优缺点 代码实现 抽象工厂模式(Abstract Factory Pattern) 抽象工厂模式(Abstract Factory Pattern)是围绕一个超级工厂创建其他…...
AUTOSAR_PRS_LogAndTraceProtocol文档翻译
1简介和概述 本协议规范规定了AUTOSAR协议Dlt的格式、消息序列和语义。 该协议允许将诊断、日志和跟踪信息发送到通信总线上。 因此,Dlt模块从应用程序或其他软件模块收集调试信息,向调试信息添加元数据,并将其发送到通信总线。 此外&#x…...
自定义比较器
package org.jeecg.modules.develop.api.livePort; import java.util.ArrayList; import java.util.Collections; import java.util.Comparator; import java.util.List; // 创建一个泛型类 class MyObject { private T data; public MyObject(T data) {this.data data; }p…...
【NLP】如何管理大型语言模型 (LLM)
什么是LLM编排? LLM 编排是管理和控制大型语言模型 (LLM)的过程,以优化其性能和有效性。这包括以下任务: 提示LLM:生成有效的提示,为LLMs提供适当的背景和信息以产生所需的输出。链接LLM: 结合多个LLM的输…...
利用机器学习实现客户细分的实战
前言: Hello大家好,我是Dream。 今天来学习一下机器学习实战中的案例:创建客户细分,在此过程中也会补充很多重要的知识点,欢迎大家一起前来探讨学习~ 一、导入数据 在此项目中,我们使用 UCI 机器学习代码库…...
Tair(4):Tair原理架构
一个Tair集群主要包括3个必选模块:ConfigServer、Dataserver和Client 通常情况下,一个 Tair 集群中包含2台 Configserver 及多台 DataServer。其中两台 Configserver 互为主备。通过和 Dataserver 之间的心跳检测获取集群中存活可用的 Dataserver&#…...
SAP UI5 walkthrough step7 JSON Model
这个章节,帮助我们理解MVC架构中的M 我们将会在APP中新增一个输入框,并将输入的值绑定到model,然后将其作为描述,直接显示在输入框的右边 首先修改App.controllers.js webapp/controller/App.controller.js sap.ui.define([&…...
智能检测/摄像头监控系统EasyCVR无法启动进程是什么原因?如何解决?
国标GB28181智慧安防平台EasyCVR支持高清视频的接入和传输、分发,平台采用了开放式的网络结构,提供实时远程视频监控、录像回放与存储等功能。视频安防监控汇聚平台可支持1、4、9、16个画面窗口播放,可同时播放多路视频流,也能支持…...
export命令详解
export命令详解 大家好,我是免费搭建查券返利机器人赚佣金就用微赚淘客系统3.0的小编,也是冬天不穿秋裤,天冷也要风度的程序猿! Export命令详解:释放Linux强大的数据导出能力 在Linux世界中,export命令是…...
十几个软件测试实战项目【外卖/医药/银行/电商/金融】
项目一:ShopNC商城 项目概况: ShopNC商城是一个电子商务B2C电商平台系统,功能强大,安全便捷。适合企业及个人快速构建个性化网上商城。 包含PCIOS客户端Adroid客户端微商城,系统PC后台是基于ThinkPHP MVC构架开发的跨…...
用python打印出菱形图案
你可以使用Python编写一个简单的函数来打印菱形图案。下面是一个例子,这个函数接受一个参数n,表示菱形的高度,然后打印出一个菱形图案: def print_diamond(n): # 上半部分 for i in range(n): print(" " …...
k8s 中externalTrafficPolicy应用场景和实践
在Kubernetes(K8s)中,externalTrafficPolicy 是一个用于控制服务的外部流量的策略。这个字段可以在 Service 的定义中设置,其主要作用是决定服务对外部请求的负载均衡行为。具体来说,externalTrafficPolicy 有两个可选…...
使用docker在3台服务器上搭建基于redis 6.x的一主两从三台均是哨兵模式
一、环境及版本说明 如果服务器已经安装了docker,则忽略此步骤,如果没有安装,则可以按照一下方式安装: 1. 在线安装(有互联网环境): 请看我这篇文章 传送阵>> 点我查看 2. 离线安装(内网环境):请看我这篇文章 传送阵>> 点我查看 说明:假设每台服务器已…...
Java 语言特性(面试系列2)
一、SQL 基础 1. 复杂查询 (1)连接查询(JOIN) 内连接(INNER JOIN):返回两表匹配的记录。 SELECT e.name, d.dept_name FROM employees e INNER JOIN departments d ON e.dept_id d.dept_id; 左…...
地震勘探——干扰波识别、井中地震时距曲线特点
目录 干扰波识别反射波地震勘探的干扰波 井中地震时距曲线特点 干扰波识别 有效波:可以用来解决所提出的地质任务的波;干扰波:所有妨碍辨认、追踪有效波的其他波。 地震勘探中,有效波和干扰波是相对的。例如,在反射波…...
云计算——弹性云计算器(ECS)
弹性云服务器:ECS 概述 云计算重构了ICT系统,云计算平台厂商推出使得厂家能够主要关注应用管理而非平台管理的云平台,包含如下主要概念。 ECS(Elastic Cloud Server):即弹性云服务器,是云计算…...
《Qt C++ 与 OpenCV:解锁视频播放程序设计的奥秘》
引言:探索视频播放程序设计之旅 在当今数字化时代,多媒体应用已渗透到我们生活的方方面面,从日常的视频娱乐到专业的视频监控、视频会议系统,视频播放程序作为多媒体应用的核心组成部分,扮演着至关重要的角色。无论是在个人电脑、移动设备还是智能电视等平台上,用户都期望…...
python如何将word的doc另存为docx
将 DOCX 文件另存为 DOCX 格式(Python 实现) 在 Python 中,你可以使用 python-docx 库来操作 Word 文档。不过需要注意的是,.doc 是旧的 Word 格式,而 .docx 是新的基于 XML 的格式。python-docx 只能处理 .docx 格式…...
TRS收益互换:跨境资本流动的金融创新工具与系统化解决方案
一、TRS收益互换的本质与业务逻辑 (一)概念解析 TRS(Total Return Swap)收益互换是一种金融衍生工具,指交易双方约定在未来一定期限内,基于特定资产或指数的表现进行现金流交换的协议。其核心特征包括&am…...
CMake 从 GitHub 下载第三方库并使用
有时我们希望直接使用 GitHub 上的开源库,而不想手动下载、编译和安装。 可以利用 CMake 提供的 FetchContent 模块来实现自动下载、构建和链接第三方库。 FetchContent 命令官方文档✅ 示例代码 我们将以 fmt 这个流行的格式化库为例,演示如何: 使用 FetchContent 从 GitH…...
c#开发AI模型对话
AI模型 前面已经介绍了一般AI模型本地部署,直接调用现成的模型数据。这里主要讲述讲接口集成到我们自己的程序中使用方式。 微软提供了ML.NET来开发和使用AI模型,但是目前国内可能使用不多,至少实践例子很少看见。开发训练模型就不介绍了&am…...
蓝桥杯 冶炼金属
原题目链接 🔧 冶炼金属转换率推测题解 📜 原题描述 小蓝有一个神奇的炉子用于将普通金属 O O O 冶炼成为一种特殊金属 X X X。这个炉子有一个属性叫转换率 V V V,是一个正整数,表示每 V V V 个普通金属 O O O 可以冶炼出 …...
