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 大意:给出一个 n 个数组成的环 , 要对环上的点染色 , 要求任意一个相邻数不同的点对染色不同 ,求使用最少的颜色数 , 并用颜色数排列构造一种染色方案。 思路…...
什么是SaaS、PaaS、aPaaS、iPaaS、IaaS,一文讲透
在数字化的带动下,各行业对云服务的需求进入快速增长期。 SaaS、PaaS、aPaaS、iPaaS、IaaS…… 这些词经常出现,那么他们分别是什么意思?又有什么区别?小帆带大家一起来看看~ SaaS SaaS,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大幅提升乳腺癌的预测成功率?
一、引言 乳腺癌是女性中最常见的恶性肿瘤之一,也影响着全球范围内许多人们的健康。据世界卫生组织(WHO)的数据,乳腺癌是全球癌症发病率和死亡率最高的肿瘤之一,其对个体和社会的危害不可忽视。因此,早期乳…...
Python程序设计基础:random库的使用
文章目录 一、常见的random库函数二、应用实例 一、常见的random库函数 在使用Python语言进行编程计算时,计算机完成的计算主要是确定的,但是在将其进行应用时,人们会模拟现实生活中的现象和活动,希望其增加一些随机性࿰…...
webpack 打包全流程
目录 1 webpack的安装 2 webpack的配置 配置流程: 1 webpack安装 2 创建webpack配置文件 webpack.config.js 3 配置入口 entry 单入口和多入口 2. 动态配置入口文件 4 配置出口 output 5 配置模式 mode(webpack4) 6 配置解析策略 …...
如何准备软件开发项目成本估算?
软件开发的成本估算是出了名的困难。对于软件开发项目来说,预算超支反而是常态,而不是例外。 在开始估算之前,请从业务角度了解项目的战略目标和你的目标。你可能计划尽可能赚取更多利润,探索新技术,或者在项目可能亏…...
音视频FAQ(三):音画不同步
摘要 本文介绍了音画不同步问题的五个因素:编码和封装阶段、网络传输阶段、播放器中的处理阶段、源内容产生的问题以及转码和编辑。针对这些因素,提出了相应的解决方案,如使用标准化工具、选择强大的传输协议、自适应缓冲等。此外࿰…...
MFC为控件添加背景图片
1、 添加选择Bitmap导入图片,图片文件最好放在项目res目录中,同时是BMP格式。上传后的图片在资源视图,命名为IDB_BITMAP_M_BACK。 2、在cpp的C***Dlg::OnPaint()函数下添加如下代码 void C***Dlg::OnPaint() {CPaintDC dc(this); // device…...
1047:判断能否被3,5,7整除
【题目描述】 给定一个整数,判断它能否被3,5,7整除,并输出以下信息: 1、能同时被3,5,7整除(直接输出3 5 7,每个数中间一个空格); 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、提供了通讯过程中,必须要使用的另一个地址:逻辑IP地址【ipv4、ipv6】 2、连接不同媒介类型【内网--外网(intra -- inter)】 3、根据运行的不同的路由协议,选择不同的最佳路径 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等…...
善于打仗的人,没有特别大的名气和勇功
善于打仗的人,没有特别大的勇功 【安志强趣讲《孙子兵法》第15讲】 【原文】 见胜不过众人之所知,非善之善者也;战胜而天下曰善,非善之善者也。 【趣讲白话】 预判胜负没有超出常人的见识,算不上高明中最高明的&#x…...
虚幻官方项目《CropOut》技术解析 之 程序化岛屿生成器(IslandGenerator)
开个新坑详细分析一下虚幻官方发布的《CropOut》,文章会同步发布到我在知乎|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) 线程隔离(舱壁模式) 3) 熔断降级3.a) 熔断策略-慢…...
Excel VBA 复制除指定工作表外所有的工作表的内容到一张工作表中
当我们有一张表里面有很多sheet 具有相同的表结构,如果需要汇总到一张表中,那么我们可以借助VBA 去实现汇总自动化 Sub 复制所有工作表内容()Dim ws As WorksheetDim targetSheet As WorksheetDim lastRow As Long 设置目标表格,即要将所有…...
电脑上安装,多版本node
手上有一个vue3的项目,sass配置如下图所示: 安装了Python3.10和node 16.14.0,项目能正常install 跟run。 因工作需要,收上有一个vue2的项目,sass配置如下图所示: 执行npm intsall 的时候一直报Python2找不…...
在rocky linux 9.5上在线安装 docker
前面是指南,后面是日志 sudo dnf config-manager --add-repo https://download.docker.com/linux/centos/docker-ce.repo sudo dnf install docker-ce docker-ce-cli containerd.io -y docker version sudo systemctl start docker sudo systemctl status docker …...
Day131 | 灵神 | 回溯算法 | 子集型 子集
Day131 | 灵神 | 回溯算法 | 子集型 子集 78.子集 78. 子集 - 力扣(LeetCode) 思路: 笔者写过很多次这道题了,不想写题解了,大家看灵神讲解吧 回溯算法套路①子集型回溯【基础算法精讲 14】_哔哩哔哩_bilibili 完…...
从零实现STL哈希容器:unordered_map/unordered_set封装详解
本篇文章是对C学习的STL哈希容器自主实现部分的学习分享 希望也能为你带来些帮助~ 那咱们废话不多说,直接开始吧! 一、源码结构分析 1. SGISTL30实现剖析 // hash_set核心结构 template <class Value, class HashFcn, ...> class hash_set {ty…...
uniapp微信小程序视频实时流+pc端预览方案
方案类型技术实现是否免费优点缺点适用场景延迟范围开发复杂度WebSocket图片帧定时拍照Base64传输✅ 完全免费无需服务器 纯前端实现高延迟高流量 帧率极低个人demo测试 超低频监控500ms-2s⭐⭐RTMP推流TRTC/即构SDK推流❌ 付费方案 (部分有免费额度&#x…...
LLM基础1_语言模型如何处理文本
基于GitHub项目:https://github.com/datawhalechina/llms-from-scratch-cn 工具介绍 tiktoken:OpenAI开发的专业"分词器" torch:Facebook开发的强力计算引擎,相当于超级计算器 理解词嵌入:给词语画"…...
Mac下Android Studio扫描根目录卡死问题记录
环境信息 操作系统: macOS 15.5 (Apple M2芯片)Android Studio版本: Meerkat Feature Drop | 2024.3.2 Patch 1 (Build #AI-243.26053.27.2432.13536105, 2025年5月22日构建) 问题现象 在项目开发过程中,提示一个依赖外部头文件的cpp源文件需要同步,点…...
DeepSeek 技术赋能无人农场协同作业:用 AI 重构农田管理 “神经网”
目录 一、引言二、DeepSeek 技术大揭秘2.1 核心架构解析2.2 关键技术剖析 三、智能农业无人农场协同作业现状3.1 发展现状概述3.2 协同作业模式介绍 四、DeepSeek 的 “农场奇妙游”4.1 数据处理与分析4.2 作物生长监测与预测4.3 病虫害防治4.4 农机协同作业调度 五、实际案例大…...
wpf在image控件上快速显示内存图像
wpf在image控件上快速显示内存图像https://www.cnblogs.com/haodafeng/p/10431387.html 如果你在寻找能够快速在image控件刷新大图像(比如分辨率3000*3000的图像)的办法,尤其是想把内存中的裸数据(只有图像的数据,不包…...
MySQL 主从同步异常处理
阅读原文:https://www.xiaozaoshu.top/articles/mysql-m-s-update-pk MySQL 做双主,遇到的这个错误: Could not execute Update_rows event on table ... Error_code: 1032是 MySQL 主从复制时的经典错误之一,通常表示ÿ…...
MySQL的pymysql操作
本章是MySQL的最后一章,MySQL到此完结,下一站Hadoop!!! 这章很简单,完整代码在最后,详细讲解之前python课程里面也有,感兴趣的可以往前找一下 一、查询操作 我们需要打开pycharm …...
