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

逆向思考 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 思路&#xff1a;逆序考虑&#xff0c;因为每一块木板都是被最后一次粉刷所决定的。 从后往前开始&#xff0c;对于 c i c_i ci​来说&#xff0c; 如果这个颜色还有没有涂的木板&#xff0c;那么涂到其中一个木板即可如果这个颜色下没有未涂的…...

当当狸AR智能学习图集跨越千年文明传承,邀您“面对面”与虚拟诗人互动对诗

中华传统文化底蕴深厚&#xff0c;余韵悠长。即使经过千年的历史裂变&#xff0c;依然历久铭心慰藉着一代又一代人的灵魂。千百年后的今天&#xff0c;成为了我们独一无二的财富。 如今&#xff0c;国人学习中华传统文化的方式有很多&#xff0c;诗词集、动画影片、诗歌传颂等…...

CESM笔记——component活动状态+compset前缀解析+B1850,BHIST区别

时隔一年没写CSDN笔记了&#xff0c;一些CESM的知识点我都快忘了。诶&#xff0c;主要是在国外办公室的网屏蔽了好多国内的网络&#xff0c;CSDN登不上&#xff0c;回家又不想干活。。。好吧&#xff0c;好多借口。。。 昨天师弟问我一些问题&#xff0c;想想要不可以水一篇小…...

vue 页面跳转时,浏览器上方显示进度条

vue 页面跳转时&#xff0c;浏览器上方显示进度条 文章目录 vue 页面跳转时&#xff0c;浏览器上方显示进度条先看效果一、安装 nprogress二、main.js 引入nprogress1.引入库 三、在router.js中对路由钩子进行设置四、测试 先看效果 vue 页面跳转时&#xff0c;浏览器上方显示进…...

tqdm输出字符串被截断

tqdm输出截断 1.遇到的问题2.tqdm默认的字符串长度是80&#xff08;ncols属性&#xff09;3.修改tqdm的ncols属性4.本人字符串长度是64 1.遇到的问题 字符串打印&#xff0c;显示不完整&#xff0c; 2.tqdm默认的字符串长度是80&#xff08;ncols属性&#xff09; 3.修改tqdm的…...

Qt::UniqueConnection和lambda一块用无效

如果槽函数是lambda。 那么用了Qt::UniqueConnection也会出现槽函数被多次调用的问题。 原因&#xff1a; 参考官方文档&#xff1a; QObject Class | Qt Core 5.15.16https://doc.qt.io/qt-5/qobject.html#connect...

四川技能大赛——2023年四川网信人才技能大赛(网络安全管理员赛项)决赛

四川技能大赛——2023年四川网信人才技能大赛&#xff08;网络安全管理员赛项&#xff09;决赛 文章目录 四川技能大赛——2023年四川网信人才技能大赛&#xff08;网络安全管理员赛项&#xff09;决赛C1-比64少的bas - DONEC2-affine - DONEC3-简单的RSA - DONEM1-不要动我的f…...

死锁(面试常问)

1.什么是死锁 简单来说就是一个线程加锁后解锁不了 一个线程&#xff0c;一把锁&#xff0c;线程连续加锁两次。如果这个锁是不可重入锁&#xff0c;会死锁。两个线程&#xff0c;两把锁。 举几个例子&#xff0c;1.钥匙锁车里了&#xff0c;车钥匙锁家里了。2. 现在有一本书…...

GO设计模式——3、抽象工厂模式(创建型)

目录 抽象工厂模式&#xff08;Abstract Factory Pattern&#xff09; 抽象工厂模式的核心角色 优缺点 代码实现 抽象工厂模式&#xff08;Abstract Factory Pattern&#xff09; 抽象工厂模式&#xff08;Abstract Factory Pattern&#xff09;是围绕一个超级工厂创建其他…...

AUTOSAR_PRS_LogAndTraceProtocol文档翻译

