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

CF 1328 D Carousel(环构造)

CF 1328 D. Carousel(环构造)

Problem - D - Codeforces

大意:给出一个 n 个数组成的环 , 要对环上的点染色 , 要求任意一个相邻数不同的点对染色不同 ,求使用最少的颜色数 , 并用颜色数排列构造一种染色方案。

思路:手模一下发现颜色数并不会超过 3 .

下面分情况进行讨论:

1 : 当所有数相同时 ans = 1

2 : 当环为偶数长度时 , 显然可以构造 1 , 2 交替的环 ans = 2

3 : 当环长为奇数时 , 构造 1 , 2 交替的环会强制让断点处的数相等 , 这时候如果环中有相邻相等的数对 , 就可以作为断点 , ans = 2 , 否则 ans = 3 , 先构造 1 2 交替 , 让最后一个数作为 3 即可。

#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define IOS std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
#define int long long
const int N = 2e6 + 10;
const int mod = 1e9 + 7;
typedef pair<int,int>PII;/*
3
1 2 3 4 5
1 2 1 2 1
*/
int n , t;
int a[N] , ans[N];signed main(){IOScin >> t;while(t --){cin >> n;bool tag = 0;int now = 0;map<int , int>mp;for(int i = 0 ; i < n ; i ++){cin >> a[i];mp[a[i]] = 1;}for(int i = 0 ; i < n ; i ++){if(a[i] == a[(i + 1) % n]) tag = 1 , now = (i + 1) % n;}if(mp.size() == 1){cout << "1\n";for(int i = 0 ; i < n ; i ++) ans[i] = 1;}else{if(n % 2 == 0){cout << "2\n";for(int i = 0 ; i < n ; i ++){if(i & 1) ans[i] = 1;else ans[i] = 2;}}else if(tag){cout << "2\n";for(int i = 1 , j = now ; i <= n ; i ++ , j = (j + 1) % n){if(i & 1) ans[j] = 1;else ans[j] = 2;}}else{cout << "3\n";for(int i = 0 ; i < n - 1 ; i ++){if(i & 1) ans[i] = 1;else ans[i] = 2;}ans[n - 1] = 3;}}for(int i = 0 ; i < n ; i ++) cout << ans[i] << " ";cout << "\n";}return 0;
}
//freopen("文件名.in","r",stdin);
//freopen("文件名.out","w",stdout);

相关文章:

CF 1328 D Carousel(环构造)

CF 1328 D. Carousel(环构造) Problem - D - Codeforces 大意&#xff1a;给出一个 n 个数组成的环 &#xff0c; 要对环上的点染色 &#xff0c; 要求任意一个相邻数不同的点对染色不同 &#xff0c;求使用最少的颜色数 &#xff0c; 并用颜色数排列构造一种染色方案。 思路…...

什么是SaaS、PaaS、aPaaS、iPaaS、IaaS,一文讲透

在数字化的带动下&#xff0c;各行业对云服务的需求进入快速增长期。 SaaS、PaaS、aPaaS、iPaaS、IaaS…… 这些词经常出现&#xff0c;那么他们分别是什么意思&#xff1f;又有什么区别&#xff1f;小帆带大家一起来看看~ SaaS SaaS&#xff0c;Software as a Service&…...

Mac nvm 切换为淘宝镜像

编辑环境配置 # 或者 vim ~/.bash_profile $ vim ~/.zshrc贴入镜像 # 淘宝镜像 export NVM_NODEJS_ORG_MIRRORhttp://npm.taobao.org/mirrors/node export NVM_IOJS_ORG_MIRRORhttp://npm.taobao.org/mirrors/iojs# nvm环境配置 export NVM_DIR"$HOME/.nvm"[ -s &quo…...

aardio简单网站css或js下载练习

