6.12(e,f,g,h,i)

E - Black and White Tree

题意:

  一棵树由n个节点组成,每个节点都被涂成黑色或白色,相连的点颜色不同,每个点有一个值s[i],表示与该节点相连的边值的和,输出树的每条边连接的点和值。

思路:

  白点值的和肯定等于黑点值的和,将黑点和白点分别排序,选出最小的两个点,相连后值较小的点弹出,值较大的点减去小的值,重复直到点清空。

F - The table

题意:

  给出一个n*m的矩阵,你可以对行/列进行操作,使该行/列全部数字取反,使得矩阵中每行/列的和都大于0

思路:

  感觉就是一个贪心,每次找到行或列中和最小且小于0的取反,直到满足题目要求,取反偶数次的等于没取反

G - Start of the season

题意:

  构造一个矩阵,满足三个条件

  1)主对角线为0  2)矩阵关于主对角线对称  3)每行每列没有重复的数字

思路:

  如果只考虑2和3,且不放0,构造的矩阵就是

  123

  231

  312

  然后把主对角线替换为0

  023            0231

  201            2013

  310  然后把缺的数字补齐 3102 

                 1320

H - Polycarp's Picture Gallery

题意:

  给出m组照片,每组有ai张,选出n张照片,相邻的照片(1与n相邻)不能出自同一组。

思路:

  数据范围不是很大,感觉就是一个贪心,每次选和前一张不同的组中剩余最多的放,最后一张特判一下

I - Powerful Ksenia

题意:

  给出长度为n的序列,每次操作可以选择i,j,k三个数变成i xor j xor k,问能否在n次操作内让数列变成相同的数。

思路:

  题目不要求最小操作数,但要求在n次内,每次操作可以让三个数变成相同的数,如果i,j,k中有两个数相等,那就相当于全部变成单独出现的数,所以将序列变成相同的数对,再用一个数做一次就可以。

  如果n为奇数,直接123,345,567....最后12相同,34相同,单独出一个n,操作数为n-1符合条件

  如果n为偶数,首先序列xor值应该为0,所以序列最后相同的数是任意的,直接将n放出来做前n-1位,最后结果也会和第n位相同

原文地址:https://www.cnblogs.com/Tokisaki-Kurumi/p/14878799.html