1简介和概述 本协议规范规定了AUTOSAR协议Dlt的格式、消息序列和语义。 该协议允许将诊断、日志和跟踪信息发送到通信总线上。 因此&#xff0c;Dlt模块从应用程序或其他软件模块收集调试信息&#xff0c;向调试信息添加元数据&#xff0c;并将其发送到通信总线。 此外&#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编排&#xff1f; LLM 编排是管理和控制大型语言模型 (LLM)的过程&#xff0c;以优化其性能和有效性。这包括以下任务&#xff1a; 提示LLM&#xff1a;生成有效的提示&#xff0c;为LLMs提供适当的背景和信息以产生所需的输出。链接LLM&#xff1a; 结合多个LLM的输…...

利用机器学习实现客户细分的实战

前言&#xff1a; Hello大家好&#xff0c;我是Dream。 今天来学习一下机器学习实战中的案例&#xff1a;创建客户细分&#xff0c;在此过程中也会补充很多重要的知识点&#xff0c;欢迎大家一起前来探讨学习~ 一、导入数据 在此项目中&#xff0c;我们使用 UCI 机器学习代码库…...

Tair(4):Tair原理架构

一个Tair集群主要包括3个必选模块&#xff1a;ConfigServer、Dataserver和Client 通常情况下&#xff0c;一个 Tair 集群中包含2台 Configserver 及多台 DataServer。其中两台 Configserver 互为主备。通过和 Dataserver 之间的心跳检测获取集群中存活可用的 Dataserver&#…...

SAP UI5 walkthrough step7 JSON Model

这个章节&#xff0c;帮助我们理解MVC架构中的M 我们将会在APP中新增一个输入框&#xff0c;并将输入的值绑定到model&#xff0c;然后将其作为描述&#xff0c;直接显示在输入框的右边 首先修改App.controllers.js webapp/controller/App.controller.js sap.ui.define([&…...

智能检测/摄像头监控系统EasyCVR无法启动进程是什么原因?如何解决?

国标GB28181智慧安防平台EasyCVR支持高清视频的接入和传输、分发&#xff0c;平台采用了开放式的网络结构&#xff0c;提供实时远程视频监控、录像回放与存储等功能。视频安防监控汇聚平台可支持1、4、9、16个画面窗口播放&#xff0c;可同时播放多路视频流&#xff0c;也能支持…...

export命令详解

export命令详解 大家好&#xff0c;我是免费搭建查券返利机器人赚佣金就用微赚淘客系统3.0的小编&#xff0c;也是冬天不穿秋裤&#xff0c;天冷也要风度的程序猿&#xff01; Export命令详解&#xff1a;释放Linux强大的数据导出能力 在Linux世界中&#xff0c;export命令是…...

十几个软件测试实战项目【外卖/医药/银行/电商/金融】

项目一&#xff1a;ShopNC商城 项目概况&#xff1a; ShopNC商城是一个电子商务B2C电商平台系统&#xff0c;功能强大&#xff0c;安全便捷。适合企业及个人快速构建个性化网上商城。 包含PCIOS客户端Adroid客户端微商城&#xff0c;系统PC后台是基于ThinkPHP MVC构架开发的跨…...

用python打印出菱形图案

你可以使用Python编写一个简单的函数来打印菱形图案。下面是一个例子&#xff0c;这个函数接受一个参数n&#xff0c;表示菱形的高度&#xff0c;然后打印出一个菱形图案&#xff1a; def print_diamond(n): # 上半部分 for i in range(n): print(" " …...

k8s 中externalTrafficPolicy应用场景和实践

在Kubernetes&#xff08;K8s&#xff09;中&#xff0c;externalTrafficPolicy 是一个用于控制服务的外部流量的策略。这个字段可以在 Service 的定义中设置&#xff0c;其主要作用是决定服务对外部请求的负载均衡行为。具体来说&#xff0c;externalTrafficPolicy 有两个可选…...

Python|GIF 解析与构建(5):手搓截屏和帧率控制

