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

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

相关文章

揭秘Python Socket网络编程的7种硬核用法

《揭秘PythonSocket网络编程的7种硬核用法》Socket不仅能做聊天室,还能干一大堆硬核操作,这篇文章就带大家看看Python网络编程的7种超实用玩法,感兴趣的小伙伴可以跟随小编一起... 目录1.端口扫描器:探测开放端口2.简易 HTTP 服务器:10 秒搭个网页3.局域网游戏:多人联机对战4.

Java并发编程必备之Synchronized关键字深入解析

《Java并发编程必备之Synchronized关键字深入解析》本文我们深入探索了Java中的Synchronized关键字,包括其互斥性和可重入性的特性,文章详细介绍了Synchronized的三种... 目录一、前言二、Synchronized关键字2.1 Synchronized的特性1. 互斥2.

Python异步编程中asyncio.gather的并发控制详解

《Python异步编程中asyncio.gather的并发控制详解》在Python异步编程生态中,asyncio.gather是并发任务调度的核心工具,本文将通过实际场景和代码示例,展示如何结合信号量... 目录一、asyncio.gather的原始行为解析二、信号量控制法:给并发装上"节流阀"三、进阶控制

SpringBoot中整合RabbitMQ(测试+部署上线最新完整)的过程

《SpringBoot中整合RabbitMQ(测试+部署上线最新完整)的过程》本文详细介绍了如何在虚拟机和宝塔面板中安装RabbitMQ,并使用Java代码实现消息的发送和接收,通过异步通讯,可以优化... 目录一、RabbitMQ安装二、启动RabbitMQ三、javascript编写Java代码1、引入

Nginx设置连接超时并进行测试的方法步骤

《Nginx设置连接超时并进行测试的方法步骤》在高并发场景下,如果客户端与服务器的连接长时间未响应,会占用大量的系统资源,影响其他正常请求的处理效率,为了解决这个问题,可以通过设置Nginx的连接... 目录设置连接超时目的操作步骤测试连接超时测试方法:总结:设置连接超时目的设置客户端与服务器之间的连接

C#多线程编程中导致死锁的常见陷阱和避免方法

《C#多线程编程中导致死锁的常见陷阱和避免方法》在C#多线程编程中,死锁(Deadlock)是一种常见的、令人头疼的错误,死锁通常发生在多个线程试图获取多个资源的锁时,导致相互等待对方释放资源,最终形... 目录引言1. 什么是死锁?死锁的典型条件:2. 导致死锁的常见原因2.1 锁的顺序问题错误示例:不同

PyCharm接入DeepSeek实现AI编程的操作流程

《PyCharm接入DeepSeek实现AI编程的操作流程》DeepSeek是一家专注于人工智能技术研发的公司,致力于开发高性能、低成本的AI模型,接下来,我们把DeepSeek接入到PyCharm中... 目录引言效果演示创建API key在PyCharm中下载Continue插件配置Continue引言

如何测试计算机的内存是否存在问题? 判断电脑内存故障的多种方法

《如何测试计算机的内存是否存在问题?判断电脑内存故障的多种方法》内存是电脑中非常重要的组件之一,如果内存出现故障,可能会导致电脑出现各种问题,如蓝屏、死机、程序崩溃等,如何判断内存是否出现故障呢?下... 如果你的电脑是崩溃、冻结还是不稳定,那么它的内存可能有问题。要进行检查,你可以使用Windows 11

C#反射编程之GetConstructor()方法解读

《C#反射编程之GetConstructor()方法解读》C#中Type类的GetConstructor()方法用于获取指定类型的构造函数,该方法有多个重载版本,可以根据不同的参数获取不同特性的构造函... 目录C# GetConstructor()方法有4个重载以GetConstructor(Type[]

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

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