import win.ui; /*DSG{{*/ var winform win.form(text"下载网站css或js";right664;bottom290;maxfalse) winform.add( buttonClose{cls"button";text"退出";left348;top204;right498;bottom262;color14120960;fontLOGFONT(h-14);note" &qu…...

“维度削减+逻辑回归”:如何使用PCA大幅提升乳腺癌的预测成功率?

一、引言 乳腺癌是女性中最常见的恶性肿瘤之一&#xff0c;也影响着全球范围内许多人们的健康。据世界卫生组织&#xff08;WHO&#xff09;的数据&#xff0c;乳腺癌是全球癌症发病率和死亡率最高的肿瘤之一&#xff0c;其对个体和社会的危害不可忽视。因此&#xff0c;早期乳…...

Python程序设计基础:random库的使用

文章目录 一、常见的random库函数二、应用实例 一、常见的random库函数 在使用Python语言进行编程计算时&#xff0c;计算机完成的计算主要是确定的&#xff0c;但是在将其进行应用时&#xff0c;人们会模拟现实生活中的现象和活动&#xff0c;希望其增加一些随机性&#xff0…...

webpack 打包全流程

目录 1 webpack的安装 2 webpack的配置 配置流程&#xff1a; 1 webpack安装 2 创建webpack配置文件 webpack.config.js 3 配置入口 entry 单入口和多入口 2. 动态配置入口文件 4 配置出口 output 5 配置模式 mode&#xff08;webpack4&#xff09; 6 配置解析策略 …...

如何准备软件开发项目成本估算?

软件开发的成本估算是出了名的困难。对于软件开发项目来说&#xff0c;预算超支反而是常态&#xff0c;而不是例外。 在开始估算之前&#xff0c;请从业务角度了解项目的战略目标和你的目标。你可能计划尽可能赚取更多利润&#xff0c;探索新技术&#xff0c;或者在项目可能亏…...

音视频FAQ(三):音画不同步

摘要 本文介绍了音画不同步问题的五个因素&#xff1a;编码和封装阶段、网络传输阶段、播放器中的处理阶段、源内容产生的问题以及转码和编辑。针对这些因素&#xff0c;提出了相应的解决方案&#xff0c;如使用标准化工具、选择强大的传输协议、自适应缓冲等。此外&#xff0…...

MFC为控件添加背景图片

1、 添加选择Bitmap导入图片&#xff0c;图片文件最好放在项目res目录中&#xff0c;同时是BMP格式。上传后的图片在资源视图&#xff0c;命名为IDB_BITMAP_M_BACK。 2、在cpp的C***Dlg::OnPaint()函数下添加如下代码 void C***Dlg::OnPaint() {CPaintDC dc(this); // device…...

1047:判断能否被3,5,7整除

【题目描述】 给定一个整数&#xff0c;判断它能否被3&#xff0c;5&#xff0c;7整除&#xff0c;并输出以下信息&#xff1a; 1、能同时被3&#xff0c;5&#xff0c;7整除&#xff08;直接输出3 5 7&#xff0c;每个数中间一个空格&#xff09;&#xff1b; 2、只能被其中两…...

十七、DoIP诊断通信 2 (专栏:从零开始搭建一个UDS诊断自动化测试CANoe工程)

专栏:从零开始搭建一个UDS诊断自动化测试CANoe工程 文章目录 专栏:从零开始搭建一个UDS诊断自动化测试CANoe工程前言一、以太网panel面板配置二、DoIP建立连接与断开连接三、panel面板上的DoIP诊断报文发送接收SEND按钮会话切换复位1101按钮解锁按钮DTC按钮3E80保持会话前言 …...

【2023】LeetCode HOT 100——哈希

目录 1. 两数之和1.1 C++实现1.2 Python实现1.3 时空分析2. 字母异位词分组2.1 C++实现2.2 Python实现2.3 时空分析3. 最长连续序列3.1 C++实现3.2 Python实现3.3 时空分析1. 两数之和 🔗 原题链接:1. 两数之和 不妨设 i...

TCP/IP---网络层

一、网络层的主要功能 1、提供了通讯过程中&#xff0c;必须要使用的另一个地址&#xff1a;逻辑IP地址【ipv4、ipv6】 2、连接不同媒介类型【内网--外网&#xff08;intra -- inter&#xff09;】 3、根据运行的不同的路由协议&#xff0c;选择不同的最佳路径 4、在选择的最好…...

解决访问Github出现的Couldn‘t connect to server错误

文章目录 前言原因分析以及解决办法原因分析解决办法 参考 前言 在Github上面克隆代码仓库出现Failed to connect to 127.0.0.1 port 1080 after 2063 ms: Couldnt connect to server、Failed to connect to github.com port 443 after 21083 ms: Couldnt connect to server等…...

善于打仗的人,没有特别大的名气和勇功

善于打仗的人&#xff0c;没有特别大的勇功 【安志强趣讲《孙子兵法》第15讲】 【原文】 见胜不过众人之所知&#xff0c;非善之善者也&#xff1b;战胜而天下曰善&#xff0c;非善之善者也。 【趣讲白话】 预判胜负没有超出常人的见识&#xff0c;算不上高明中最高明的&#x…...

虚幻官方项目《CropOut》技术解析 之 程序化岛屿生成器(IslandGenerator)

开个新坑详细分析一下虚幻官方发布的《CropOut》&#xff0c;文章会同步发布到我在知乎|CSDN的专栏里 文章目录 概要Create Island几何体生成部分随机种子Step 1Step 2Step 3Step 4Step 5Step 6 岛屿材质部分动态为草地设置颜色 程序设计的小技巧其它Platform Switch函数 概要 …...

微服务中间件--微服务保护

微服务保护 微服务保护a.sentinelb.sentinel限流规则1) 流控模式1.a) 关联模式1.b) 链路模式 2) 流控效果2.a) 预热模式2.b) 排队等待 3) 热点参数限流 c.隔离和降级1) Feign整合Sentinel2) 线程隔离2.a) 线程隔离&#xff08;舱壁模式&#xff09; 3) 熔断降级3.a) 熔断策略-慢…...

