4
18
2015
0

2015省选互测#2

看蒟蒻是怎么把一道傻逼题写傻逼的

 

D.BZOJ3611: [Heoi2014]大工程

虚树裸题。考前还在群里浪:“知道做过还放上去?”“锻炼码力?”然后考完就TM被打脸。。。身败名裂too young too naive

我犯了3个sb错误:

1)原图的边和虚树中的边写成了一个函数,所以就成了单向边QAQ

2)在虚树上连边的时候最后的将f入栈出了点儿问题,最后应该是add(f,sta[top--]),if(sta[top]!=f)sta[++top]=f

   然后我写成了 add(sta[top-1],sta[top],if(sta[top]!=f)sta[++top]=f

   然后导致边就跨越了。。。

3)CH上输出long long是lld。我这么多年来一直记得是I64d。。。

 

B.BZOJ3612: [Heoi2014]平衡

 

其实这题也不难,但是我直接看到题就想到背包上来了,而之后就在一直思考如何优化背包。

实际上我们要求的是f[i][j]表示用不相同的不超过n的j个数装满i的方案数。应该很有规律(其实应该算是组合经典模型吧,还是多记点儿比较好。),这类问题一般是不需要背包的。

(以后看到这种式子,要么想一下递推式,然后再用背包。)

f[i][j]=f[i-j][j]+f[i-j][j-1]-f[i-(n+1)][j-1]

第一部分是最小的不是1,第二部分是最小的是1(之所以不用f[i-1][j-1]是因为这个方案可能已经用过1了)。

然后最后一部分是最大的是n+1的方案数,所以要减掉。(最大不会是n+2,因为这个不合法是由f[i-j][j]和f[i-j][j-1]加出来的,而这些方案里最大都只可能是n)

 

C.3610: [Heoi2014]林中路径

刚看见想了想矩阵乘法么,100分到手。。。然后扭过头来写发现构造不出矩阵QAQ。

于是写了暴力的矩阵乘法。。。

啦啦来补正解啦

我看的是这里的题解

我们发现这道题直接维护  路径条数*长度*长度 的前缀和是不太好维护的,

这种情况下我们一般需要多记录几个值,比如此题就是 同时维护 路径条数*长度*长度  路径条数*长度 以及 路径条数的前缀和。

这样三个矩阵,当然还有路径条数(不是前缀和)

是可以相互递推的。

还有什么情况下可以使用矩阵乘法&快速幂呢?

如果我们由k的情况可以推出k+1的情况和2*k的情况,就可以用矩阵乘法加速。

想一想,是不是这样。我们从最高位开始搞,然后每次让k+=1,或者让k<<=1,这样总会得到n。

然后这题就搞完了。

 

A.BZOJ3609: [Heoi2014]人人尽说江南好

没想到我胡策补的最后一道题居然是胡策正式开始的第一题,可能我比较傻逼。打表找规律这种太靠智商的东西实在搞不来。。。

但是我们直接打表还是看不出什么规律的。实际上一个状态是黑手还是白手只取决于当前石子的总堆数。因为一堆数量为x的石子需要合并x-1次。

而k堆石子我们只需要合并n-k次就可以了。而由合并的次数奇偶就可以推出当前是黑手操作还是白手操作。

那么也就是说,起始状态的输赢只与终状态的石子堆数的奇偶有关。

那么我们打表发现最后剩下的石子堆数就是(n-1)/m+1。(这个表还是不太好打的QAQ)

然后直接判断就好了。

 

Category: 模拟赛 | Tags: | Read Count: 482

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter

| Theme: Aeros 2.0 by TheBuckmaker.com