目录 Python&#xff5c;GIF 解析与构建&#xff08;5&#xff09;&#xff1a;手搓截屏和帧率控制 一、引言 二、技术实现&#xff1a;手搓截屏模块 2.1 核心原理 2.2 代码解析&#xff1a;ScreenshotData类 2.2.1 截图函数&#xff1a;capture_screen 三、技术实现&…...

超短脉冲激光自聚焦效应

前言与目录 强激光引起自聚焦效应机理 超短脉冲激光在脆性材料内部加工时引起的自聚焦效应&#xff0c;这是一种非线性光学现象&#xff0c;主要涉及光学克尔效应和材料的非线性光学特性。 自聚焦效应可以产生局部的强光场&#xff0c;对材料产生非线性响应&#xff0c;可能…...

应用升级/灾备测试时使用guarantee 闪回点迅速回退

1.场景 应用要升级,当升级失败时,数据库回退到升级前. 要测试系统,测试完成后,数据库要回退到测试前。 相对于RMAN恢复需要很长时间&#xff0c; 数据库闪回只需要几分钟。 2.技术实现 数据库设置 2个db_recovery参数 创建guarantee闪回点&#xff0c;不需要开启数据库闪回。…...

简易版抽奖活动的设计技术方案

1.前言 本技术方案旨在设计一套完整且可靠的抽奖活动逻辑,确保抽奖活动能够公平、公正、公开地进行,同时满足高并发访问、数据安全存储与高效处理等需求,为用户提供流畅的抽奖体验,助力业务顺利开展。本方案将涵盖抽奖活动的整体架构设计、核心流程逻辑、关键功能实现以及…...

线程与协程

1. 线程与协程 1.1. “函数调用级别”的切换、上下文切换 1. 函数调用级别的切换 “函数调用级别的切换”是指&#xff1a;像函数调用/返回一样轻量地完成任务切换。 举例说明&#xff1a; 当你在程序中写一个函数调用&#xff1a; funcA() 然后 funcA 执行完后返回&…...

visual studio 2022更改主题为深色

visual studio 2022更改主题为深色 点击visual studio 上方的 工具-> 选项 在选项窗口中&#xff0c;选择 环境 -> 常规 &#xff0c;将其中的颜色主题改成深色 点击确定&#xff0c;更改完成...

蓝桥杯 2024 15届国赛 A组 儿童节快乐

P10576 [蓝桥杯 2024 国 A] 儿童节快乐 题目描述 五彩斑斓的气球在蓝天下悠然飘荡&#xff0c;轻快的音乐在耳边持续回荡&#xff0c;小朋友们手牵着手一同畅快欢笑。在这样一片安乐祥和的氛围下&#xff0c;六一来了。 今天是六一儿童节&#xff0c;小蓝老师为了让大家在节…...

MODBUS TCP转CANopen 技术赋能高效协同作业

在现代工业自动化领域&#xff0c;MODBUS TCP和CANopen两种通讯协议因其稳定性和高效性被广泛应用于各种设备和系统中。而随着科技的不断进步&#xff0c;这两种通讯协议也正在被逐步融合&#xff0c;形成了一种新型的通讯方式——开疆智能MODBUS TCP转CANopen网关KJ-TCPC-CANP…...

Nginx server_name 配置说明

Nginx 是一个高性能的反向代理和负载均衡服务器&#xff0c;其核心配置之一是 server 块中的 server_name 指令。server_name 决定了 Nginx 如何根据客户端请求的 Host 头匹配对应的虚拟主机&#xff08;Virtual Host&#xff09;。 1. 简介 Nginx 使用 server_name 指令来确定…...

python如何将word的doc另存为docx

将 DOCX 文件另存为 DOCX 格式&#xff08;Python 实现&#xff09; 在 Python 中&#xff0c;你可以使用 python-docx 库来操作 Word 文档。不过需要注意的是&#xff0c;.doc 是旧的 Word 格式&#xff0c;而 .docx 是新的基于 XML 的格式。python-docx 只能处理 .docx 格式…...