Excel VBA 复制除指定工作表外所有的工作表的内容到一张工作表中

当我们有一张表里面有很多sheet 具有相同的表结构&#xff0c;如果需要汇总到一张表中&#xff0c;那么我们可以借助VBA 去实现汇总自动化 Sub 复制所有工作表内容()Dim ws As WorksheetDim targetSheet As WorksheetDim lastRow As Long 设置目标表格&#xff0c;即要将所有…...

电脑上安装,多版本node

手上有一个vue3的项目&#xff0c;sass配置如下图所示&#xff1a; 安装了Python3.10和node 16.14.0&#xff0c;项目能正常install 跟run。 因工作需要&#xff0c;收上有一个vue2的项目&#xff0c;sass配置如下图所示&#xff1a; 执行npm intsall 的时候一直报Python2找不…...

ssc377d修改flash分区大小

1、flash的分区默认分配16M、 / # df -h Filesystem Size Used Available Use% Mounted on /dev/root 1.9M 1.9M 0 100% / /dev/mtdblock4 3.0M...

Mybatis逆向工程,动态创建实体类、条件扩展类、Mapper接口、Mapper.xml映射文件

今天呢&#xff0c;博主的学习进度也是步入了Java Mybatis 框架&#xff0c;目前正在逐步杨帆旗航。 那么接下来就给大家出一期有关 Mybatis 逆向工程的教学&#xff0c;希望能对大家有所帮助&#xff0c;也特别欢迎大家指点不足之处&#xff0c;小生很乐意接受正确的建议&…...

el-switch文字内置

el-switch文字内置 效果 vue <div style"color:#ffffff;font-size:14px;float:left;margin-bottom:5px;margin-right:5px;">自动加载</div> <el-switch v-model"value" active-color"#3E99FB" inactive-color"#DCDFE6"…...

Qwen3-Embedding-0.6B深度解析:多语言语义检索的轻量级利器

第一章 引言&#xff1a;语义表示的新时代挑战与Qwen3的破局之路 1.1 文本嵌入的核心价值与技术演进 在人工智能领域&#xff0c;文本嵌入技术如同连接自然语言与机器理解的“神经突触”——它将人类语言转化为计算机可计算的语义向量&#xff0c;支撑着搜索引擎、推荐系统、…...

从零开始打造 OpenSTLinux 6.6 Yocto 系统(基于STM32CubeMX)(九)

设备树移植 和uboot设备树修改的内容同步到kernel将设备树stm32mp157d-stm32mp157daa1-mx.dts复制到内核源码目录下 源码修改及编译 修改arch/arm/boot/dts/st/Makefile&#xff0c;新增设备树编译 stm32mp157f-ev1-m4-examples.dtb \stm32mp157d-stm32mp157daa1-mx.dtb修改…...

UR 协作机器人「三剑客」:精密轻量担当(UR7e)、全能协作主力(UR12e)、重型任务专家(UR15)

UR协作机器人正以其卓越性能在现代制造业自动化中扮演重要角色。UR7e、UR12e和UR15通过创新技术和精准设计满足了不同行业的多样化需求。其中&#xff0c;UR15以其速度、精度及人工智能准备能力成为自动化领域的重要突破。UR7e和UR12e则在负载规格和市场定位上不断优化&#xf…...

【HTTP三个基础问题】

面试官您好&#xff01;HTTP是超文本传输协议&#xff0c;是互联网上客户端和服务器之间传输超文本数据&#xff08;比如文字、图片、音频、视频等&#xff09;的核心协议&#xff0c;当前互联网应用最广泛的版本是HTTP1.1&#xff0c;它基于经典的C/S模型&#xff0c;也就是客…...

华硕a豆14 Air香氛版,美学与科技的馨香融合

在快节奏的现代生活中&#xff0c;我们渴望一个能激发创想、愉悦感官的工作与生活伙伴&#xff0c;它不仅是冰冷的科技工具&#xff0c;更能触动我们内心深处的细腻情感。正是在这样的期许下&#xff0c;华硕a豆14 Air香氛版翩然而至&#xff0c;它以一种前所未有的方式&#x…...

Git 3天2K星标:Datawhale 的 Happy-LLM 项目介绍(附教程)

引言 在人工智能飞速发展的今天&#xff0c;大语言模型&#xff08;Large Language Models, LLMs&#xff09;已成为技术领域的焦点。从智能写作到代码生成&#xff0c;LLM 的应用场景不断扩展&#xff0c;深刻改变了我们的工作和生活方式。然而&#xff0c;理解这些模型的内部…...

Spring Security 认证流程——补充

一、认证流程概述 Spring Security 的认证流程基于 过滤器链&#xff08;Filter Chain&#xff09;&#xff0c;核心组件包括 UsernamePasswordAuthenticationFilter、AuthenticationManager、UserDetailsService 等。整个流程可分为以下步骤&#xff1a; 用户提交登录请求拦…...