AcWing 6099. 座位
原题目链接
问题描述
有 n
头奶牛(n ≥ 5
),编号为 1 ∼ n
,按照某种顺序围着一张圆桌坐成一圈。
奶牛之间存在如下的朋友关系:
- 如果两头奶牛相邻,则它们是朋友;
- 如果两头奶牛之间只隔着一头奶牛,它们也是朋友。
例如,如果共有 5 头奶牛,沿顺时针方向按 1∼5
的顺序就座,则共有如下 10 对朋友关系:
(1,2), (2,3), (3,4), (4,5), (5,1),
(1,3), (2,4), (3,5), (4,1), (5,2)
不难发现,当 n ≥ 5
时,一共会有 2n
对朋友关系。
现在,给定这 2n
对朋友关系,请你输出一种可能的奶牛就座顺序。
输入格式
- 第一行:一个整数
n
,表示奶牛的数量。 - 接下来
2n
行:每行包含两个整数aᵢ, bᵢ
,表示一对给定的朋友关系。
输入保证同一对朋友关系不会重复给出。
输出格式
- 如果给定的朋友关系存在错误,导致无解,则输出
-1
。 - 否则,请输出任意一头奶牛作为起点,并沿顺时针或逆时针方向输出一组 n 个奶牛编号,表示一个合法的就座顺序。
如果方案不唯一,可以输出任意一种合理方案。
数据范围
- 前 5 个测试点满足:
5 ≤ n ≤ 10
- 所有测试点满足:
5 ≤ n ≤ 10⁵
1 ≤ aᵢ, bᵢ ≤ n
aᵢ ≠ bᵢ
输入样例 1
5
1 2
2 3
3 4
4 5
5 1
1 3
2 4
3 5
4 1
5 2
输出样例 1
1 2 3 4 5
输入样例 2
6
5 6
4 3
5 3
2 4
6 1
3 1
6 2
2 5
1 4
3 6
1 2
4 5
输出样例 2
1 2 4 5 3 6
c++代码
#include<bits/stdc++.h>
#include<stdio.h>using namespace std;int n, a, b;
vector<unordered_set<int>> arr;
vector<bool> know;
vector<int> mid, tem;int main() {scanf("%d", &n);arr = vector<unordered_set<int>>(n + 1);for (int i = 0; i < 2 * n; i++) {scanf("%d %d", &a, &b);if (a == b || arr[a].find(b) != arr[a].end() || arr[b].find(a) != arr[b].end()) {printf("-1");return 0;}arr[a].insert(b);arr[b].insert(a);if (a == 1) tem.push_back(b);if (b == 1) tem.push_back(a);}if (tem.size() != 4) {printf("-1");return 0;}sort(tem.begin(), tem.end());do {mid.clear();mid = { tem[0], tem[1], 1, tem[2], tem[3] };if (arr[tem[0]].find(tem[1]) == arr[tem[0]].end()|| arr[tem[1]].find(tem[2]) == arr[tem[1]].end()|| arr[tem[2]].find(tem[3]) == arr[tem[2]].end()) continue;know = vector<bool>(n + 1, false);know[tem[0]] = true, know[tem[1]] = true, know[tem[2]] = true, know[tem[3]] = true, know[1] = true;for (int i = 3; i <= n - 3; i++) {int k, cont = 0;for (int x : arr[mid[i]]) {if (x == mid[i - 1] || x == mid[i - 2] || x == mid[i + 1]) {cont++;continue;}else k = x;}if (cont != 3 || know[k]) break;mid.push_back(k);know[k] = true;}if (mid.size() != n) continue;int i = 0;for (i = 0; i < n; i++) {vector<int> res(4);res[0] = (i + 1) % n, res[1] = (i + 2) % n, res[2] = (i + n - 1) % n, res[3] = (i + n - 2) % n;int j = 0;for (j = 0; j < 4; j++) {if (arr[mid[i]].find(mid[res[j]]) == arr[mid[i]].end()) break;}if (j != 4) break;}if (i != n) continue;for (i = 0; i < n; i++) {printf("%d ", mid[i]);}return 0;} while (next_permutation(tem.begin(), tem.end()));printf("-1");return 0;
}//by wqs
相关文章:
AcWing 6099. 座位
原题目链接 问题描述 有 n 头奶牛(n ≥ 5),编号为 1 ∼ n,按照某种顺序围着一张圆桌坐成一圈。 奶牛之间存在如下的朋友关系: 如果两头奶牛相邻,则它们是朋友;如果两头奶牛之间只隔着一头奶…...
MySQL SQL Mode
SQL Mode 是 MySQL 中一个重要的系统变量,它决定了 MySQL 应遵循的 SQL 语法规则和数据验证规则。 什么是 SQL Mode SQL Mode 定义了 MySQL 应该支持的 SQL 语法以及执行数据验证的方式。通过设置不同的 SQL Mode,可以让 MySQL 在不同程度上兼容其他数据…...
linux不同用户共享同一anaconda
这里写目录标题 1、anaconda安装2、所有账号可以访问conda 按一下步骤顺序执行,可使linux上不同权限隔离的用户可以同时访问anaconda。 1、anaconda安装 step1:anaconda是通过root账号安装在某个自定义目录下(如:/data/software/…...
Langflow 远程命令执行漏洞复现(CVE-2025-3248)(附脚本)
免责申明: 本文所描述的漏洞及其复现步骤仅供网络安全研究与教育目的使用。任何人不得将本文提供的信息用于非法目的或未经授权的系统测试。作者不对任何由于使用本文信息而导致的直接或间接损害承担责任。如涉及侵权,请及时与我们联系,我们将尽快处理并删除相关内容。 前言…...
如何在 Excel 中处理并拆分你提供的这种混合单位的库存数据。
使用 Power Query (获取与转换数据) - 最推荐 这是处理这类复杂、不规范数据的最强大、最灵活的方法,尤其适合数据量大或需要重复处理的情况。 加载数据到 Power Query: 选中你的数据区域。 在 Excel 菜单栏点击 数据 选项卡。 在 获取和转换数据 功能…...
OpenHarmony荷兰研习会回顾 | 仓颉语言赋能原生应用开发实践
近日,由全球顶级学术峰会EuroSys/ASPLOS和OpenHarmony社区在荷兰鹿特丹合办的操作系统深度研习会圆满收官,本次研习会以"架构探秘-开发实践-创新实验"三位一体的进阶模式,为全球开发者构建了沉浸式技术探索平台。其中,由…...
广州华锐视点考试考核系统:引领智能考核新时代
在当今数字化飞速发展的时代,考试考核作为教育与培训成果检验的重要环节,也在不断寻求创新与突破。广州华锐视点凭借其先进的技术实力,打造出了一套功能强大、高效便捷的考试考核系统,为各类教育机构、企业培训等提供了全面且优质…...
Harmony鸿蒙应用开发-录音保存并播放音频
功能介绍: 录音并保存为m4a格式的音频,然后播放该音频,参考文档使用AVRecorder开发音频录制功能(ArkTS),更详细接口信息请查看接口文档:ohos.multimedia.media (媒体服务)。 知识点: 熟悉使用AVRecorder…...
室分系统(室内分布系统)详解
室分系统(室内分布系统,Indoor Distribution System)是用于解决建筑物内部信号弱、覆盖差、容量不足的专用通信网络,广泛应用于商场、写字楼、地铁、机场等场景。 1. 室分系统的作用 解决信号覆盖问题:消除室内盲区&am…...
基于 Qt4 的图片处理工具开发(二):增加对比度调节、界面布局优化、多线程操作
废话不多说,先来看一下最终的界面效果 一、引言 在上一篇博客中,我们完成了图片处理工具的基础框架,实现了拖拽加载、亮度调节和角度旋转功能。本文将聚焦界面布局重构、对比度调节功能扩展以及多线程性能优化,进一步提升工具的实…...
禁止页面滚动的方法-微信小程序
在微信小程序中,有几种方法可以禁止页面滚动: 一、通过页面配置禁止滚动 在页面的JSON配置文件中设置,此方法完全禁止页面的滚动行为: {"disableScroll": true }二、通过 CSS 样式禁止滚动 在页面的WXSS文件中添加&…...
基于landsat与Modis影像的遥感技术的生态环境质量评价
本次将结合ArcGIS与ENVI,发布 landsat与Modis影像的遥感技术的生态环境质量评价技术专题,专题课程学习! 在反映生态质量的诸多自然因素中,绿度、湿度、热度、干度可谓是与人类生存息息相关的4个重要指标,也是人类直观…...
蓝桥杯刷题--宝石组合
在一个神秘的森林里,住着一个小精灵名叫小蓝。有一天,他偶然发现了一个隐藏在树洞里的宝藏,里面装满了闪烁着美丽光芒的宝石。这些宝石都有着不同的颜色和形状,但最引人注目的是它们各自独特的 “闪亮度” 属性。每颗宝石都有一个…...
记录一下学习docker的命令(不断补充中)
#2025-04-10,22:12############### 在wsl2中安装了ubuntu24.04.1后有部署了docker, 如果没有启动docker可以通过下列命令启动docker: sudo systemctl start docker 执行下列命令可以看到docker状态,并不占用控制台的命令: su…...
沃伦森电机状态传感器RS-MTS01:智能运维的解决方案
行业工况背景 一、方案背景 在现代工业生产中,电机发挥着至关重要的作用,其运行状况直接关联到生产效率、产品质量以及成本控制。传统的电机维护主要依赖于定期的巡检和事后维修,这种方式难以提前发现潜在的故障隐患,容易导致意外…...
设计模式:单例模式
复习一下: 单例模式(Singleton Pattern) 原理: 单例模式确保一个类只有一个实例,并提供一个全局访问点来获取这个实例。它通过将类的构造函数设为私有,防止外部代码直接实例化该类。同时,提供…...
电商素材革命:影刀RPA魔法指令3.0驱动批量去水印,实现秒级素材净化
本文 去除水印实操视频展示电商图片水印处理的困境影刀 RPA 魔法指令 3.0 强势登场利用魔法指令3.0两步实现去除水印操作关于影刀RPA 去除水印实操视频展示 我们这里选择了4张小红书里面比较帅气的图片,但凡用过小红书的都知道,小红书右下角是会有小…...
解析 WebSocket 协议的基本原理
随着互联网的快速发展,Web 应用对实时通信的需求越来越高。传统的 HTTP 协议无法满足实时性的要求,而 WebSocket 协议则应运而生。WebSocket 是一种新型的协议,允许在一个单独的持久连接上进行全双工的通信,提供了更高效、实时的数…...
学生管理系统(Python)
运行结果: 源代码: """ 项目:类似于学生管理系统---增删改查 """ #封装一个学生类 import random class Student: def __init__(self,stuid,name,score): self.stuid stuid self.name name self.score …...
Java抽象类:深入理解与应用
一、引言 在Java的面向对象编程中,抽象类(Abstract Class)是一个非常重要的概念。它允许我们定义一个类,该类中包含一些抽象方法和非抽象方法,但自己不能被实例化。抽象类主要用于创建类的层次结构,并为子…...
下垂控制的定义与应用解析
下垂控制(Droop Control)是一种广泛应用于微电网、逆变器及分布式电源系统的控制策略,其核心思想是通过模拟传统同步发电机的下垂特性,实现电力系统中电压、频率的稳定以及功率的合理分配。以下是其关键解释及参考依据:…...
oracle 并行度(Parallel Degree)
在Oracle数据库中,并行度(Parallel Degree) 是用于控制并行处理任务的关键配置,旨在通过多进程协作加速大规模数据处 一、并行度的核心概念 并行度(DOP, Degree of Parallelism) 表示一个操作同时使用的并…...
轻量级碎片化笔记memos本地NAS部署与跨平台跨网络同步笔记实战
文章目录 前言1. 使用Docker部署memos2. 注册账号与简单操作演示3. 安装cpolar内网穿透4. 创建公网地址5. 创建固定公网地址 推荐 前些天发现了一个巨牛的人工智能学习网站,通俗易懂,风趣幽默,忍不住分享一下给大家。 点击跳转到网站 前言…...
心有猛虎,细嗅蔷薇
2025年4月10日,13~28℃,还好 待办: 融智云考平台《物理》《物理2》《地理》《地理1》重修试卷 冶金《物理》课程标准 教学技能大赛PPT教案 遇见:网友过得挺好的。 感受:和网友说话还是不错的。 反思:无。 …...
借助DeepSeek开启学术写作高效通道
摘要 在学术研究领域,撰写高质量论文是研究者成果展示与学术交流的关键环节。然而,传统论文写作过程复杂,常使研究者面临诸多挑战。随着人工智能技术的发展,DeepSeek等工具为论文写作带来新契机。本文深入剖析利用DeepSeek进行论文…...
interrupt子系统中的数据结构
我们接着上一篇,开始真正的interrupt子系统: 现在有一个共享的中断,网卡跟开关共享同一个gpio中断,然后当触发中断的时候,GIC会发信号给CPU,告诉他已经发生了中断了,然后CPU会去读取GIC里面的寄…...
本地浏览器运行服务器jupyter文件
之前不知道要设置密码 一直登不上 远程linux服务器中安装jupyter通过本地浏览器访问使用_服务器jupyter 本地浏览器访问-CSDN博客...
P1331 洛谷 海战
题目描述 思路 这个题需要读懂题意,即“什么样的形式表示两只船相撞?” ----> 上下相邻或左右相邻 如果图是不和法的,一定存在如下结构: # # . # 或 # # # . 或 # . # # 或 . # # #即四个格子里有三个#,一个"…...
如何开发iOS辅助工具?iOS按键精灵帮你实现
强大的辅助工具可以支持自动化操作,轻松实现一键点击、滑动、输入等操作,无论是游戏挂机、日常任务还是批量处理,都能高效完成。 在按键精灵中针对新手用户和资深开发作者都有路径实现游戏的任务点击。 新手用户推荐使用录制功能以及连点器…...
数据可视化 —— 柱形图应用(大全)
一、案例一:单柱形图 1.导入库 import matplotlib.pyplot as plt import pandas as pd import numpy as np 2.给窗口名称和画布大小 plt.figure(num单柱形图, figsize(6, 4), facecolorw) 3.定义x、y轴的数据 # range(0-4) x np.arange(5) # 创建数组 y1 np.a…...
NLP高频面试题(三十九)——什么是大模型的涌现能力?
在人工智能领域,随着模型规模的扩大,研究人员观察到大型语言模型会展现出一些在小型模型中未曾出现的全新能力,这种现象被称为涌现能力。这些能力并非通过特定编程或训练目标直接获得,而是在模型参数和训练数据达到一定规模后自发出现的。 为什么会产生涌现能力? 涌现能…...
课程发布|ROS+PX4固定翼无人机仿真开发课程
课程链接(限时优惠): ROSPX4固定翼无人机仿真开发课程https://www.bilibili.com/cheese/play/ss131501135...
使用 VcXsrv 在 Windows 10 上运行 Ubuntu 图形界面
VcXsrv 是一款用于 Windows 的开源 X 服务器,它允许在 Windows 系统上显示 Linux 的图形应用程序。当在 Windows 10 上安装并正确配置 VcXsrv 后,通过设置 WSL2 中的DISPLAY环境变量,使其指向运行 VcXsrv 的 Windows 主机的 IP 地址ÿ…...
Java中的参数是值传递还是引用传递?
在java中, 参数传递只有值传递 ,不论是基本类型还是引用类型。 其中的区别在于: 基本数据类型(如byte,short,int等):传递的参数是值的副本,即基本类型的数值本身。因此在方法中&am…...
SD教程|AI绘画软件Stable Diffusion的Lora模型详解与使用教程
一、引言 在[AI绘画 领域,StableDiffusion作为一种强大的文本到图像的生成模型,已经吸引了众多艺术家和爱好者的关注。而Lora(Low-RankAdaptation)模型作为StableDiffusion的一个重要扩展,进一步提升了模型的微调效率…...
矢量网络分析仪测试S参数注意事项
正式测试S参数之前一定要先校准 测量1个端口时,校准步骤如下: 开路(Open); 短路(Short); 负载(Load)。 测试2个端口时,校准步骤如下: …...
模拟-与-现实协同训练:基于视觉机器人操控的简单方法
25年3月来自 UT Austin、Nvidia、UC Berkeley 和纽约大学的论文“Sim-and-Real Co-Training: A Simple Recipe for Vision-Based Robotic Manipulation”。 大型现实世界机器人数据集在训练通才机器人模型方面拥有巨大潜力,但扩展现实世界人类数据收集既耗时又耗资…...
期权与期货的在险价值
在险价值(Value at Risk,VaR) 在险价值(Value at Risk,VaR)是指在一定概率水平 α % \alpha\% α%(置信水平)下,某金融资产或资产组合的价值在未来特定时期(…...
消防设施操作员证书用途有哪些
消防设施操作员证书是国家职业资格证书之一,持有该证书表明具备从事消防设施操作、监控、维护等工作的专业资格。其具体用途和重要性如下: 一、主要用途 就业准入资格 根据《消防法》及相关规定,从事消防控制室值班、消防设施操作与维护等…...
【C++ 内存管理】静态分配和动态分配
文章目录 1.静态分配2.动态分配3.对静态分配和动态分配理解4.析构函数调用顺序5.new[ ] 为什么会多申请内存呢? 1.静态分配 定义: 在编译阶段确定内存大小和生命周期,由编译器自动分配和释放。 特点: ①分配时机:程序…...
基于autokeras的简单天气预报例子和运行输出
import numpy as np from autokeras import StructuredDataClassifier from sklearn.model_selection import train_test_split from sklearn.preprocessing import StandardScaler # 模拟数据 np.random.seed(0) n_samples 1000 X np.random.rand(n_samples, 3…...
云服务器的入门了解
首先,用户可能对云计算和云服务器的基本概念不太清楚,需要先做一个简单易懂的定义,避免使用太多技术术语。接下来,要说明云服务器和传统物理服务器的区别,强调云服务器的优势,比如弹性扩展、按需付费等。 然…...
Navicat连接远程PostGreSQL失败
问题描述 使用本地Navicat连接Windows远程服务器上部署的PostGreSQL数据库时,出现以下错误: 解决方案 出现以上报错信息,是因为PostGreSQL数据库服务尚未设置允许客户端建立远程连接。可做如下配置, 1. 找到PostGreSQL数据库安装目录下的data子文件夹,重点关注:postgres…...
经济金融最优化:从理论到MATLAB实践——最大利润问题全解析
内容摘要 本文聚焦经济金融领域的最大利润问题,深入探讨不考虑销售影响和考虑销售影响两种情形下的利润最大化模型柯布 - 道格拉斯生产函数等理论构建与求解。 关键词:经济金融;最大利润问题;柯布-道格拉斯生产函数 1. 引言 在…...
“AI工业革命2.0”:大语言模型驱动的行业再造浪潮
📝个人主页🌹:慌ZHANG-CSDN博客 🌹🌹期待您的关注 🌹🌹 一、引言:从“工具”到“力量”的跃迁 当人工智能步入大模型时代,尤其以ChatGPT、DeepSeek、Grok 等为代表的大语言模型不断刷新人类对智能的认知边界,它们不再只是工具,而是逐步变成了行业逻辑的重构力…...
AI日报 - 2025年4月11日
🌟 今日概览(60秒速览) ▎🤖 模型突破 | 学术界发布5B模型生成1分钟连贯视频;Pokemon AI达人类水平;Kimi-VL开源;Llama-Nemotron-Ultra 253B发布;Google Gemini长文本处理达200万token。 ▎💼 商…...
企业安全用电 智能物联网断路器 功能参数介绍
安科瑞刘鸿鹏 摘要 随着城市化和智能化建设的不断推进,现代建筑对用电系统的安全性、可视化管理和智能化控制提出了更高的要求。传统空气开关已无法满足当前电力系统对故障预警、远程控制及能效管理的复杂需求。本文结合安科瑞ASCB2LE125系列物联网漏电断路器的功…...
python:all列表
1.all列表的说明: 当模块中有__all__变量时,当使用from xxx import *时,只能导入这个列表中的元素。 2.具体的例子: 1.先创建一个模块my_mod,在列表__all__中分别写入第一次只写入test1,第二次写入test1、test2两个…...
ctfshow VIP题目限免 js敏感信息泄露
根据题目提示是 js 敏感信息泄露,那我就右键查看源代码看看能不能发现 js 文件 访问这个 js 文件 发现了“玩101分给你flag”的源码,还有一段密文,找个在线网站解密一下(解码UTF16成文字转换器在线) 这句话的意思是去…...
git 提交空文件夹
git 提交空文件夹 方法1:使用 .gitkeep 文件 touch path/to/empty/folder/.gitkeep git add path/to/empty/folder/.gitkeep git commit -m "Add .gitkeep to track empty folder"...