当前位置: 首页 > 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找不…...

未来机器人的大脑:如何用神经网络模拟器实现更智能的决策?

编辑&#xff1a;陈萍萍的公主一点人工一点智能 未来机器人的大脑&#xff1a;如何用神经网络模拟器实现更智能的决策&#xff1f;RWM通过双自回归机制有效解决了复合误差、部分可观测性和随机动力学等关键挑战&#xff0c;在不依赖领域特定归纳偏见的条件下实现了卓越的预测准…...

conda相比python好处

Conda 作为 Python 的环境和包管理工具&#xff0c;相比原生 Python 生态&#xff08;如 pip 虚拟环境&#xff09;有许多独特优势&#xff0c;尤其在多项目管理、依赖处理和跨平台兼容性等方面表现更优。以下是 Conda 的核心好处&#xff1a; 一、一站式环境管理&#xff1a…...

3.3.1_1 检错编码(奇偶校验码)

从这节课开始&#xff0c;我们会探讨数据链路层的差错控制功能&#xff0c;差错控制功能的主要目标是要发现并且解决一个帧内部的位错误&#xff0c;我们需要使用特殊的编码技术去发现帧内部的位错误&#xff0c;当我们发现位错误之后&#xff0c;通常来说有两种解决方案。第一…...

【Redis技术进阶之路】「原理分析系列开篇」分析客户端和服务端网络诵信交互实现(服务端执行命令请求的过程 - 初始化服务器)

服务端执行命令请求的过程 【专栏简介】【技术大纲】【专栏目标】【目标人群】1. Redis爱好者与社区成员2. 后端开发和系统架构师3. 计算机专业的本科生及研究生 初始化服务器1. 初始化服务器状态结构初始化RedisServer变量 2. 加载相关系统配置和用户配置参数定制化配置参数案…...

定时器任务——若依源码分析

分析util包下面的工具类schedule utils&#xff1a; ScheduleUtils 是若依中用于与 Quartz 框架交互的工具类&#xff0c;封装了定时任务的 创建、更新、暂停、删除等核心逻辑。 createScheduleJob createScheduleJob 用于将任务注册到 Quartz&#xff0c;先构建任务的 JobD…...

第25节 Node.js 断言测试

Node.js的assert模块主要用于编写程序的单元测试时使用&#xff0c;通过断言可以提早发现和排查出错误。 稳定性: 5 - 锁定 这个模块可用于应用的单元测试&#xff0c;通过 require(assert) 可以使用这个模块。 assert.fail(actual, expected, message, operator) 使用参数…...

全面解析各类VPN技术:GRE、IPsec、L2TP、SSL与MPLS VPN对比

目录 引言 VPN技术概述 GRE VPN 3.1 GRE封装结构 3.2 GRE的应用场景 GRE over IPsec 4.1 GRE over IPsec封装结构 4.2 为什么使用GRE over IPsec&#xff1f; IPsec VPN 5.1 IPsec传输模式&#xff08;Transport Mode&#xff09; 5.2 IPsec隧道模式&#xff08;Tunne…...

深度学习水论文:mamba+图像增强

&#x1f9c0;当前视觉领域对高效长序列建模需求激增&#xff0c;对Mamba图像增强这方向的研究自然也逐渐火热。原因在于其高效长程建模&#xff0c;以及动态计算优势&#xff0c;在图像质量提升和细节恢复方面有难以替代的作用。 &#x1f9c0;因此短时间内&#xff0c;就有不…...

省略号和可变参数模板

本文主要介绍如何展开可变参数的参数包 1.C语言的va_list展开可变参数 #include <iostream> #include <cstdarg>void printNumbers(int count, ...) {// 声明va_list类型的变量va_list args;// 使用va_start将可变参数写入变量argsva_start(args, count);for (in…...

Sklearn 机器学习 缺失值处理 获取填充失值的统计值

💖亲爱的技术爱好者们,热烈欢迎来到 Kant2048 的博客!我是 Thomas Kant,很开心能在CSDN上与你们相遇~💖 本博客的精华专栏: 【自动化测试】 【测试经验】 【人工智能】 【Python】 使用 Scikit-learn 处理缺失值并提取填充统计信息的完整指南 在机器学习项目中,数据清…...