当前位置: 首页 > 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 有两个可选…...

谷歌浏览器插件

项目中有时候会用到插件 sync-cookie-extension1.0.0&#xff1a;开发环境同步测试 cookie 至 localhost&#xff0c;便于本地请求服务携带 cookie 参考地址&#xff1a;https://juejin.cn/post/7139354571712757767 里面有源码下载下来&#xff0c;加在到扩展即可使用FeHelp…...

Xshell远程连接Kali(默认 | 私钥)Note版

前言:xshell远程连接&#xff0c;私钥连接和常规默认连接 任务一 开启ssh服务 service ssh status //查看ssh服务状态 service ssh start //开启ssh服务 update-rc.d ssh enable //开启自启动ssh服务 任务二 修改配置文件 vi /etc/ssh/ssh_config //第一…...

CMake基础:构建流程详解

目录 1.CMake构建过程的基本流程 2.CMake构建的具体步骤 2.1.创建构建目录 2.2.使用 CMake 生成构建文件 2.3.编译和构建 2.4.清理构建文件 2.5.重新配置和构建 3.跨平台构建示例 4.工具链与交叉编译 5.CMake构建后的项目结构解析 5.1.CMake构建后的目录结构 5.2.构…...

linux 错误码总结

1,错误码的概念与作用 在Linux系统中,错误码是系统调用或库函数在执行失败时返回的特定数值,用于指示具体的错误类型。这些错误码通过全局变量errno来存储和传递,errno由操作系统维护,保存最近一次发生的错误信息。值得注意的是,errno的值在每次系统调用或函数调用失败时…...

C++ 求圆面积的程序(Program to find area of a circle)

给定半径r&#xff0c;求圆的面积。圆的面积应精确到小数点后5位。 例子&#xff1a; 输入&#xff1a;r 5 输出&#xff1a;78.53982 解释&#xff1a;由于面积 PI * r * r 3.14159265358979323846 * 5 * 5 78.53982&#xff0c;因为我们只保留小数点后 5 位数字。 输…...

JVM暂停(Stop-The-World,STW)的原因分类及对应排查方案

JVM暂停(Stop-The-World,STW)的完整原因分类及对应排查方案,结合JVM运行机制和常见故障场景整理而成: 一、GC相关暂停​​ 1. ​​安全点(Safepoint)阻塞​​ ​​现象​​:JVM暂停但无GC日志,日志显示No GCs detected。​​原因​​:JVM等待所有线程进入安全点(如…...

算法:模拟

1.替换所有的问号 1576. 替换所有的问号 - 力扣&#xff08;LeetCode&#xff09; ​遍历字符串​&#xff1a;通过外层循环逐一检查每个字符。​遇到 ? 时处理​&#xff1a; 内层循环遍历小写字母&#xff08;a 到 z&#xff09;。对每个字母检查是否满足&#xff1a; ​与…...

Qemu arm操作系统开发环境

使用qemu虚拟arm硬件比较合适。 步骤如下&#xff1a; 安装qemu apt install qemu-system安装aarch64-none-elf-gcc 需要手动下载&#xff0c;下载地址&#xff1a;https://developer.arm.com/-/media/Files/downloads/gnu/13.2.rel1/binrel/arm-gnu-toolchain-13.2.rel1-x…...

AI语音助手的Python实现

引言 语音助手(如小爱同学、Siri)通过语音识别、自然语言处理(NLP)和语音合成技术,为用户提供直观、高效的交互体验。随着人工智能的普及,Python开发者可以利用开源库和AI模型,快速构建自定义语音助手。本文由浅入深,详细介绍如何使用Python开发AI语音助手,涵盖基础功…...

Xela矩阵三轴触觉传感器的工作原理解析与应用场景

Xela矩阵三轴触觉传感器通过先进技术模拟人类触觉感知&#xff0c;帮助设备实现精确的力测量与位移监测。其核心功能基于磁性三维力测量与空间位移测量&#xff0c;能够捕捉多维触觉信息。该传感器的设计不仅提升了触觉感知的精度&#xff0c;还为机器人、医疗设备和制造业的智…...