编程之美测试赛第二题—大神与三位小伙伴

2024-08-28 08:08

本文主要是介绍编程之美测试赛第二题—大神与三位小伙伴,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

大神与三位小伙伴

时间限制: 2000ms
单点时限: 1000ms
内存限制: 256MB

描述

给定2个树A和B,保证A的节点个数>=B的节点个数。

现在你需要对树A的边进行二染色。

一个好的染色方案,指不存在一个树A中的连通块,同时满足以下2个条件

1. 其中只有同色的边

2. 和B同构。两个树同构是指,存在一个一一映射(既是单射又是满射),将树B的各节点映射到不同的树A的节点,使得原来在树B中相邻的点,在映射后,仍相邻。

问是否存在一种好的染色方案。


输入

第一行一个整数T (1<=T<=10),表示数据组数。

接下来是T组输入数据,测试数据之间没有空行。


每组数据格式如下:

第一行一个整数N ,表示树A的节点总数。

接下来N-1行,每行2个数a, b (1 <= a, b <= N)表示树A的节点a和b之间有一条边。

接下来一行,一个整数M(1 <= M <= N),表示树B的节点总数。

接下来M-1行,每行2个数a, b (1 <= a, b <= M)表示树B的节点a和b之间有一条边。


输出

对每组数据,先输出“Case x: ”,x表示是第几组数据,然后接“YES”/“NO”,表示是否存在所求的染色方案。


数据范围

小数据:1 <= N <= 20

大数据:1 <= N <= 1000000


样例解释

无论如何染色,只要从A中挑一条边就行了。


样例输入
1
3
1 2
2 3
2
1 2
样例输出
Case 1: NO
  • 此题比较简单,自己推了一下数学公式,基本上就一次性AC了。1^3+2^3+...+n^3+i*j*k*6对不同ijk求和(i<j<k)
  • 下面是AC代码,第一题没看懂题目,第三题感觉很难考虑的问题太多,应该是DFS+剪枝吧。细细的想象。。。。。
  • #include<iostream>
    using namespace std;
    long long ans=0;
    const int maxn=1e9+7;int main(){int T,n;cin>>T;for(int count=1;count<=T;count++){cin>>n;ans=0;for(int i=1;i<=n;i++)ans=(ans+i*i*i)%maxn;for(int i=1;i<=n-2;i++)for(int j=i+1;j<=n-1;j++)for(int k=j+1;k<=n;k++)ans=(ans+i*j*k*6)%maxn;cout<<"Case "<<count<<":"<<ans<<endl;}return 0;
    }


这篇关于编程之美测试赛第二题—大神与三位小伙伴的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1114207

相关文章

闲置电脑也能活出第二春?鲁大师AiNAS让你动动手指就能轻松部署

对于大多数人而言,在这个“数据爆炸”的时代或多或少都遇到过存储告急的情况,这使得“存储焦虑”不再是个别现象,而将会是随着软件的不断臃肿而越来越普遍的情况。从不少手机厂商都开始将存储上限提升至1TB可以见得,我们似乎正处在互联网信息飞速增长的阶段,对于存储的需求也将会不断扩大。对于苹果用户而言,这一问题愈发严峻,毕竟512GB和1TB版本的iPhone可不是人人都消费得起的,因此成熟的外置存储方案开

性能测试介绍

性能测试是一种测试方法,旨在评估系统、应用程序或组件在现实场景中的性能表现和可靠性。它通常用于衡量系统在不同负载条件下的响应时间、吞吐量、资源利用率、稳定性和可扩展性等关键指标。 为什么要进行性能测试 通过性能测试,可以确定系统是否能够满足预期的性能要求,找出性能瓶颈和潜在的问题,并进行优化和调整。 发现性能瓶颈:性能测试可以帮助发现系统的性能瓶颈,即系统在高负载或高并发情况下可能出现的问题

字节面试 | 如何测试RocketMQ、RocketMQ?

字节面试:RocketMQ是怎么测试的呢? 答: 首先保证消息的消费正确、设计逆向用例,在验证消息内容为空等情况时的消费正确性; 推送大批量MQ,通过Admin控制台查看MQ消费的情况,是否出现消费假死、TPS是否正常等等问题。(上述都是临场发挥,但是RocketMQ真正的测试点,还真的需要探讨) 01 先了解RocketMQ 作为测试也是要简单了解RocketMQ。简单来说,就是一个分

Linux 网络编程 --- 应用层

一、自定义协议和序列化反序列化 代码: 序列化反序列化实现网络版本计算器 二、HTTP协议 1、谈两个简单的预备知识 https://www.baidu.com/ --- 域名 --- 域名解析 --- IP地址 http的端口号为80端口,https的端口号为443 url为统一资源定位符。CSDNhttps://mp.csdn.net/mp_blog/creation/editor

【Python编程】Linux创建虚拟环境并配置与notebook相连接

1.创建 使用 venv 创建虚拟环境。例如,在当前目录下创建一个名为 myenv 的虚拟环境: python3 -m venv myenv 2.激活 激活虚拟环境使其成为当前终端会话的活动环境。运行: source myenv/bin/activate 3.与notebook连接 在虚拟环境中,使用 pip 安装 Jupyter 和 ipykernel: pip instal

【测试】输入正确用户名和密码,点击登录没有响应的可能性原因

目录 一、前端问题 1. 界面交互问题 2. 输入数据校验问题 二、网络问题 1. 网络连接中断 2. 代理设置问题 三、后端问题 1. 服务器故障 2. 数据库问题 3. 权限问题: 四、其他问题 1. 缓存问题 2. 第三方服务问题 3. 配置问题 一、前端问题 1. 界面交互问题 登录按钮的点击事件未正确绑定,导致点击后无法触发登录操作。 页面可能存在

业务中14个需要进行A/B测试的时刻[信息图]

在本指南中,我们将全面了解有关 A/B测试 的所有内容。 我们将介绍不同类型的A/B测试,如何有效地规划和启动测试,如何评估测试是否成功,您应该关注哪些指标,多年来我们发现的常见错误等等。 什么是A/B测试? A/B测试(有时称为“分割测试”)是一种实验类型,其中您创建两种或多种内容变体——如登录页面、电子邮件或广告——并将它们显示给不同的受众群体,以查看哪一种效果最好。 本质上,A/B测

【编程底层思考】垃圾收集机制,GC算法,垃圾收集器类型概述

Java的垃圾收集(Garbage Collection,GC)机制是Java语言的一大特色,它负责自动管理内存的回收,释放不再使用的对象所占用的内存。以下是对Java垃圾收集机制的详细介绍: 一、垃圾收集机制概述: 对象存活判断:垃圾收集器定期检查堆内存中的对象,判断哪些对象是“垃圾”,即不再被任何引用链直接或间接引用的对象。内存回收:将判断为垃圾的对象占用的内存进行回收,以便重新使用。

Go Playground 在线编程环境

For all examples in this and the next chapter, we will use Go Playground. Go Playground represents a web service that can run programs written in Go. It can be opened in a web browser using the follow

深入理解RxJava:响应式编程的现代方式

在当今的软件开发世界中,异步编程和事件驱动的架构变得越来越重要。RxJava,作为响应式编程(Reactive Programming)的一个流行库,为Java和Android开发者提供了一种强大的方式来处理异步任务和事件流。本文将深入探讨RxJava的核心概念、优势以及如何在实际项目中应用它。 文章目录 💯 什么是RxJava?💯 响应式编程的优势💯 RxJava的核心概念