二模08day1解题报告

时间:2023-03-08 23:18:27
二模08day1解题报告

T1.高中运动会(match)

N个数的最大公约数。

gcd不解释。

T2.智力游戏

火柴棒等式形如a+b=c,现在给出啊a,b,c求使等式成立的最小的移动次数。

火柴棒表示数字不用解释了吧,在此提醒一点,1的放法有2种哦。

首先处理出每个数字的火柴棒根数(打表*1),然后用num[11][7]的数组表示每个数用到7个位置中的哪几个(打表*2)(P.S.num[11][]是留给另一种1的)。

表示如下:

二模08day1解题报告

那么怎么判断呢,由于题目明确指出位数和符号不能变所以可以采用枚举的方法,首先计算出a,b,c的位数,然后枚举a,b位置的数,判断a+b的位数是否为c的位数。这还不够,还要计算目前的数字的根数和原来是否相等。那么初步判断就解决了。

难点就在于判断改变的火柴棒数,由于位数不止一位,所以要分位判断。我的判断方法是比较每位数字的组成的不同(这个我是有点烦的样子),累加,然后/2.最后取最小值。

然而看了LZW大神的题解发现,其实还可以优化。用move[i][j]算出i到j的移动数使i成为j的一部分(或者j成为i的一部分),hash[i][j]表示i和j的木棍数量差,由于数据小,可以手动处理(打表*3),然后处理起来就方便多了。

T3.周年纪念日(anniversary)

详情请见yzoi2306  But,pay attention now:根节点必须选,这是唯一的不同。

咳咳,裸的树形dp,f[i][0]和f[i][1]分别表示i结点取和不取的最大值,f[i][0]=sum(max(f[son[i][]][0],f[son[i][]][1]))  (son[i][]为vector)

f[i][1]=sum(f[son[i][]][0]).

千万记住树根必取(我就死这儿了)。