python可以做网站前端,团结湖网站建设,佛山网站推广建设,口碑好的句容网站建设2014 编程之美挑战赛 --- 资格赛真题 题目1 : 同构 时间限制:2000ms单点时限:1000ms内存限制:256MB描述 给定2个树A和B#xff0c;保证A的节点个数B的节点个数。 现在你需要对树A的边进行二染色。 一个好的染色方案#xff0c;指不存在一个树A中的连通块#xff0c;同时…2014 编程之美挑战赛 --- 资格赛真题 题目1 : 同构 时间限制:2000ms 单点时限:1000ms 内存限制:256MB 描述 给定2个树A和B保证A的节点个数B的节点个数。 现在你需要对树A的边进行二染色。 一个好的染色方案指不存在一个树A中的连通块同时满足以下2个条件 1. 其中只有同色的边 2. 和B同构。两个树同构是指存在一个一一映射既是单射又是满射将树B的各节点映射到不同的树A的节点使得原来在树B中相邻的点在映射后仍相邻。 问是否存在一种好的染色方案。 输入 第一行一个整数T (1T10)表示数据组数。 接下来是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 题目2 : 大神与三位小伙伴 时间限制:2000ms 单点时限:1000ms 内存限制:256MB 描述 L国是一个有着优美景色且物产丰富的国家很多人都喜欢来这里旅游并且喜欢带走一些纪念品大神同学也不例外。距离开L国的时间越来越近了大神同学正在烦恼给她可爱的小伙伴们带什么纪念品好现在摆在大神同学面前的有三类纪念品A, B, C可以选择每类纪念品各有N种。其中种类为A_i, B_i, C_i的纪念品价值均为i, 且分别有N1-i个剩余。现在大神同学希望在三类纪念品中各挑选一件然后赠送给她的三名可爱的小伙伴但是她又不希望恰好挑出来两件价值相同的纪念品因为这样拿到相同价值纪念品的两位小伙伴就会认为大神同学偏袒另一位小伙伴而不理睬她超过一星期。现在大神同学希望你买到的三件纪念品能让三位小伙伴都开心并且不和她闹别扭她想知道一共有多少种不同挑选的方法 因为方案数可能非常大大神同学希望知道挑选纪念品的方案数模10^97之后的答案。 输入 第一行包括一个数T表示数据的组数。 接下来包含T组数据每组数据一行包括一个整数N。 输出 对于每组数据输出一行“Case x: ”其中x表示每组数据的编号(从1开始)后接一个数表示模10^97后的选择纪念品的方案数。 数据范围 小数据 1T10 1N100 大数据 1T1000 1N10^18 样例解释 对于第二组数据合法的方案有以下几种(X,Y,Z)表示选择了A类纪念品中价值为X的B类纪念品中价值为Y的C类纪念品中价值为Z的。 (1,1,1): 3*3*327种 (1,2,3): 3*2*16种 (1,3,2): 3*1*26种 (2,1,3): 2*3*16种 (2,2,2): 2*2*28种 (2,3,1): 2*1*36种 (3,1,2): 1*3*26种 (3,2,1): 1*2*36种 (3,3,3): 1*1*11种 一共276668666172种选择纪念品的方案 注意如(1,1,2), (2,3,3), (3,1,3)都因为恰好选择了两件价值相同的纪念品所以并不是一种符合要求的纪念品选择方法。 样例输入 2
1
3样例输出 Case 1: 1
Case 2: 72 题目3 : 格格取数 时间限制:2000ms 单点时限:1000ms 内存限制:256MB 描述 给你一个m x n (1 m, n 100)的矩阵A (0aij10000)要求在矩阵中选择一些数要求每一行每一列都至少选到了一个数使得选出的数的和尽量的小。 输入 多组测试数据。首先是数据组数T 对于每组测试数据第1行是两个正整数m, n分别表示矩阵的行数和列数。 接下来的m行每行n个整数之间用一个空格分隔表示矩阵A的元素。 输出 每组数据输出一行表示选出的数的和的最小值。 数据范围 小数据1 m, n 5 大数据1 m, n 100 样例输入 2
3 3
1 2 3
3 1 2
2 3 1
5 5
1 2 3 4 5
5 1 2 3 4
4 5 1 2 3
3 4 5 1 2
2 3 4 5 1样例输出 Case 1: 3
Case 2: 5 提交页面
