当前位置: 首页 > 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;在不依赖领域特定归纳偏见的条件下实现了卓越的预测准…...

XCTF-web-easyupload

试了试php&#xff0c;php7&#xff0c;pht&#xff0c;phtml等&#xff0c;都没有用 尝试.user.ini 抓包修改将.user.ini修改为jpg图片 在上传一个123.jpg 用蚁剑连接&#xff0c;得到flag...

在鸿蒙HarmonyOS 5中实现抖音风格的点赞功能

下面我将详细介绍如何使用HarmonyOS SDK在HarmonyOS 5中实现类似抖音的点赞功能&#xff0c;包括动画效果、数据同步和交互优化。 1. 基础点赞功能实现 1.1 创建数据模型 // VideoModel.ets export class VideoModel {id: string "";title: string ""…...

【入坑系列】TiDB 强制索引在不同库下不生效问题

文章目录 背景SQL 优化情况线上SQL运行情况分析怀疑1:执行计划绑定问题?尝试:SHOW WARNINGS 查看警告探索 TiDB 的 USE_INDEX 写法Hint 不生效问题排查解决参考背景 项目中使用 TiDB 数据库,并对 SQL 进行优化了,添加了强制索引。 UAT 环境已经生效,但 PROD 环境强制索…...

高等数学(下)题型笔记(八)空间解析几何与向量代数

目录 0 前言 1 向量的点乘 1.1 基本公式 1.2 例题 2 向量的叉乘 2.1 基础知识 2.2 例题 3 空间平面方程 3.1 基础知识 3.2 例题 4 空间直线方程 4.1 基础知识 4.2 例题 5 旋转曲面及其方程 5.1 基础知识 5.2 例题 6 空间曲面的法线与切平面 6.1 基础知识 6.2…...

Spring是如何解决Bean的循环依赖:三级缓存机制

1、什么是 Bean 的循环依赖 在 Spring框架中,Bean 的循环依赖是指多个 Bean 之间‌互相持有对方引用‌,形成闭环依赖关系的现象。 多个 Bean 的依赖关系构成环形链路,例如: 双向依赖:Bean A 依赖 Bean B,同时 Bean B 也依赖 Bean A(A↔B)。链条循环: Bean A → Bean…...

面向无人机海岸带生态系统监测的语义分割基准数据集

描述&#xff1a;海岸带生态系统的监测是维护生态平衡和可持续发展的重要任务。语义分割技术在遥感影像中的应用为海岸带生态系统的精准监测提供了有效手段。然而&#xff0c;目前该领域仍面临一个挑战&#xff0c;即缺乏公开的专门面向海岸带生态系统的语义分割基准数据集。受…...

Redis:现代应用开发的高效内存数据存储利器

一、Redis的起源与发展 Redis最初由意大利程序员Salvatore Sanfilippo在2009年开发&#xff0c;其初衷是为了满足他自己的一个项目需求&#xff0c;即需要一个高性能的键值存储系统来解决传统数据库在高并发场景下的性能瓶颈。随着项目的开源&#xff0c;Redis凭借其简单易用、…...

VisualXML全新升级 | 新增数据库编辑功能

VisualXML是一个功能强大的网络总线设计工具&#xff0c;专注于简化汽车电子系统中复杂的网络数据设计操作。它支持多种主流总线网络格式的数据编辑&#xff08;如DBC、LDF、ARXML、HEX等&#xff09;&#xff0c;并能够基于Excel表格的方式生成和转换多种数据库文件。由此&…...

【实施指南】Android客户端HTTPS双向认证实施指南

&#x1f510; 一、所需准备材料 证书文件&#xff08;6类核心文件&#xff09; 类型 格式 作用 Android端要求 CA根证书 .crt/.pem 验证服务器/客户端证书合法性 需预置到Android信任库 服务器证书 .crt 服务器身份证明 客户端需持有以验证服务器 客户端证书 .crt 客户端身份…...